http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3225<\/a><\/p>\n\u7b80\u5355\u5730\u8bf4\uff0c\u8fd9\u9053\u9898\u8981\u6c42\u662f\u5df2\u77e5<\/p>\n
A \u222a B\t={x : x \u2208 A or x \u2208 B}
\nA \u2229 B\t ={x : x \u2208 A and x \u2208 B}
\nA \u2212 B ={x : x \u2208 A but x \u2209 B}
\nA \u2295 B = (A \u2212 B) \u222a (B \u2212 A)<\/p>\n
\u7136\u540e\u7ed9\u4f60\u4e00\u4e2a\u7a7a\u96c6S\uff0c\u548c\u4e00\u7cfb\u5217\u64cd\u4f5c\uff08\u64cd\u4f5c\u6570\u5c0f\u4e8e\u7b49\u4e8e65535\uff09\uff1a<\/p>\n
U T :\tS \u2190 S \u222a T
\nI T\t: S \u2190 S \u2229 T
\nD T :\tS \u2190 S \u2212 T
\nC T :\u00a0\tS \u2190 T \u2212 S
\nS T\t: S \u2190 S \u2295 T<\/p>\n
\u5176\u4e2dT\u662f\u7aef\u70b9\u662f0\u523065535\u7684\u533a\u95f4\uff08\u53ef\u5f00\u53ef\u95ed\u53ef\u534a\u5f00\u534a\u95ed\uff09\u3002<\/p>\n
\u7136\u540e\u8981\u4f60\u6253\u5370\u6240\u6709\u64cd\u4f5c\u540e\u7684S\u96c6\u5408\u3002<\/p>\n
\u57fa\u672c\u601d\u8def<\/h3>\n
\u5bf9\u4e8e\u5f00\u95ed\u533a\u95f4\u7684\u65ad\u70b9\u95ee\u9898\uff0c\u6211\u4eec\u53ea\u8981\u91cd\u65b0\u7f16\u53f7\u5c31\u53ef\u4ee5\u4e86\u3002[0,0]=>0; (0,1)=>1; [1,1]=>2; (1,2)=>3\uff0c\u4f9d\u6b64\u7c7b\u63a8\u3002<\/p>\n
\u8fd9\u9053\u9898\u4e00\u62ff\u5230\u5c31\u6709\u4e00\u4e2a\u66b4\u529b\u523701\u6570\u7ec4\u7684\u51b2\u52a8\uff081\u8868\u793a\u8fd9\u4e2a\u5c5e\u4e8eS, 0\u4e0d\u5c5e\u4e8e\uff09\u3002\u53ef\u662f\u6570\u636e\u8303\u56f4\u8981\u6c42\u5feb\u901f\u4fee\u6539\u7684\u64cd\u4f5c\uff08\u5bf9\u67e5\u8be2\u7684\u8981\u6c42\u4e0d\u9ad8\uff09\uff0c\u4e8e\u662f\u6211\u4eec\u81ea\u7136\u800c\u7136\u60f3\u5230\u7ebf\u6bb5\u6811( segtree)\u3002<\/p>\n
\u7531USACO\u7684Elite 2008 November Competition\u7684Cowxor\u7684\u542f\u53d1\uff0c\u6211\u53d1\u73b0\u53ea\u89812\u4e2a\u64cd\u4f5c\u5c31\u53ef\u4ee5\u8986\u76d6\u9898\u76ee\u8981\u6c42\u76845\u4e2a\u64cd\u4f5c\u3002<\/p>\n
cover(a,b,c)\u662f\u628aa\u5230b\u6d82\u6210c\u3002\u7136\u540echange(a,b)\u8868\u793a\u8ba9a,b\u6bb5\u5168\u90e80,1\u53cd\u5411\u3002<\/p>\n
\u8bbeT\u96c6\u5408\u7f16\u53f7\u540e\u5de6\u53f3\u7aef\u70b9\u5206\u522b\u662fl,r, \u5219\u64cd\u4f5c\u6709\u5982\u4e0b\u7b49\u4ef7\u5173\u7cfb<\/p>\n
U T :\tcover(l,r,1)
\nI T\t: cover(0,l-1,0);cover(r+1,maxn,0)
\nD T : cover(l,r,0)
\nC T :\u00a0 change(0,maxn);cover(0,l-1,0);cover(r+1,maxn,0)
\nS T\t: change(l,r)<\/p>\n
\u4e00\u4e2a\u7ebf\u6bb5\u68112\u4e2a\u53c2\u6570\uff0cst\u548cch\u3002st\u662f\u7ebf\u6bb5\u7684\u989c\u8272\uff0c-1\u8868\u793a\u989c\u8272\u53d8\u5316\u3002ch\u8868\u793a\u8be5\u7ebf\u6bb5\u989c\u8272\u6709\u6ca1\u6709\u6574\u6bb5\u53cd\u8f6c\uff0c\u5982\u679c[0,2)\u548c[0,1)\u90fd\u6709\u53cd\u8f6c\uff0c\u5219\u5b9e\u9645\u989c\u8272\u53cd\u8f6c2\u6b21\u30022\u8868\u793a\u4e0b\u9762\u7684\u53cd\u8f6c\u90fd\u4f5c\u5e9f\u3002<\/p>\n
\u6709\u4e86\u4e24\u4e2a\u53c2\u6570\uff0ccover\u3001change\u548cana(lysis)\u64cd\u4f5c\u5c31\u4e0d\u90a3\u4e48\u5b9e\u73b0\u4e86\u3002\u4f46\u662f\u8868\u793a\u65b9\u6cd5\u7684\u63a2\u7a76\u8fc7\u7a0b\u8fd8\u662f\u8981\u81ea\u5df1\u7422\u78e8\u7684\u3002\u8981\u540c\u65f6\u517c\u987e\u4e24\u4e2a\u64cd\u4f5c\u7684\u5b9e\u73b0\u96be\u5ea6\u3002<\/p>\n
\u7a0b\u5e8f:<\/h3>\nconst\nconst\n pn='p3225';\n maxn=65535 shl 1;\/\/\u7f16\u53f7\u540e\u7684\u8303\u56f4\u662f0..maxn\n\ntype\n segtree=array[1..(maxn+1) shl 2]of longint;\n\nvar\n s:string;\n op:char;\n i,j,l,r:longint;\n st,ch:segtree;\n sol:array[0..maxn+1]of longint;\/\/\u6700\u540e\u6574\u7406\u5f97\u5230\u768401\u6570\u7ec4\n\nfunction code(x:string):longint;var ret,t:longint;c:char;begin\/\/\u7f16\u7801\n if x[1]in['[','(']then begin\n c:=x[1];\n delete(x,1,1);\n val(x,ret,t);\n ret:=ret shl 1+ord(c='(');\n end else begin\n c:=x[length(x)];\n delete(x,length(x),1);\n val(x,ret,t);\n ret:=ret shl 1-ord(c=')');\n end;\n exit(ret);\nend;\n\nfunction decode_l(x:longint):string;begin\/\/\u89e3\u7801\u5230\u5de6\u7aef\u70b9\n str(x shr 1,decode_l);\n if odd(x)then\n insert('(',decode_l,1)\n else\n insert('[',decode_l,1)\nend;\n\nfunction decode_r(x:longint):string;begin\/\/\u89e3\u7801\u5230\u53f3\u7aef\u70b9\n str((x+1)shr 1,decode_r);\n if odd(x)then\n insert(')',decode_r,length(decode_r)+1)\n else\n insert(']',decode_r,length(decode_r)+1)\nend;\n\nprocedure cover(n,l,r,x,y,a:longint);var lc,rc,m:longint;begin\n if(x=l)and(y=r)then begin\n ch[n]:=2;\n st[n]:=a;\n end else begin\n lc:=n shl 1;\n rc:=lc+1;\n m:=(l+r)shr 1;\n if ch[n]>1 then begin\n ch[lc]:=ch[n];\n ch[rc]:=ch[n];\n ch[n]:=0;\n end else begin\n ch[lc]:=ch[lc]xor ch[n];\n ch[rc]:=ch[rc]xor ch[n];\n ch[n]:=0;\n end;\n if st[n]<>-1 then begin\n st[lc]:=st[n];\n st[rc]:=st[n];\n st[n]:=-1;\n end;\n if y<=m then begin\n cover(lc,l,m,x,y,a)\n end else begin\n if x>m then begin\n cover(rc,m+1,r,x,y,a)\n end else begin\n cover(lc,l,m,x,m,a);\n cover(rc,m+1,r,m+1,y,a);\n end;\n end;\n end;\nend;\n\nprocedure change(n,l,r,x,y:longint);var lc,rc,m:longint;begin\n m:=(l+r)shr 1;\n lc:=n shl 1;\n rc:=lc+1;\n if ch[n]>1 then begin\n if r-l>0 then begin\n ch[lc]:=2;\n ch[rc]:=2;\n end;\n ch[n]:=ch[n]and 1;\n end;\n if(x=l)and(y=r)then begin\n ch[n]:=ch[n]xor 1;\n end else begin\n if y<=m then begin\n change(lc,l,m,x,y)\n end else begin\n if x>m then begin\n change(rc,m+1,r,x,y)\n end else begin\n change(lc,l,m,x,m);\n change(rc,m+1,r,m+1,y);\n end;\n end;\n end;\nend;\n\nprocedure ana(n,l,r,a,ch1:longint);var lc,rc,m:longint;begin\/\/\u7edf\u8ba1\uff0c\u8fd8\u539f01\u6570\u7ec4(sol\u6570\u7ec4)\n if(a=-1)and(st[n]>=0)then\n a:=st[n];\n if ch1<2 then\n ch1:=ch1 xor ch[n];\n if(l=r)then begin\n sol[l]:=(ch1 xor a)and 1;\n end else begin\n lc:=n shl 1;\n rc:=lc+1;\n m:=(l+r)shr 1;\n ana(lc,l,m,a,ch1);\n ana(rc,m+1,r,a,ch1);\n end;\nend;\n\nprocedure re;begin\/\/\u6bcf\u4e00\u6b65\u7684\u8bfb\u5165\n read(op);\n readln(s);\n for i:=1 to length(st)do\n if s[i]=',' then break;\n l:=code(copy(s,2,i-2));\n r:=code(copy(s,i+1,length(st)));\nend;\n\nprocedure work;begin\/\/\u6838\u5fc3\u5de5\u4f5c\u7a0b\u5e8f\n case op of\n 'U':begin\n if l<=r then\n cover(1,0,maxn,l,r,1);\n end;\n 'I':begin\n if l>0 then\n cover(1,0,maxn,0,l-1,0);\n if r0 then\n cover(1,0,maxn,0,l-1,0);\n if r\n","protected":false},"excerpt":{"rendered":"\u8fd9\u9053\u9898\u5728\u4e0a\u6d77\u5361\u4e863\u5929\u3002 \u5176\u5b9e\u4e00\u4e2a\u539f\u56e0\u662f\u53bb\u505a\u7259\u9f7f\uff0c\u611f\u60c5\u6ce2\u52a8\u7b49\u6d6a\u8d39\u5f88\u591a\u65f6\u95f4\u3002\u7136\u540e\u6628\u5929\u6574\u5929\u5148\u53bb\u4e66\u57ce\u4e70\u4e66\u4e70\u789f\uff0c\u53c8\u53bb\u535a\u7269 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14],"tags":[131,344],"class_list":["post-342","post","type-post","status-publish","format-standard","hentry","category-14","tag-131","tag-344"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/342","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=342"}],"version-history":[{"count":0,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/342\/revisions"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}