{"id":1146,"date":"2015-07-05T01:19:25","date_gmt":"2015-07-04T17:19:25","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1146"},"modified":"2016-08-24T20:21:52","modified_gmt":"2016-08-24T12:21:52","slug":"%e3%80%90%e5%ae%8c%e5%85%a8%e7%89%88%e3%80%91%e7%ba%bf%e6%ae%b5%e6%a0%91%ef%bc%88%e8%bd%ac%e8%bd%bd%ef%bc%89","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/%e3%80%90%e5%ae%8c%e5%85%a8%e7%89%88%e3%80%91%e7%ba%bf%e6%ae%b5%e6%a0%91%ef%bc%88%e8%bd%ac%e8%bd%bd%ef%bc%89\/","title":{"rendered":"\u3010\u5b8c\u5168\u7248\u3011\u7ebf\u6bb5\u6811\uff08\u8f6c\u8f7d\uff09"},"content":{"rendered":"<p>\u6848\uff1a\u8f6c\u8f7d\u81ea <a href=\"http:\/\/www.cnblogs.com\/Mu-Tou\/archive\/2011\/08\/11\/2134427.html\">http:\/\/www.cnblogs.com\/Mu-Tou\/archive\/2011\/08\/11\/2134427.html<\/a><br \/>\n______<br \/>\n<!--more--><br \/>\n\u5f88\u65e9\u524d\u5199\u7684\u90a3\u7bc7\u7ebf\u6bb5\u6811\u4e13\u8f91\u81f3\u4eca\u4e00\u76f4\u662f\u672c\u535a\u5ba2\u9605\u8bfb\u70b9\u51fb\u91cf\u6700\u5927\u7684\u4e00\u7247\u6587\u7ae0,\u5f53\u65f6\u89c9\u5f97\u633a\u81ea\u8c6a\u7684,\u8fd8\u53bbpku\u6253\u5e7f\u544a,\u4f46\u662f\u73b0\u5728\u6211\u81ea\u5df1\u90fd\u4e0d\u592a\u597d\u610f\u601d\u53bb\u770b\u90a3\u7bc7\u6587\u7ae0\u4e86,\u89c9\u5f97\u5f53\u65f6\u7684\u4ee3\u7801\u98ce\u683c\u5b9e\u5728\u662f\u592a\u4e11\u4e86,\u5f88\u591a\u7ebf\u6bb5\u6811\u7684\u521d\u5b66\u8005\u53ef\u80fd\u5c31\u662f\u770b\u7740\u8fd9\u7bc7\u6587\u7ae0\u6765\u7ec3\u4e60\u7684,\u5982\u679c\u4e0d\u5c0f\u5fc3\u88ab\u6211\u57f9\u517b\u51fa\u4e86\u8fd9\u4e48\u7cdf\u7cd5\u7684\u98ce\u683c,\u5b9e\u5728\u662f\u8fc7\u610f\u4e0d\u53bb,\u6b63\u597d\u8fc7\u51e0\u5929\u53c8\u8981\u7ed9\u96c6\u8bad\u961f\u8bb2\u89e3\u7ebf\u6bb5\u6811,\u6240\u4ee5\u51b3\u5b9a\u628a\u8fd9\u4e9b\u9898\u76ee\u91cd\u65b0\u5199\u4e00\u904d,\u987a\u4fbf\u628a\u8fd1\u5e74\u6211\u63a5\u89e6\u5230\u7684\u4e00\u4e9b\u65b0\u9898\u66f4\u65b0\u4e0a\u53bb~;\u5e76\u4e14\u5b66\u4e60\u4e86splay\u7b49\u66f4\u9ad8\u7ea7\u7684\u6570\u636e\u7ed3\u6784\u540e\u5bf9\u7ebf\u6bb5\u6811\u7684\u4f53\u4f1a\u6709\u66f4\u6df1\u4e86\u4e00\u5c42,\u7ebf\u6bb5\u6811\u7684\u5199\u6cd5\u4e5f\u5c31\u6bd4\u4ee5\u524d\u98d8\u9038,\u7b80\u6d01\u4e14\u65b9\u4fbf\u591a\u4e86.<\/p>\n<p>\u5728\u4ee3\u7801\u524d\u5148\u4ecb\u7ecd\u4e00\u4e9b\u6211\u7684\u7ebf\u6bb5\u6811\u98ce\u683c:<\/p>\n<ul>\n<li>maxn\u662f\u9898\u76ee\u7ed9\u7684\u6700\u5927\u533a\u95f4,\u800c\u8282\u70b9\u6570\u8981\u5f004\u500d,\u786e\u5207\u7684\u6765\u8bf4\u8282\u70b9\u6570\u8981\u5f00\u5927\u4e8emaxn\u7684\u6700\u5c0f2x\u7684\u4e24\u500d<\/li>\n<li>lson\u548crson\u5206\u8fa8\u8868\u793a\u7ed3\u70b9\u7684\u5de6\u513f\u5b50\u548c\u53f3\u513f\u5b50,\u7531\u4e8e\u6bcf\u6b21\u4f20\u53c2\u6570\u7684\u65f6\u5019\u90fd\u56fa\u5b9a\u662f\u8fd9\u51e0\u4e2a\u53d8\u91cf,\u6240\u4ee5\u53ef\u4ee5\u7528\u9884\u5b9a\u4e8e\u6bd4\u8f83\u65b9\u4fbf\u7684\u8868\u793a<br \/>\n\u4ee5\u524d\u7684\u5199\u6cd5\u662f\u53e6\u5916\u5f00\u4e24\u4e2a\u4e2a\u6570\u7ec4\u8bb0\u5f55\u6bcf\u4e2a\u7ed3\u70b9\u6240\u8868\u793a\u7684\u533a\u95f4,\u5176\u5b9e\u8fd9\u4e2a\u533a\u95f4\u4e0d\u5fc5\u4fdd\u5b58,\u4e00\u8fb9\u7b97\u4e00\u8fb9\u4f20\u4e0b\u53bb\u5c31\u884c,\u53ea\u9700\u8981\u5199\u51fd\u6570\u7684\u65f6\u5019\u591a\u4e24\u4e2a\u53c2\u6570,\u7ed3\u5408lson\u548crson\u7684\u9884\u5b9a\u4e49\u53ef\u4ee5\u5f88\u65b9\u4fbf<\/li>\n<li>PushUP(int rt)\u662f\u628a\u5f53\u524d\u7ed3\u70b9\u7684\u4fe1\u606f\u66f4\u65b0\u5230\u7236\u7ed3\u70b9<\/li>\n<li>PushDown(int rt)\u662f\u628a\u5f53\u524d\u7ed3\u70b9\u7684\u4fe1\u606f\u66f4\u65b0\u7ed9\u513f\u5b50\u7ed3\u70b9<\/li>\n<li>rt\u8868\u793a\u5f53\u524d\u5b50\u6811\u7684\u6839(root),\u4e5f\u5c31\u662f\u5f53\u524d\u6240\u5728\u7684\u7ed3\u70b9<\/li>\n<\/ul>\n<p>\u6574\u7406\u8fd9\u4e9b\u9898\u76ee\u540e\u6211\u89c9\u5f97\u7ebf\u6bb5\u6811\u7684\u9898\u76ee\u6574\u4f53\u4e0a\u53ef\u4ee5\u5206\u6210\u4ee5\u4e0b\u56db\u4e2a\u90e8\u5206:<\/p>\n<h2>\u5355\u70b9\u66f4\u65b0<\/h2>\n<p>\u6700\u6700\u57fa\u7840\u7684\u7ebf\u6bb5\u6811,\u53ea\u66f4\u65b0\u53f6\u5b50\u8282\u70b9,\u7136\u540e\u628a\u4fe1\u606f\u7528PushUP(int r)\u8fd9\u4e2a\u51fd\u6570\u66f4\u65b0\u4e0a\u6765<\/p>\n<ul>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=1166\">HDU 1166. \u654c\u5175\u5e03\u9635<\/a><\/li>\n<p>\u9898\u610f:O(-1)<br \/>\n\u601d\u8def:O(-1)<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u5355\u70b9\u589e\u51cf query:\u533a\u95f4\u6c42\u548c<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n \r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\nconst int maxn = 55555;\r\nint sum&#x5B;maxn&lt;&lt;2];\r\nvoid PushUP(int rt) {\r\n       sum&#x5B;rt] = sum&#x5B;rt&lt;&lt;1] + sum&#x5B;rt&lt;&lt;1|1];\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       if (l == r) {\r\n              scanf(&quot;%d&quot;,&amp;sum&#x5B;rt]);\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n       PushUP(rt);\r\n}\r\nvoid update(int p,int add,int l,int r,int rt) {\r\n       if (l == r) {\r\n              sum&#x5B;rt] += add;\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (p &lt;= m) update(p , add , lson);\r\n       else update(p , add , rson);\r\n       PushUP(rt);\r\n}\r\nint query(int L,int R,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              return sum&#x5B;rt];\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       int ret = 0;\r\n       if (L &lt;= m) ret += query(L , R , lson);\r\n       if (R &gt; m) ret += query(L , R , rson);\r\n       return ret;\r\n}\r\nint main() {\r\n       int T , n;\r\n       scanf(&quot;%d&quot;,&amp;T);\r\n       for (int cas = 1 ; cas &lt;= T ; cas ++) {\r\n              printf(&quot;Case %d:\\n&quot;,cas);\r\n              scanf(&quot;%d&quot;,&amp;n);\r\n              build(1 , n , 1);\r\n              char op&#x5B;10];\r\n              while (scanf(&quot;%s&quot;,op)) {\r\n                     if (op&#x5B;0] == 'E') break;\r\n                     int a , b;\r\n                     scanf(&quot;%d%d&quot;,&amp;a,&amp;b);\r\n                     if (op&#x5B;0] == 'Q') printf(&quot;%d\\n&quot;,query(a , b , 1 , n , 1));\r\n                     else if (op&#x5B;0] == 'S') update(a , -b , 1 , n , 1);\r\n                     else update(a , b , 1 , n , 1);\r\n              }\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=1754\">HDU 1754. I Hate It<\/a><\/li>\n<p>\u9898\u610f:O(-1)<br \/>\n\u601d\u8def:O(-1)<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u5355\u70b9\u66ff\u6362 query:\u533a\u95f4\u6700\u503c<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n \r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\nconst int maxn = 222222;\r\nint MAX&#x5B;maxn&lt;&lt;2];\r\nvoid PushUP(int rt) {\r\n       MAX&#x5B;rt] = max(MAX&#x5B;rt&lt;&lt;1] , MAX&#x5B;rt&lt;&lt;1|1]);\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       if (l == r) {\r\n              scanf(&quot;%d&quot;,&amp;MAX&#x5B;rt]);\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n       PushUP(rt);\r\n}\r\nvoid update(int p,int sc,int l,int r,int rt) {\r\n       if (l == r) {\r\n              MAX&#x5B;rt] = sc;\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (p &lt;= m) update(p , sc , lson);\r\n       else update(p , sc , rson);\r\n       PushUP(rt);\r\n}\r\nint query(int L,int R,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              return MAX&#x5B;rt];\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       int ret = 0;\r\n       if (L &lt;= m) ret = max(ret , query(L , R , lson));\r\n       if (R &gt; m) ret = max(ret , query(L , R , rson));\r\n       return ret;\r\n}\r\nint main() {\r\n       int n , m;\r\n       while (~scanf(&quot;%d%d&quot;,&amp;n,&amp;m)) {\r\n              build(1 , n , 1);\r\n              while (m --) {\r\n                     char op&#x5B;2];\r\n                     int a , b;\r\n                     scanf(&quot;%s%d%d&quot;,op,&amp;a,&amp;b);\r\n                     if (op&#x5B;0] == 'Q') printf(&quot;%d\\n&quot;,query(a , b , 1 , n , 1));\r\n                     else update(a , b , 1 , n , 1);\r\n              }\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=1394\">HDU 1394. Minimum Inversion Number<\/a><\/li>\n<p>\u9898\u610f:\u6c42Inversion\u540e\u7684\u6700\u5c0f\u9006\u5e8f\u6570<br \/>\n\u601d\u8def:\u7528O(nlogn)\u590d\u6742\u5ea6\u6c42\u51fa\u6700\u521d\u9006\u5e8f\u6570\u540e,\u5c31\u53ef\u4ee5\u7528O(1)\u7684\u590d\u6742\u5ea6\u5206\u522b\u9012\u63a8\u51fa\u5176\u4ed6\u89e3<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u5355\u70b9\u589e\u51cf query:\u533a\u95f4\u6c42\u548c<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n \r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\nconst int maxn = 5555;\r\nint sum&#x5B;maxn&lt;&lt;2];\r\nvoid PushUP(int rt) {\r\n       sum&#x5B;rt] = sum&#x5B;rt&lt;&lt;1] + sum&#x5B;rt&lt;&lt;1|1];\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       sum&#x5B;rt] = 0;\r\n       if (l == r) return ;\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n}\r\nvoid update(int p,int l,int r,int rt) {\r\n       if (l == r) {\r\n              sum&#x5B;rt] ++;\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (p &lt;= m) update(p , lson);\r\n       else update(p , rson);\r\n       PushUP(rt);\r\n}\r\nint query(int L,int R,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              return sum&#x5B;rt];\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       int ret = 0;\r\n       if (L &lt;= m) ret += query(L , R , lson);\r\n       if (R &gt; m) ret += query(L , R , rson);\r\n       return ret;\r\n}\r\nint x&#x5B;maxn];\r\nint main() {\r\n       int n;\r\n       while (~scanf(&quot;%d&quot;,&amp;n)) {\r\n              build(0 , n - 1 , 1);\r\n              int sum = 0;\r\n              for (int i = 0 ; i &lt; n ; i ++) {\r\n                     scanf(&quot;%d&quot;,&amp;x&#x5B;i]);\r\n                     sum += query(x&#x5B;i] , n - 1 , 0 , n - 1 , 1);\r\n                     update(x&#x5B;i] , 0 , n - 1 , 1);\r\n              }\r\n              int ret = sum;\r\n              for (int i = 0 ; i &lt; n ; i ++) {\r\n                     sum += n - x&#x5B;i] - x&#x5B;i] - 1;\r\n                     ret = min(ret , sum);\r\n              }\r\n              printf(&quot;%d\\n&quot;,ret);\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=2795\">HDU 2795. Billboard<\/a><\/li>\n<p>\u9898\u610f:h*w\u7684\u6728\u677f,\u653e\u8fdb\u4e00\u4e9b1*L\u7684\u7269\u54c1,\u6c42\u6bcf\u6b21\u653e\u7a7a\u95f4\u80fd\u5bb9\u7eb3\u4e14\u6700\u4e0a\u8fb9\u7684\u4f4d\u5b50<br \/>\n\u601d\u8def:\u6bcf\u6b21\u627e\u5230\u6700\u5927\u503c\u7684\u4f4d\u5b50,\u7136\u540e\u51cf\u53bbL<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:query:\u533a\u95f4\u6c42\u6700\u5927\u503c\u7684\u4f4d\u5b50(\u76f4\u63a5\u628aupdate\u7684\u64cd\u4f5c\u5728query\u91cc\u505a\u4e86)<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n \r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\nconst int maxn = 222222;\r\nint h , w , n;\r\nint MAX&#x5B;maxn&lt;&lt;2];\r\nvoid PushUP(int rt) {\r\n       MAX&#x5B;rt] = max(MAX&#x5B;rt&lt;&lt;1] , MAX&#x5B;rt&lt;&lt;1|1]);\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       MAX&#x5B;rt] = w;\r\n       if (l == r) return ;\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n}\r\nint query(int x,int l,int r,int rt) {\r\n       if (l == r) {\r\n              MAX&#x5B;rt] -= x;\r\n              return l;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       int ret = (MAX&#x5B;rt&lt;&lt;1] &gt;= x) ? query(x , lson) : query(x , rson);\r\n       PushUP(rt);\r\n       return ret;\r\n}\r\nint main() {\r\n       while (~scanf(&quot;%d%d%d&quot;,&amp;h,&amp;w,&amp;n)) {\r\n              if (h &gt; n) h = n;\r\n              build(1 , h , 1);\r\n              while (n --) {\r\n                     int x;\r\n                     scanf(&quot;%d&quot;,&amp;x);\r\n                     if (MAX&#x5B;1] &lt; x) puts(&quot;-1&quot;);\r\n                     else printf(&quot;%d\\n&quot;,query(x , 1 , h , 1));\r\n              }\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<h3>\u7ec3\u4e60<\/h3>\n<li><a href=\"http:\/\/poj.org\/problem?id=2828\">POJ 2828. Buy Tickets<\/a><\/li>\n<li><a href=\"http:\/\/poj.org\/problem?id=2886\">POJ 2886. Who Gets the Most Candies?<\/a><\/li>\n<h2>\u6210\u6bb5\u66f4\u65b0<\/h2>\n<p>\u901a\u5e38\u8fd9\u5bf9\u521d\u5b66\u8005\u6765\u8bf4\u662f\u4e00\u9053\u574e,\u9700\u8981\u7528\u5230\u5ef6\u8fdf\u6807\u8bb0(\u6216\u8005\u8bf4\u61d2\u60f0\u6807\u8bb0),\u7b80\u5355\u6765\u8bf4\u5c31\u662f\u6bcf\u6b21\u66f4\u65b0\u7684\u65f6\u5019\u4e0d\u8981\u66f4\u65b0\u5230\u5e95,\u7528\u5ef6\u8fdf\u6807\u8bb0\u4f7f\u5f97\u66f4\u65b0\u5ef6\u8fdf\u5230\u4e0b\u6b21\u9700\u8981\u66f4\u65b0or\u8be2\u95ee\u5230\u7684\u65f6\u5019<\/p>\n<li>hdu1698 Just a Hook<\/li>\n<p>\u9898\u610f:O(-1)<br \/>\n\u601d\u8def:O(-1)<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u6210\u6bb5\u66ff\u6362 (\u7531\u4e8e\u53eaquery\u4e00\u6b21\u603b\u533a\u95f4,\u6240\u4ee5\u53ef\u4ee5\u76f4\u63a5\u8f93\u51fa1\u7ed3\u70b9\u7684\u4fe1\u606f)<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n \r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\nconst int maxn = 111111;\r\nint h , w , n;\r\nint col&#x5B;maxn&lt;&lt;2];\r\nint sum&#x5B;maxn&lt;&lt;2];\r\nvoid PushUp(int rt) {\r\n       sum&#x5B;rt] = sum&#x5B;rt&lt;&lt;1] + sum&#x5B;rt&lt;&lt;1|1];\r\n}\r\nvoid PushDown(int rt,int m) {\r\n       if (col&#x5B;rt]) {\r\n              col&#x5B;rt&lt;&lt;1] = col&#x5B;rt&lt;&lt;1|1] = col&#x5B;rt];\r\n              sum&#x5B;rt&lt;&lt;1] = (m - (m &gt;&gt; 1)) * col&#x5B;rt];\r\n              sum&#x5B;rt&lt;&lt;1|1] = (m &gt;&gt; 1) * col&#x5B;rt];\r\n              col&#x5B;rt] = 0;\r\n       }\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       col&#x5B;rt] = 0;\r\n       sum&#x5B;rt] = 1;\r\n       if (l == r) return ;\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n       PushUp(rt);\r\n}\r\nvoid update(int L,int R,int c,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              col&#x5B;rt] = c;\r\n              sum&#x5B;rt] = c * (r - l + 1);\r\n              return ;\r\n       }\r\n       PushDown(rt , r - l + 1);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(L , R , c , lson);\r\n       if (R &gt; m) update(L , R , c , rson);\r\n       PushUp(rt);\r\n}\r\nint main() {\r\n       int T , n , m;\r\n       scanf(&quot;%d&quot;,&amp;T);\r\n       for (int cas = 1 ; cas &lt;= T ; cas ++) {\r\n              scanf(&quot;%d%d&quot;,&amp;n,&amp;m);\r\n              build(1 , n , 1);\r\n              while (m --) {\r\n                     int a , b , c;\r\n                     scanf(&quot;%d%d%d&quot;,&amp;a,&amp;b,&amp;c);\r\n                     update(a , b , c , 1 , n , 1);\r\n              }\r\n              printf(&quot;Case %d: The total value of the hook is %d.\\n&quot;,cas , sum&#x5B;1]);\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li>poj3468 A Simple Problem with Integers<\/li>\n<p>\u9898\u610f:O(-1)<br \/>\n\u601d\u8def:O(-1)<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u6210\u6bb5\u589e\u51cf query:\u533a\u95f4\u6c42\u548c<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n \r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\n#define LL long long\r\nconst int maxn = 111111;\r\nLL add&#x5B;maxn&lt;&lt;2];\r\nLL sum&#x5B;maxn&lt;&lt;2];\r\nvoid PushUp(int rt) {\r\n       sum&#x5B;rt] = sum&#x5B;rt&lt;&lt;1] + sum&#x5B;rt&lt;&lt;1|1];\r\n}\r\nvoid PushDown(int rt,int m) {\r\n       if (add&#x5B;rt]) {\r\n              add&#x5B;rt&lt;&lt;1] += add&#x5B;rt];\r\n              add&#x5B;rt&lt;&lt;1|1] += add&#x5B;rt];\r\n              sum&#x5B;rt&lt;&lt;1] += add&#x5B;rt] * (m - (m &gt;&gt; 1));\r\n              sum&#x5B;rt&lt;&lt;1|1] += add&#x5B;rt] * (m &gt;&gt; 1);\r\n              add&#x5B;rt] = 0;\r\n       }\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       add&#x5B;rt] = 0;\r\n       if (l == r) {\r\n              scanf(&quot;%lld&quot;,&amp;sum&#x5B;rt]);\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n       PushUp(rt);\r\n}\r\nvoid update(int L,int R,int c,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              add&#x5B;rt] += c;\r\n              sum&#x5B;rt] += (LL)c * (r - l + 1);\r\n              return ;\r\n       }\r\n       PushDown(rt , r - l + 1);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(L , R , c , lson);\r\n       if (m &lt; R) update(L , R , c , rson);\r\n       PushUp(rt);\r\n}\r\nLL query(int L,int R,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              return sum&#x5B;rt];\r\n       }\r\n       PushDown(rt , r - l + 1);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       LL ret = 0;\r\n       if (L &lt;= m) ret += query(L , R , lson);\r\n       if (m &lt; R) ret += query(L , R , rson);\r\n       return ret;\r\n}\r\nint main() {\r\n       int N , Q;\r\n       scanf(&quot;%d%d&quot;,&amp;N,&amp;Q);\r\n       build(1 , N , 1);\r\n       while (Q --) {\r\n              char op&#x5B;2];\r\n              int a , b , c;\r\n              scanf(&quot;%s&quot;,op);\r\n              if (op&#x5B;0] == 'Q') {\r\n                     scanf(&quot;%d%d&quot;,&amp;a,&amp;b);\r\n                     printf(&quot;%lld\\n&quot;,query(a , b , 1 , N , 1));\r\n              } else {\r\n                     scanf(&quot;%d%d%d&quot;,&amp;a,&amp;b,&amp;c);\r\n                     update(a , b , c , 1 , N , 1);\r\n              }\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li>poj2528 Mayor\u2019s posters<\/li>\n<p>\u9898\u610f:\u5728\u5899\u4e0a\u8d34\u6d77\u62a5,\u6d77\u62a5\u53ef\u4ee5\u4e92\u76f8\u8986\u76d6,\u95ee\u6700\u540e\u53ef\u4ee5\u770b\u89c1\u51e0\u5f20\u6d77\u62a5<br \/>\n\u601d\u8def:\u8fd9\u9898\u6570\u636e\u8303\u56f4\u5f88\u5927,\u76f4\u63a5\u641e\u8d85\u65f6+\u8d85\u5185\u5b58,\u9700\u8981\u79bb\u6563\u5316:<br \/>\n\u79bb\u6563\u5316\u7b80\u5355\u7684\u6765\u8bf4\u5c31\u662f\u53ea\u53d6\u6211\u4eec\u9700\u8981\u7684\u503c\u6765\u7528,\u6bd4\u5982\u8bf4\u533a\u95f4[1000,2000],[1990,2012] \u6211\u4eec\u7528\u4e0d\u5230[-\u221e,999][1001,1989][1991,1999][2001,2011][2013,+\u221e]\u8fd9\u4e9b\u503c,\u6240\u4ee5\u6211\u53ea\u9700\u89811000,1990,2000,2012\u5c31\u591f\u4e86,\u5c06\u5176\u5206\u522b\u6620\u5c04\u52300,1,2,3,\u5728\u4e8e\u590d\u6742\u5ea6\u5c31\u5927\u5927\u7684\u964d\u4e0b\u6765\u4e86<br \/>\n\u6240\u4ee5\u79bb\u6563\u5316\u8981\u4fdd\u5b58\u6240\u6709\u9700\u8981\u7528\u5230\u7684\u503c,\u6392\u5e8f\u540e,\u5206\u522b\u6620\u5c04\u52301~n,\u8fd9\u6837\u590d\u6742\u5ea6\u5c31\u4f1a\u5c0f\u5f88\u591a\u5f88\u591a<br \/>\n\u800c\u8fd9\u9898\u7684\u96be\u70b9\u5728\u4e8e\u6bcf\u4e2a\u6570\u5b57\u5176\u5b9e\u8868\u793a\u7684\u662f\u4e00\u4e2a\u5355\u4f4d\u957f\u5ea6(\u5e76\u4e14\u4e00\u4e2a\u70b9),\u8fd9\u6837\u666e\u901a\u7684\u79bb\u6563\u5316\u4f1a\u9020\u6210\u8bb8\u591a\u9519\u8bef(\u5305\u62ec\u6211\u4ee5\u524d\u7684\u4ee3\u7801,poj\u8fd9\u9898\u6570\u636e\u5947\u5f31)<br \/>\n\u7ed9\u51fa\u4e0b\u9762\u4e24\u4e2a\u7b80\u5355\u7684\u4f8b\u5b50\u5e94\u8be5\u80fd\u4f53\u73b0\u666e\u901a\u79bb\u6563\u5316\u7684\u7f3a\u9677:<br \/>\n1-10 1-4 5-10<br \/>\n1-10 1-4 6-10<br \/>\n\u4e3a\u4e86\u89e3\u51b3\u8fd9\u79cd\u7f3a\u9677,\u6211\u4eec\u53ef\u4ee5\u5728\u6392\u5e8f\u540e\u7684\u6570\u7ec4\u4e0a\u52a0\u4e9b\u5904\u7406,\u6bd4\u5982\u8bf4[1,2,6,10]<br \/>\n\u5982\u679c\u76f8\u90bb\u6570\u5b57\u95f4\u8ddd\u5927\u4e8e1\u7684\u8bdd,\u5728\u5176\u4e2d\u52a0\u4e0a\u4efb\u610f\u4e00\u4e2a\u6570\u5b57,\u6bd4\u5982\u52a0\u6210[1,2,3,6,7,10],\u7136\u540e\u518d\u505a\u7ebf\u6bb5\u6811\u5c31\u597d\u4e86.<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u6210\u6bb5\u66ff\u6362 query:\u7b80\u5355hash<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\n \r\nconst int maxn = 11111;\r\nbool hash&#x5B;maxn];\r\nint li&#x5B;maxn] , ri&#x5B;maxn];\r\nint X&#x5B;maxn*3];\r\nint col&#x5B;maxn&lt;&lt;4];\r\nint cnt;\r\n \r\nvoid PushDown(int rt) {\r\n       if (col&#x5B;rt] != -1) {\r\n              col&#x5B;rt&lt;&lt;1] = col&#x5B;rt&lt;&lt;1|1] = col&#x5B;rt];\r\n              col&#x5B;rt] = -1;\r\n       }\r\n}\r\nvoid update(int L,int R,int c,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              col&#x5B;rt] = c;\r\n              return ;\r\n       }\r\n       PushDown(rt);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(L , R , c , lson);\r\n       if (m &lt; R) update(L , R , c , rson);\r\n}\r\nvoid query(int l,int r,int rt) {\r\n       if (col&#x5B;rt] != -1) {\r\n              if (!hash&#x5B;col&#x5B;rt]]) cnt ++;\r\n              hash&#x5B; col&#x5B;rt] ] = true;\r\n              return ;\r\n       }\r\n       if (l == r) return ;\r\n       int m = (l + r) &gt;&gt; 1;\r\n       query(lson);\r\n       query(rson);\r\n}\r\nint Bin(int key,int n,int X&#x5B;]) {\r\n       int l = 0 , r = n - 1;\r\n       while (l &lt;= r) {\r\n              int m = (l + r) &gt;&gt; 1;\r\n              if (X&#x5B;m] == key) return m;\r\n              if (X&#x5B;m] &lt; key) l = m + 1;\r\n              else r = m - 1;\r\n       }\r\n       return -1;\r\n}\r\nint main() {\r\n       int T , n;\r\n       scanf(&quot;%d&quot;,&amp;T);\r\n       while (T --) {\r\n              scanf(&quot;%d&quot;,&amp;n);\r\n              int nn = 0;\r\n              for (int i = 0 ; i &lt; n ; i ++) {\r\n                     scanf(&quot;%d%d&quot;,&amp;li&#x5B;i] , &amp;ri&#x5B;i]);\r\n                     X&#x5B;nn++] = li&#x5B;i];\r\n                     X&#x5B;nn++] = ri&#x5B;i];\r\n              }\r\n              sort(X , X + nn);\r\n              int m = 1;\r\n              for (int i = 1 ; i &lt; nn; i ++) {\r\n                     if (X&#x5B;i] != X&#x5B;i-1]) X&#x5B;m ++] = X&#x5B;i];\r\n              }\r\n              for (int i = m - 1 ; i &gt; 0 ; i --) {\r\n                     if (X&#x5B;i] != X&#x5B;i-1] + 1) X&#x5B;m ++] = X&#x5B;i] + 1;\r\n              }\r\n              sort(X , X + m);\r\n              memset(col , -1 , sizeof(col));\r\n              for (int i = 0 ; i &lt; n ; i ++) {\r\n                     int l = Bin(li&#x5B;i] , m , X);\r\n                     int r = Bin(ri&#x5B;i] , m , X);\r\n                     update(l , r , i , 0 , m , 1);\r\n              }\r\n              cnt = 0;\r\n              memset(hash , false , sizeof(hash));\r\n              query(0 , m , 1);\r\n              printf(&quot;%d\\n&quot;,cnt);\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li>poj3225 Help with Intervals<\/li>\n<p>\u9898\u610f:\u533a\u95f4\u64cd\u4f5c,\u4ea4,\u5e76,\u8865\u7b49<br \/>\n\u601d\u8def:<br \/>\n\u6211\u4eec\u4e00\u4e2a\u4e00\u4e2a\u64cd\u4f5c\u6765\u5206\u6790:(\u75280\u548c1\u8868\u793a\u662f\u5426\u5305\u542b\u533a\u95f4,-1\u8868\u793a\u8be5\u533a\u95f4\u5185\u65e2\u6709\u5305\u542b\u53c8\u6709\u4e0d\u5305\u542b)<br \/>\nU:\u628a\u533a\u95f4[l,r]\u8986\u76d6\u62101<br \/>\nI:\u628a[-\u221e,l)(r,\u221e]\u8986\u76d6\u62100<br \/>\nD:\u628a\u533a\u95f4[l,r]\u8986\u76d6\u62100<br \/>\nC:\u628a[-\u221e,l)(r,\u221e]\u8986\u76d6\u62100 , \u4e14[l,r]\u533a\u95f40\/1\u4e92\u6362<br \/>\nS:[l,r]\u533a\u95f40\/1\u4e92\u6362<\/p>\n<p>\u6210\u6bb5\u8986\u76d6\u7684\u64cd\u4f5c\u5f88\u7b80\u5355,\u6bd4\u8f83\u7279\u6b8a\u7684\u5c31\u662f\u533a\u95f40\/1\u4e92\u6362\u8fd9\u4e2a\u64cd\u4f5c,\u6211\u4eec\u53ef\u4ee5\u79f0\u4e4b\u4e3a\u5f02\u6216\u64cd\u4f5c<br \/>\n\u5f88\u660e\u663e\u6211\u4eec\u53ef\u4ee5\u77e5\u9053\u8fd9\u4e2a\u6027\u8d28:\u5f53\u4e00\u4e2a\u533a\u95f4\u88ab\u8986\u76d6\u540e,\u4e0d\u7ba1\u4e4b\u524d\u6709\u6ca1\u6709\u5f02\u6216\u6807\u8bb0\u90fd\u6ca1\u6709\u610f\u4e49\u4e86<br \/>\n\u6240\u4ee5\u5f53\u4e00\u4e2a\u8282\u70b9\u5f97\u5230\u8986\u76d6\u6807\u8bb0\u65f6\u628a\u5f02\u6216\u6807\u8bb0\u6e05\u7a7a<br \/>\n\u800c\u5f53\u4e00\u4e2a\u8282\u70b9\u5f97\u5230\u5f02\u6216\u6807\u8bb0\u7684\u65f6\u5019,\u5148\u5224\u65ad\u8986\u76d6\u6807\u8bb0,\u5982\u679c\u662f0\u62161,\u76f4\u63a5\u6539\u53d8\u4e00\u4e0b\u8986\u76d6\u6807\u8bb0,\u4e0d\u7136\u7684\u8bdd\u6539\u53d8\u5f02\u6216\u6807\u8bb0<\/p>\n<p>\u5f00\u533a\u95f4\u95ed\u533a\u95f4\u53ea\u8981\u6570\u5b57\u4e58\u4ee52\u5c31\u53ef\u4ee5\u5904\u7406(\u5076\u6570\u8868\u793a\u7aef\u70b9,\u5947\u6570\u8868\u793a\u4e24\u7aef\u70b9\u95f4\u7684\u533a\u95f4)<br \/>\n\u7ebf\u6bb5\u6811\u529f\u80fd:update:\u6210\u6bb5\u66ff\u6362,\u533a\u95f4\u5f02\u6216 query:\u7b80\u5355hash<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;cctype&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\n \r\nconst int maxn = 131072;\r\nbool hash&#x5B;maxn];\r\nint cover&#x5B;maxn&lt;&lt;2];\r\nint XOR&#x5B;maxn&lt;&lt;2];\r\nvoid FXOR(int rt) {\r\n       if (cover&#x5B;rt] != -1) cover&#x5B;rt] ^= 1;\r\n       else XOR&#x5B;rt] ^= 1;\r\n}\r\nvoid PushDown(int rt) {\r\n       if (cover&#x5B;rt] != -1) {\r\n              cover&#x5B;rt&lt;&lt;1] = cover&#x5B;rt&lt;&lt;1|1] = cover&#x5B;rt];\r\n              XOR&#x5B;rt&lt;&lt;1] = XOR&#x5B;rt&lt;&lt;1|1] = 0;\r\n              cover&#x5B;rt] = -1;\r\n       }\r\n       if (XOR&#x5B;rt]) {\r\n              FXOR(rt&lt;&lt;1);\r\n              FXOR(rt&lt;&lt;1|1);\r\n              XOR&#x5B;rt] = 0;\r\n       }\r\n}\r\nvoid update(char op,int L,int R,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              if (op == 'U') {\r\n                     cover&#x5B;rt] = 1;\r\n                     XOR&#x5B;rt] = 0;\r\n              } else if (op == 'D') {\r\n                     cover&#x5B;rt] = 0;\r\n                     XOR&#x5B;rt] = 0;\r\n              } else if (op == 'C' || op == 'S') {\r\n                     FXOR(rt);\r\n              }\r\n              return ;\r\n       }\r\n       PushDown(rt);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(op , L , R , lson);\r\n       else if (op == 'I' || op == 'C') {\r\n              XOR&#x5B;rt&lt;&lt;1] = cover&#x5B;rt&lt;&lt;1] = 0;\r\n       }\r\n       if (m &lt; R) update(op , L , R , rson);\r\n       else if (op == 'I' || op == 'C') {\r\n              XOR&#x5B;rt&lt;&lt;1|1] = cover&#x5B;rt&lt;&lt;1|1] = 0;\r\n       }\r\n}\r\nvoid query(int l,int r,int rt) {\r\n       if (cover&#x5B;rt] == 1) {\r\n              for (int it = l ; it &lt;= r ; it ++) {\r\n                     hash&#x5B;it] = true;\r\n              }\r\n              return ;\r\n       } else if (cover&#x5B;rt] == 0) return ;\r\n       if (l == r) return ;\r\n       PushDown(rt);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       query(lson);\r\n       query(rson);\r\n}\r\nint main() {\r\n       cover&#x5B;1] = XOR&#x5B;1] = 0;\r\n       char op , l , r;\r\n       int a , b;\r\n       while ( ~scanf(&quot;%c %c%d,%d%c\\n&quot;,&amp;op , &amp;l , &amp;a , &amp;b , &amp;r) ) {\r\n              a &lt;&lt;= 1 , b &lt;&lt;= 1;\r\n              if (l == '(') a ++;\r\n              if (r == ')') b --;\r\n              if (a &gt; b) {\r\n                     if (op == 'C' || op == 'I') {\r\n                            cover&#x5B;1] = XOR&#x5B;1] = 0;\r\n                     }\r\n              } else update(op , a , b , 0 , maxn , 1);\r\n       }\r\n       query(0 , maxn , 1);\r\n       bool flag = false;\r\n       int s = -1 , e;\r\n       for (int i = 0 ; i &lt;= maxn ; i ++) {\r\n              if (hash&#x5B;i]) {\r\n                     if (s == -1) s = i;\r\n                     e = i;\r\n              } else {\r\n                     if (s != -1) {\r\n                            if (flag) printf(&quot; &quot;);\r\n                            flag = true;\r\n                            printf(&quot;%c%d,%d%c&quot;,s&amp;1?'(':'&#x5B;' , s&gt;&gt;1 , (e+1)&gt;&gt;1 , e&amp;1?')':']');\r\n                            s = -1;\r\n                     }\r\n              }\r\n       }\r\n       if (!flag) printf(&quot;empty set&quot;);\r\n       puts(&quot;&quot;);\r\n       return 0;\r\n}\r\n<\/pre>\n<h3>\u7ec3\u4e60<\/h3>\n<li>poj1436 Horizontally Visible Segments<\/li>\n<li>poj2991 Crane<\/li>\n<li>Another LCIS<\/li>\n<li>Bracket Sequence<\/li>\n<h2>\u533a\u95f4\u5408\u5e76<\/h2>\n<p><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/contest\/view.action?cid=25506#overview\">Hust &#8211; \u3010\u4e60\u9898\u7d22\u5f15\u3011\u7ebf\u6bb5\u6811, \u533a\u95f4\u5408\u5e76<\/a><\/p>\n<p>\u8fd9\u7c7b\u9898\u76ee\u4f1a\u8be2\u95ee\u533a\u95f4\u4e2d\u6ee1\u8db3\u6761\u4ef6\u7684\u8fde\u7eed\u6700\u957f\u533a\u95f4,\u6240\u4ee5PushUp\u7684\u65f6\u5019\u9700\u8981\u5bf9\u5de6\u53f3\u513f\u5b50\u7684\u533a\u95f4\u8fdb\u884c\u5408\u5e76<\/p>\n<li>poj3667 Hotel<\/li>\n<p>\u9898\u610f:1 a:\u8be2\u95ee\u662f\u4e0d\u662f\u6709\u8fde\u7eed\u957f\u5ea6\u4e3aa\u7684\u7a7a\u623f\u95f4,\u6709\u7684\u8bdd\u4f4f\u8fdb\u6700\u5de6\u8fb9<br \/>\n2 a b:\u5c06[a,a+b-1]\u7684\u623f\u95f4\u6e05\u7a7a<br \/>\n\u601d\u8def:\u8bb0\u5f55\u533a\u95f4\u4e2d\u6700\u957f\u7684\u7a7a\u623f\u95f4<br \/>\n\u7ebf\u6bb5\u6811\u64cd\u4f5c:update:\u533a\u95f4\u66ff\u6362 query:\u8be2\u95ee\u6ee1\u8db3\u6761\u4ef6\u7684\u6700\u5de6\u65ad\u70b9<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n #include &lt;cstdio&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;cctype&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\n \r\nconst int maxn = 55555;\r\nint lsum&#x5B;maxn&lt;&lt;2] , rsum&#x5B;maxn&lt;&lt;2] , msum&#x5B;maxn&lt;&lt;2];\r\nint cover&#x5B;maxn&lt;&lt;2];\r\n \r\nvoid PushDown(int rt,int m) {\r\n       if (cover&#x5B;rt] != -1) {\r\n              cover&#x5B;rt&lt;&lt;1] = cover&#x5B;rt&lt;&lt;1|1] = cover&#x5B;rt];\r\n              msum&#x5B;rt&lt;&lt;1] = lsum&#x5B;rt&lt;&lt;1] = rsum&#x5B;rt&lt;&lt;1] = cover&#x5B;rt] ? 0 : m - (m &gt;&gt; 1);\r\n              msum&#x5B;rt&lt;&lt;1|1] = lsum&#x5B;rt&lt;&lt;1|1] = rsum&#x5B;rt&lt;&lt;1|1] = cover&#x5B;rt] ? 0 : (m &gt;&gt; 1);\r\n              cover&#x5B;rt] = -1;\r\n       }\r\n}\r\nvoid PushUp(int rt,int m) {\r\n       lsum&#x5B;rt] = lsum&#x5B;rt&lt;&lt;1];\r\n       rsum&#x5B;rt] = rsum&#x5B;rt&lt;&lt;1|1];\r\n       if (lsum&#x5B;rt] == m - (m &gt;&gt; 1)) lsum&#x5B;rt] += lsum&#x5B;rt&lt;&lt;1|1];\r\n       if (rsum&#x5B;rt] == (m &gt;&gt; 1)) rsum&#x5B;rt] += rsum&#x5B;rt&lt;&lt;1];\r\n       msum&#x5B;rt] = max(lsum&#x5B;rt&lt;&lt;1|1] + rsum&#x5B;rt&lt;&lt;1] , max(msum&#x5B;rt&lt;&lt;1] , msum&#x5B;rt&lt;&lt;1|1]));\r\n}\r\nvoid build(int l,int r,int rt) {\r\n       msum&#x5B;rt] = lsum&#x5B;rt] = rsum&#x5B;rt] = r - l + 1;\r\n       cover&#x5B;rt] = -1;\r\n       if (l == r) return ;\r\n       int m = (l + r) &gt;&gt; 1;\r\n       build(lson);\r\n       build(rson);\r\n}\r\nvoid update(int L,int R,int c,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              msum&#x5B;rt] = lsum&#x5B;rt] = rsum&#x5B;rt] = c ? 0 : r - l + 1;\r\n              cover&#x5B;rt] = c;\r\n              return ;\r\n       }\r\n       PushDown(rt , r - l + 1);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(L , R , c , lson);\r\n       if (m &lt; R) update(L , R , c , rson);\r\n       PushUp(rt , r - l + 1);\r\n}\r\nint query(int w,int l,int r,int rt) {\r\n       if (l == r) return l;\r\n       PushDown(rt , r - l + 1);\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (msum&#x5B;rt&lt;&lt;1] &gt;= w) return query(w , lson);\r\n       else if (rsum&#x5B;rt&lt;&lt;1] + lsum&#x5B;rt&lt;&lt;1|1] &gt;= w) return m - rsum&#x5B;rt&lt;&lt;1] + 1;\r\n       return query(w , rson);\r\n}\r\nint main() {\r\n       int n , m;\r\n       scanf(&quot;%d%d&quot;,&amp;n,&amp;m);\r\n       build(1 , n , 1);\r\n       while (m --) {\r\n              int op , a , b;\r\n              scanf(&quot;%d&quot;,&amp;op);\r\n              if (op == 1) {\r\n                     scanf(&quot;%d&quot;,&amp;a);\r\n                     if (msum&#x5B;1] &lt; a) puts(&quot;0&quot;);\r\n                     else {\r\n                            int p = query(a , 1 , n , 1);\r\n                            printf(&quot;%d\\n&quot;,p);\r\n                            update(p , p + a - 1 , 1 , 1 , n , 1);\r\n                     }\r\n              } else {\r\n                     scanf(&quot;%d%d&quot;,&amp;a,&amp;b);\r\n                     update(a , a + b - 1 , 0 , 1 , n , 1);\r\n              }\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<p>\u7ec3\u4e60:<\/p>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=3308\">HDU 3308. LCIS<\/a><\/li>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=3397\">HDU 3397. Sequence operation<\/a><\/li>\n<li><a href=\"https:\/\/vijos.org\/p\/1874\">Vijos 1874. \u5c0f\u5c9b\u7684\u5b9d\u77f3\u4e32<\/a><\/li>\n<p>hdu2871 Memory Control<br \/>\nhdu1540 Tunnel Warfare<br \/>\nCF46-D Parking Lot<\/p>\n<h2>\u626b\u63cf\u7ebf<\/h2>\n<p>\u8fd9\u7c7b\u9898\u76ee\u9700\u8981\u5c06\u4e00\u4e9b\u64cd\u4f5c\u6392\u5e8f,\u7136\u540e\u4ece\u5de6\u5230\u53f3\u7528\u4e00\u6839\u626b\u63cf\u7ebf(\u5f53\u7136\u662f\u5728\u6211\u4eec\u8111\u5b50\u91cc)\u626b\u8fc7\u53bb<br \/>\n\u6700\u5178\u578b\u7684\u5c31\u662f\u77e9\u5f62\u9762\u79ef\u5e76,\u5468\u957f\u5e76\u7b49\u9898<\/p>\n<li>hdu1542 Atlantis<\/li>\n<p>\u9898\u610f:\u77e9\u5f62\u9762\u79ef\u5e76<br \/>\n\u601d\u8def:\u6d6e\u70b9\u6570\u5148\u8981\u79bb\u6563\u5316;\u7136\u540e\u628a\u77e9\u5f62\u5206\u6210\u4e24\u6761\u8fb9,\u4e0a\u8fb9\u548c\u4e0b\u8fb9,\u5bf9\u6a2a\u8f74\u5efa\u6811,\u7136\u540e\u4ece\u4e0b\u5230\u4e0a\u626b\u63cf\u4e0a\u53bb,\u7528cnt\u8868\u793a\u8be5\u533a\u95f4\u4e0b\u8fb9\u6bd4\u4e0a\u8fb9\u591a\u51e0\u4e2a<br \/>\n\u7ebf\u6bb5\u6811\u64cd\u4f5c:update:\u533a\u95f4\u589e\u51cf query:\u76f4\u63a5\u53d6\u6839\u8282\u70b9\u7684\u503c<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;cctype&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\n \r\nconst int maxn = 2222;\r\nint cnt&#x5B;maxn &lt;&lt; 2];\r\ndouble sum&#x5B;maxn &lt;&lt; 2];\r\ndouble X&#x5B;maxn];\r\nstruct Seg {\r\n       double h , l , r;\r\n       int s;\r\n       Seg(){}\r\n       Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}\r\n       bool operator &lt; (const Seg &amp;cmp) const {\r\n              return h &lt; cmp.h;\r\n       }\r\n}ss&#x5B;maxn];\r\nvoid PushUp(int rt,int l,int r) {\r\n       if (cnt&#x5B;rt]) sum&#x5B;rt] = X&#x5B;r+1] - X&#x5B;l];\r\n       else if (l == r) sum&#x5B;rt] = 0;\r\n       else sum&#x5B;rt] = sum&#x5B;rt&lt;&lt;1] + sum&#x5B;rt&lt;&lt;1|1];\r\n}\r\nvoid update(int L,int R,int c,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              cnt&#x5B;rt] += c;\r\n              PushUp(rt , l , r);\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(L , R , c , lson);\r\n       if (m &lt; R) update(L , R , c , rson);\r\n       PushUp(rt , l , r);\r\n}\r\nint Bin(double key,int n,double X&#x5B;]) {\r\n       int l = 0 , r = n - 1;\r\n       while (l &lt;= r) {\r\n              int m = (l + r) &gt;&gt; 1;\r\n              if (X&#x5B;m] == key) return m;\r\n              if (X&#x5B;m] &lt; key) l = m + 1;\r\n              else r = m - 1;\r\n       }\r\n       return -1;\r\n}\r\nint main() {\r\n       int n , cas = 1;\r\n       while (~scanf(&quot;%d&quot;,&amp;n) &amp;&amp; n) {\r\n              int m = 0;\r\n              while (n --) {\r\n                     double a , b , c , d;\r\n                     scanf(&quot;%lf%lf%lf%lf&quot;,&amp;a,&amp;b,&amp;c,&amp;d);\r\n                     X&#x5B;m] = a;\r\n                     ss&#x5B;m++] = Seg(a , c , b , 1);\r\n                     X&#x5B;m] = c;\r\n                     ss&#x5B;m++] = Seg(a , c , d , -1);\r\n              }\r\n              sort(X , X + m);\r\n              sort(ss , ss + m);\r\n              int k = 1;\r\n              for (int i = 1 ; i &lt; m ; i ++) {\r\n                     if (X&#x5B;i] != X&#x5B;i-1]) X&#x5B;k++] = X&#x5B;i];\r\n              }\r\n              memset(cnt , 0 , sizeof(cnt));\r\n              memset(sum , 0 , sizeof(sum));\r\n              double ret = 0;\r\n              for (int i = 0 ; i &lt; m - 1 ; i ++) {\r\n                     int l = Bin(ss&#x5B;i].l , k , X);\r\n                     int r = Bin(ss&#x5B;i].r , k , X) - 1;\r\n                     if (l &lt;= r) update(l , r , ss&#x5B;i].s , 0 , k - 1, 1);\r\n                     ret += sum&#x5B;1] * (ss&#x5B;i+1].h - ss&#x5B;i].h);\r\n              }\r\n              printf(&quot;Test case #%d\\nTotal explored area: %.2lf\\n\\n&quot;,cas++ , ret);\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<li>hdu1828 Picture<\/li>\n<p>\u9898\u610f:\u77e9\u5f62\u5468\u957f\u5e76<br \/>\n\u601d\u8def:\u4e0e\u9762\u79ef\u4e0d\u540c\u7684\u5730\u65b9\u662f\u8fd8\u8981\u8bb0\u5f55\u7ad6\u7684\u8fb9\u6709\u51e0\u4e2a(numseg\u8bb0\u5f55),\u5e76\u4e14\u5f53\u8fb9\u754c\u91cd\u5408\u7684\u65f6\u5019\u9700\u8981\u5408\u5e76(\u7528lbd\u548crbd\u8868\u793a\u8fb9\u754c\u6765\u8f85\u52a9)<br \/>\n\u7ebf\u6bb5\u6811\u64cd\u4f5c:update:\u533a\u95f4\u589e\u51cf query:\u76f4\u63a5\u53d6\u6839\u8282\u70b9\u7684\u503c<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;cctype&gt;\r\n#include &lt;algorithm&gt;\r\nusing namespace std;\r\n#define lson l , m , rt &lt;&lt; 1\r\n#define rson m + 1 , r , rt &lt;&lt; 1 | 1\r\n \r\nconst int maxn = 22222;\r\nstruct Seg{\r\n       int l , r , h , s;\r\n       Seg() {}\r\n       Seg(int a,int b,int c,int d):l(a) , r(b) , h(c) , s(d) {}\r\n       bool operator &lt; (const Seg &amp;cmp) const {\r\n              return h &lt; cmp.h;\r\n       }\r\n}ss&#x5B;maxn];\r\nbool lbd&#x5B;maxn&lt;&lt;2] , rbd&#x5B;maxn&lt;&lt;2];\r\nint numseg&#x5B;maxn&lt;&lt;2];\r\nint cnt&#x5B;maxn&lt;&lt;2];\r\nint len&#x5B;maxn&lt;&lt;2];\r\nvoid PushUP(int rt,int l,int r) {\r\n       if (cnt&#x5B;rt]) {\r\n              lbd&#x5B;rt] = rbd&#x5B;rt] = 1;\r\n              len&#x5B;rt] = r - l + 1;\r\n              numseg&#x5B;rt] = 2;\r\n       } else if (l == r) {\r\n              len&#x5B;rt] = numseg&#x5B;rt] = lbd&#x5B;rt] = rbd&#x5B;rt] = 0;\r\n       } else {\r\n              lbd&#x5B;rt] = lbd&#x5B;rt&lt;&lt;1];\r\n              rbd&#x5B;rt] = rbd&#x5B;rt&lt;&lt;1|1];\r\n              len&#x5B;rt] = len&#x5B;rt&lt;&lt;1] + len&#x5B;rt&lt;&lt;1|1];\r\n              numseg&#x5B;rt] = numseg&#x5B;rt&lt;&lt;1] + numseg&#x5B;rt&lt;&lt;1|1];\r\n              if (lbd&#x5B;rt&lt;&lt;1|1] &amp;&amp; rbd&#x5B;rt&lt;&lt;1]) numseg&#x5B;rt] -= 2;\/\/\u4e24\u6761\u7ebf\u91cd\u5408\r\n       }\r\n}\r\nvoid update(int L,int R,int c,int l,int r,int rt) {\r\n       if (L &lt;= l &amp;&amp; r &lt;= R) {\r\n              cnt&#x5B;rt] += c;\r\n              PushUP(rt , l , r);\r\n              return ;\r\n       }\r\n       int m = (l + r) &gt;&gt; 1;\r\n       if (L &lt;= m) update(L , R , c , lson);\r\n       if (m &lt; R) update(L , R , c , rson);\r\n       PushUP(rt , l , r);\r\n}\r\nint main() {\r\n       int n;\r\n       while (~scanf(&quot;%d&quot;,&amp;n)) {\r\n              int m = 0;\r\n              int lbd = 10000, rbd = -10000;\r\n              for (int i = 0 ; i &lt; n ; i ++) {\r\n                     int a , b , c , d;\r\n                     scanf(&quot;%d%d%d%d&quot;,&amp;a,&amp;b,&amp;c,&amp;d);\r\n                     lbd = min(lbd , a);\r\n                     rbd = max(rbd , c);\r\n                     ss&#x5B;m++] = Seg(a , c , b , 1);\r\n                     ss&#x5B;m++] = Seg(a , c , d , -1);\r\n              }\r\n              sort(ss , ss + m);\r\n              int ret = 0 , last = 0;\r\n              for (int i = 0 ; i &lt; m ; i ++) {\r\n                     if (ss&#x5B;i].l &lt; ss&#x5B;i].r) update(ss&#x5B;i].l , ss&#x5B;i].r - 1 , ss&#x5B;i].s , lbd , rbd - 1 , 1);\r\n                     ret += numseg&#x5B;1] * (ss&#x5B;i+1].h - ss&#x5B;i].h);\r\n                     ret += abs(len&#x5B;1] - last);\r\n                     last = len&#x5B;1];\r\n              }\r\n              printf(&quot;%d\\n&quot;,ret);\r\n       }\r\n       return 0;\r\n}\r\n<\/pre>\n<h3>\u7ec3\u4e60<\/h3>\n<p>hdu3265 Posters<br \/>\nhdu3642 Get The Treasury<br \/>\npoj2482 Stars in Your Window<br \/>\npoj2464 Brownie Points II<br \/>\nhdu3255 Farming<br \/>\nural1707 Hypnotoad\u2019s Secret<br \/>\nuva11983 Weird Advertisement<\/p>\n<h2>\u7ebf\u6bb5\u6811\u4e0e\u5176\u4ed6\u7ed3\u5408\u7ec3\u4e60(\u6b22\u8fce\u5927\u5bb6\u8865\u5145)<\/h2>\n<p>hdu3333 Turing Tree<br \/>\nhdu3874 Necklace<br \/>\nhdu3016 Man Down<br \/>\nhdu3340 Rain in ACStar<br \/>\nzju3511 Cake Robbery<br \/>\nUESTC1558 Charitable Exchange<br \/>\nCF85-D Sum of Medians<br \/>\nspojGSS2 Can you answer these queries II\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u6848\uff1a\u8f6c\u8f7d\u81ea http:\/\/www.cnblogs.com\/Mu-Tou\/archive\/2011\/08\/11\/2134427.html ______<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[165],"tags":[],"class_list":["post-1146","post","type-post","status-publish","format-standard","hentry","category-collection"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-iu","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1146"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1146\/revisions"}],"predecessor-version":[{"id":1147,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1146\/revisions\/1147"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}