{"id":452,"date":"2010-10-21T23:25:37","date_gmt":"2010-10-21T15:25:37","guid":{"rendered":"http:\/\/comzyh.tk\/blog\/?p=452"},"modified":"2015-10-24T16:50:01","modified_gmt":"2015-10-24T08:50:01","slug":"poj2777-%e7%ba%bf%e6%ae%b5%e6%a0%91%e6%9f%93%e8%89%b2","status":"publish","type":"post","link":"https:\/\/comzyh.com\/blog\/archives\/452\/","title":{"rendered":"POJ 2777 Count Color \u7ebf\u6bb5\u6811\u67d3\u8272"},"content":{"rendered":"

\u65e9\u4e9b\u65e5\u5b50\u4e3a\u4e86\u5b66\u4e60\u7ebf\u6bb5\u6811,\u5728Du\u795e\u725b\u7684\u5e26\u9886\u4e0b,\u505a\u4e86\u6b64\u9898,\u5165\u95e8\u597d\u9898\u4e5f! poj2777 Count Color<\/a><\/p>\n

\u6b64\u9898\u662f\u672c\u4eba\u7ebf\u6bb5\u6811\u7b2c\u4e8c\u9898,\u524d\u4e00\u9053\u662fTYVJ1039 \u5fe0\u8bda2<\/a>(\u4e00\u9053\u52a8\u6001RMQ\u95ee\u9898)<\/p>\n

\u8f93\u5165\u533a\u95f4\u957f\u5ea6L (1 <= L <= 100000),\u989c\u8272\u6570\u76ee T (1 <= T <= 30) \u548c \u6307\u4ee4\u6570O (1 <= O <= 100000)<\/p>\n

\u63a5\u4e0b\u6765O\u884cC x y z \u4ee3\u8868\u5c06[x,y]\u533a\u95f4\u67d3\u6210z\u8272,P x y z \u4ee3\u8868\u8be2\u95ee[x,y]\u6709\u591a\u5c11\u79cd\u989c\u8272,\u8d77\u59cb\u5404\u5904\u989c\u8272\u4e3a1;<\/p>\n

\u6211\u7b2c\u4e00\u773c\u770b\u5230”1 <= T <= 30″\u5c31\u683c\u5916\u6fc0\u52a8\u4e3a\u5565\u4e0d\u662f40\u5462\uff1f\u663e\u7136\u662f\u4e3a\u4e86\u5c0f\u4e8e32,\u6240\u4ee5\u663e\u7136\u53ef\u4ee5\u7528\u4e8c\u8fdb\u5236\u6bcf\u4f4d\u8868\u8fbe\u4e00\u79cd\u989c\u8272,\u989c\u82721\u662f1(0x1)\u989c\u827210\u5c31\u662f1024(0x400),\u5728\u7ebf\u6bb5\u6811\u91cc\u67e5\u8be2\u4fbf\u53ef\u4ee5\u83b7\u5f97\u8fd9\u4e00\u6bb5\u7684\u51e0\u79cd\u989c\u8272\u7136\u540e\u505a\u4e00\u6b21OR\u64cd\u4f5c\u4fbf\u53ef\u5f97\u5230\u6240\u6709\u989c\u8272<\/p>\n

\u6211\u770b\u5230T\u7684\u8303\u56f4\u5c31\u9a6c\u4e0a\u60f3\u5230\u5230\u4e86Matrix67\u725b\u7684\u4e00\u4e2a\u4f4d\u8fd0\u7b97\u4f18\u5316\uff1a\u4f4d\u8fd0\u7b97\u7b80\u4ecb\u53ca\u5b9e\u7528\u6280\u5de7\uff08\u4e8c\uff09\uff1a\u8fdb\u9636\u7bc7(1)<\/a> \u4e2d\u8ba1\u7b97\u4e8c\u8fdb\u5236\u4e2d\u76841\u7684\u4e2a\u6570<\/strong>\u7684\u65b9\u6cd5
\n<\/p>\n

\r\ninline int c1(int x){\r\n       x=(x & 0x55555555) + ((x >>1 ) & 0x55555555);\r\n       x=(x & 0x33333333) + ((x >>2 ) & 0x33333333);\r\n       x=(x & 0x0F0F0F0F) + ((x >>4 ) & 0x0F0F0F0F);\r\n       x=(x & 0x00FF00FF) + ((x >>8 ) & 0x00FF00FF);\r\n       x=(x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);   \r\n       return x;\r\n       }\r\n<\/pre>\n
\u6b64\u65b9\u6cd5\u53ef\u5feb\u901f\u7edf\u8ba1int\u578b\u4e2d1\u7684\u4e2a\u6570<\/p>\n
\u505a\u8fd9\u4e2a\u9898\u7684\u65f6\u5019\u66fe\u7ecf\u78b0\u5230\u4e2a\u68d8\u624b\u7684\u95ee\u9898,WA\u4e86\u597d\u51e0\u6b21,\u540e\u6765\u770b\u4e86Du\u795e\u725b\u7684\u9898\u89e3<\/a> ,\u53d1\u73b0\u4ee3\u7801\u51fa\u5947\u7684\u76f8\u4f3c,\u4e8e\u662f\u627e\u4e0d\u540c\u4e4b\u5904,\u8c41\u7136\u5f00\u6717.<\/p>\n
\u9519\u8bef\u7684\u4ee3\u7801\u8be6\u89c1poj2777\u91ccDiscuss\u91ccComzyh\u7684”Wa\u7684\u539f\u56e0<\/a><\/p>\n
\"Poj2777<\/a>
\u6ce8\u610f\u8fd9\u4e2a\u7ebf\u6bb5\u6811\u662f\u7528\u4e8c\u53c9\u5806\u65b9\u5f0f\u5b58\u50a8\u7684<\/figcaption><\/figure>\n
\u8fd9\u4e2a\u95ee\u9898\u7684\u7531\u6765\u662f\u8fd9\u6837\u7684,\u67b6\u8bbe\u6709\u4e00\u6bb5[1,10]\u7684\u533a\u95f4\u4e3a\u7ea2<\/span>\u8272,\u5176\u5b50\u6811\u4e3a[1,5],[6,10]\u6211\u4e48\u73b0\u5728\u8981\u5bf9[5,7]\u67d3\u6210\u84dd<\/span>\u8272,\u600e\u4e48\u505a\u5462?<\/p>\n
\u663e\u7136\u6700\u7ec8\u60c5\u51b5\u662f[1,4]<\/span>[5,7]<\/span>[7,10]<\/span><\/p>\n
\u6211\u7684\u539f\u610f\u662f\u5148\u67d3\u8272[1,4]<\/span> \u7136\u540e\u67d3\u8272[7,10]<\/span> (\u4e0b\u6c89\u64cd\u4f5c)\u7136\u540e\u67d3\u8272[5,7]<\/span><\/p>\n
\u540e\u6765\u770b\u4e86Du\u795e\u725b\u7684\u9898\u89e3,\u8c41\u7136\u5f00\u6717,\u539f\u6765\u76f4\u63a5\u5c06\u7ebf\u6bb5\u4e0b\u6c89\u5230\u4e24\u4e2a\u5b50\u8282\u70b9\u5373\u53ef,\u5373\u5148\u67d3\u8272[1,5]<\/span>,\u5728\u67d3\u8272[6,10]<\/span>,\u518d\u67d3\u8272[5,7]<\/span>,\u6211\u521a\u624d\u7684\u505a\u6cd5\u7eaf\u5c5e\u95f2\u7684,\u6211\u628a\u53f3\u8fb9\u90a3\u4e00\u6bb5[7,10]\u67d3\u6210\u5f53\u524d\u8981\u67d3\u7684\u8272\u800c\u4e0d\u662f\u5f53\u524d\u7ebf\u6bb5\u7684\u989c\u8272(\u4eca\u5929\u53c8\u8bd5\u4e86\u4e0b\u6539\u6b63\u4e86\u7684,G++688ms,C++516,\u663e\u7136\u6162).
\n\u8fd8\u662f\u628a\u9519\u8bef\u4ee3\u7801\u8d34\u4e00\u4e0b\u5427,\u7b2c23\u884cCover\u9519\u4e86.<\/p>\n
\r\nvoid cover (int b,int e,int s,int c){\r\n     \/\/printf(\"Cover from %4d to %4d in setment %4d (%4d,%4d)Colored %x\\n\",b,e,s,seg[s].b,seg[s].e,c);\r\n     segment &ts=seg[s];\r\n     if (ts.b==b && ts.e==e){\r\n        ts.cd=1;\r\n        ts.c =c;\r\n        return ;\r\n        }\r\n     int mid=(ts.b + ts.e)>>1;\r\n     if (ts.cd==1){\r\n        ts.cd=0;\r\n        if (b>ts.b)\r\n           if   (b-1<=mid)\r\n                cover(ts.b,b-1,s<<1,ts.c);\r\n           else{\r\n                cover(ts.b,mid,s<<1,ts.c);\r\n                cover(mid+1,b-1,(s<<1)+1,ts.c);\r\n                }\r\n        if (e=mid)\/\/e+1>=mid+1\r\n                cover(e+1,ts.e,(s<<1)+1,ts.c);\r\n           else {\/\/\u80fd\u770b\u5230\u5e95\u4e0b\u4e0d\u662fts.c;\u8fd9\u5c31\u662fWa\u7684\u539f\u56e0--Comzyh\u5199\u672c\u6587\u65f6\u6ce8 \r\n                cover(e+1,mid,s<<1,c);\r\n                cover(mid+1,ts.e,(s<<1)+1,c);\r\n                }\r\n        }\r\n     ts.cd=0;\r\n     if   (e <= mid)\r\n          cover(b,e,s<<1    ,c);\r\n     else if (b>mid)\/\/b>=mid+1\r\n          cover(b,e,(s<<1)+1,c);\r\n     else{\r\n          cover(b    ,mid,s<<1    ,c);\r\n          cover(mid+1,e  ,(s<<1)+1,c);\r\n          }\r\n     }\r\n<\/pre>\n
\u54ce,\u4e0b\u9762\u5e16\u4e0b\u6211\u7684G++547ms,C++438ms\u7684\u4ee3\u7801,\u521d\u5b66\u8005,\u6162\u6ca1\u6cd5,\u53e6\u5916\u4e25\u91cd\u6000\u7591poj\u7684C++\u4e3a\u4ec0\u4e48\u6bd4G++\u5feb\u8fd9\u4e48\u591a.<\/p>\n
\r\n\/*\r\nProblem: 2777\t\tUser: comzyh\r\nMemory: 4312K\t\tTime: 407MS\r\nLanguage: C++\t\tResult: Accepted\r\n*\/\r\n#include  \r\n#include \r\n#include \r\nusing namespace std;\r\n\/\/#define ts seg[s]\r\nstruct segment{\r\n       unsigned int b,e,cd;\/\/begin,end,\u8be5\u7ebf\u6bb5\u4ec5\u6709\u4e00\u79cd\u989c\u8272?;\r\n       long c;\/\/\u4e8c\u8fdb\u5236\u5b58\u50a8,\u4ecelong long \u6539\u6210 long \u5c31407ms\u4e86 \r\n       };\r\nint L,T,O;\r\nsegment seg[500000];\r\ninline int c1(int x);\r\nvoid build(int b,int e,int s);\r\nvoid cover (int b,int e,int s,int c);\r\nint  get(int b,int e,int s);\r\nint main(){\r\n    int i,j;\r\n    char t;\r\n    int b,e,c;\r\n    scanf(\"%d%d%d\",&L,&T,&O);\r\n    build(1,L,1);\r\n    for (i=1;i<=O;i++){\r\n        scanf (\"\\n%c\",&t);\r\n        if (t=='C'){\r\n           scanf (\"%d%d%d\",&b,&e,&c);\r\n           if (b>1 ) & 0x55555555);\r\n       x=(x & 0x33333333) + ((x >>2 ) & 0x33333333);\r\n       x=(x & 0x0F0F0F0F) + ((x >>4 ) & 0x0F0F0F0F);\r\n       x=(x & 0x00FF00FF) + ((x >>8 ) & 0x00FF00FF);\r\n       x=(x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);\r\n       return x;\r\n       }\r\nvoid build(int b,int e,int s){\/\/\u5efa\u6811 \r\n     \/\/printf(\"Build Tree from %4d to %4d in line %4d \\n\",b,e,s);\r\n     seg[s].b=b;\r\n     seg[s].e=e;\r\n     seg[s].c=1;\r\n     seg[s].cd=1;\r\n     if (b != e){\r\n        int mid=(b+e)>>1;\r\n        build(b    ,mid,s<<1    );\r\n        build(mid+1,e  ,(s<<1)+1);\r\n        }\r\n     }\r\nvoid cover (int b,int e,int s,int c){\/\/\u8986\u76d6,\u5f00\u59cb,\u7ed3\u675f,\u7ebf\u6bb5,\u989c\u8272 \r\n     \/\/printf(\"Cover from %4d to %4d in setment %4d (%4d,%4d)Colored %x\\n\",b,e,s,seg[s].b,seg[s].e,c);\r\n     segment &ts=seg[s];\/\/\u5f53\u524d\u7ebf\u6bb5\u7684\u5f15\u7528,\u4e0b\u540c \r\n     if (ts.b==b && ts.e==e){\r\n        ts.cd=1;\r\n        ts.c =c;\r\n        return ;\r\n        }\r\n     int mid=(ts.b + ts.e)>>1;\r\n     if (ts.cd==1){\r\n        cover(ts.b ,mid ,s<<1    ,ts.c);\r\n        cover(mid+1,ts.e,(s<<1)+1,ts.c);\r\n        }\r\n     ts.cd=0;\r\n     if   (e <= mid)\r\n          cover(b,e,s<<1    ,c);\r\n     else if (b>mid)\/\/b>=mid+1\r\n          cover(b,e,(s<<1)+1,c);\r\n     else{\r\n          cover(b    ,mid,s<<1    ,c);\r\n          cover(mid+1,e  ,(s<<1)+1,c);\r\n          }\r\n     }\r\nint  get(int b,int e,int s){\/\/\u67e5\u8be2\u989c\u8272 \r\n     \/\/printf(\"Get from %4d to %4d in segment %4d  (%4d,%4d)\\n\",b,e,s,seg[s].b,seg[s].e);\r\n     segment &ts=seg[s];\r\n     if (ts.cd==1)return ts.c;\r\n     int mid=(ts.b+ts.e)>>1;\r\n     if   (e <= mid)\r\n          return get(b,e,s<<1    );\r\n     else if (b>mid)\/\/b>=mid+1\r\n          return get(b,e,(s<<1)+1);\r\n     else{\r\n          return get(b    ,mid,s<<1    ) | \/\/\u8fd9\u91cc\u5c31\u662f\u7edf\u8ba1\u989c\u8272\u7684OR \r\n                 get(mid+1,e  ,(s<<1)+1);\r\n          }\r\n     }\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u65e9\u4e9b\u65e5\u5b50\u4e3a\u4e86\u5b66\u4e60\u7ebf\u6bb5\u6811,\u5728Du\u795e\u725b\u7684\u5e26\u9886\u4e0b,\u505a\u4e86\u6b64\u9898,\u5165\u95e8\u597d\u9898\u4e5f! poj2777 Count Color \u6b64 […]<\/p>\n","protected":false},"author":2,"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":[11,46],"tags":[45,44,18],"class_list":["post-452","post","type-post","status-publish","format-standard","hentry","category-programing","category-solution","tag-poj","tag-44","tag-18"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6XQWE-7i","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/452","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=452"}],"version-history":[{"count":3,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/452\/revisions"}],"predecessor-version":[{"id":903,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/452\/revisions\/903"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=452"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=452"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}