<\/span><\/h2>\nTime Limit:\u00a010 Sec\u00a0\u00a0Memory Limit:\u00a064 MB<\/span><\/center><\/p>\n<\/span>Description<\/span><\/h2>\nlxhgww\u6700\u8fd1\u6536\u5230\u4e86\u4e00\u4e2a01\u5e8f\u5217\uff0c\u5e8f\u5217\u91cc\u9762\u5305\u542b\u4e86n\u4e2a\u6570\uff0c\u8fd9\u4e9b\u6570\u8981\u4e48\u662f0\uff0c\u8981\u4e48\u662f1\uff0c\u73b0\u5728\u5bf9\u4e8e\u8fd9\u4e2a\u5e8f\u5217\u6709\u4e94\u79cd\u53d8\u6362\u64cd\u4f5c\u548c\u8be2\u95ee\u64cd\u4f5c\uff1a<\/div>\n
\u3000\u3000 0 a b \u628a[a, b]\u533a\u95f4\u5185\u7684\u6240\u6709\u6570\u5168\u53d8\u62100\uff1b<\/div>\n
\u3000\u30001 a b \u628a[a, b]\u533a\u95f4\u5185\u7684\u6240\u6709\u6570\u5168\u53d8\u62101\uff1b<\/div>\n
\u3000\u30002 a b \u628a[a,b]\u533a\u95f4\u5185\u7684\u6240\u6709\u6570\u5168\u90e8\u53d6\u53cd\uff0c\u4e5f\u5c31\u662f\u8bf4\u628a\u6240\u6709\u76840\u53d8\u62101\uff0c\u628a\u6240\u6709\u76841\u53d8\u62100\uff1b<\/div>\n
\u3000\u30003 a b \u8be2\u95ee[a, b]\u533a\u95f4\u5185\u603b\u5171\u6709\u591a\u5c11\u4e2a1\uff1b<\/div>\n
\u3000\u30004 a b \u8be2\u95ee[a, b]\u533a\u95f4\u5185\u6700\u591a\u6709\u591a\u5c11\u4e2a\u8fde\u7eed\u76841\u3002<\/div>\n
\u5bf9\u4e8e\u6bcf\u4e00\u79cd\u8be2\u95ee\u64cd\u4f5c\uff0clxhgww\u90fd\u9700\u8981\u7ed9\u51fa\u56de\u7b54\uff0c\u806a\u660e\u7684\u7a0b\u5e8f\u5458\u4eec\uff0c\u4f60\u4eec\u80fd\u5e2e\u52a9\u4ed6\u5417\uff1f<\/div>\n
<\/span>Input<\/span><\/h2>\n\u8f93\u5165\u6570\u636e\u7b2c\u4e00\u884c\u5305\u62ec2\u4e2a\u6570\uff0cn\u548cm\uff0c\u5206\u522b\u8868\u793a\u5e8f\u5217\u7684\u957f\u5ea6\u548c\u64cd\u4f5c\u6570\u76ee \u7b2c\u4e8c\u884c\u5305\u62ecn\u4e2a\u6570\uff0c\u8868\u793a\u5e8f\u5217\u7684\u521d\u59cb\u72b6\u6001 \u63a5\u4e0b\u6765m\u884c\uff0c\u6bcf\u884c3\u4e2a\u6570\uff0cop, a, b\uff0c\uff080<=op<=4\uff0c0<=a<=b<n\uff09\u8868\u793a\u5bf9\u4e8e\u533a\u95f4[a, b]\u6267\u884c\u6807\u53f7\u4e3aop\u7684\u64cd\u4f5c\u3002<\/p>\n
<\/span>Output<\/span><\/h2>\n\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8be2\u95ee\u64cd\u4f5c\uff0c\u8f93\u51fa\u4e00\u884c\uff0c\u5305\u62ec1\u4e2a\u6570\uff0c\u8868\u793a\u5176\u5bf9\u5e94\u7684\u7b54\u6848<\/div>\n
<\/span>Sample Input<\/span><\/h2>\n10 10
\n0 0 0 1 1 0 1 0 1 1
\n1 0 2
\n3 0 5
\n2 2 2
\n4 0 4
\n0 3 6
\n2 3 7
\n4 2 8
\n1 0 5
\n0 5 6
\n3 3 9
\n<\/span><\/div>\n<\/span>Sample Output<\/span><\/h2>\n5
\n2
\n6
\n5<\/p>\n<\/span><\/div>\n
<\/span>HINT<\/span><\/h2>\n\n
\u5bf9\u4e8e30%\u7684\u6570\u636e\uff0c1<=n, m<=1000
\n\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c1<=n, m<=100000<\/p>\n<\/div>\n
<\/span>Source<\/span><\/h2>\n<\/span>\u7ebf\u6bb5\u6811\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u533a\u95f4\u9700\u8981\u5206\u522b\u7ef4\u62a4\u5de6\u53f3\u548c\u4e2d\u95f4\u76841\u548c0\u8fde\u7eed\u4e2a\u6570\uff0c\u5e76\u5728op=4\u65f6\u7279\u6b8a\u5904\u7406\u4e00\u4e0b\u3002<\/span><\/h4>\n<\/div>\n#include<cstdio>\r\n#define M 100010\r\ninline int max(int a,int b){return a>b?a:b;}\r\nstruct tree{int l,r,s,lazy,sum,ml1,mr1,mm1,ml0,mr0,mm0;}tr[M*6];\r\nint a[M],n,m,x,y,v,op;\r\ninline int read()\r\n{\r\n int tmp=0;\r\n char ch=getchar();\r\n while(ch<'0'||ch>'9') ch=getchar();\r\n while(ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0';ch=getchar();}\r\n return tmp;\r\n}\r\ninline void pu(int p)\r\n{\r\n int p1=p<<1,p2=p<<1|1;\r\n tr[p].sum=tr[p1].sum+tr[p2].sum;\r\n tr[p].mm1=tr[p1].mr1+tr[p2].ml1;\r\n tr[p].mm0=tr[p1].mr0+tr[p2].ml0;\r\n if(tr[p1].mr1==tr[p1].s) tr[p].ml1=tr[p1].mr1+tr[p2].ml1;\r\n else tr[p].ml1=tr[p1].ml1;\r\n if(tr[p1].mr0==tr[p1].s) tr[p].ml0=tr[p1].mr0+tr[p2].ml0;\r\n else tr[p].ml0=tr[p1].ml0;\r\n if(tr[p2].mr1==tr[p2].s) tr[p].mr1=tr[p2].mr1+tr[p1].mr1;\r\n else tr[p].mr1=tr[p2].mr1;\r\n if(tr[p2].mr0==tr[p2].s) tr[p].mr0=tr[p2].mr0+tr[p1].mr0;\r\n else tr[p].mr0=tr[p2].mr0;\r\n tr[p].mm1=max(tr[p].mm1,max(tr[p1].mm1,tr[p2].mm1));\r\n tr[p].mm0=max(tr[p].mm0,max(tr[p1].mm0,tr[p2].mm0)); \r\n}\r\ninline void change(int p)\r\n{\r\n int t1=tr[p].ml0,t2=tr[p].mr0,t3=tr[p].mm0;\r\n tr[p].ml0=tr[p].ml1;\r\n tr[p].ml1=t1;\r\n tr[p].mr0=tr[p].mr1;\r\n tr[p].mr1=t2;\r\n tr[p].mm0=tr[p].mm1;\r\n tr[p].mm1=t3;\r\n}\r\ninline void make(int l,int r,int p)\r\n{\r\n tr[p].l=l,tr[p].r=r,tr[p].s=tr[p].r-tr[p].l+1,tr[p].lazy=-1;\r\n if(l==r)\r\n {\r\n tr[p].sum=a[l];\r\n tr[p].ml1=tr[p].mm1=tr[p].mr1=a[l];\r\n tr[p].ml0=tr[p].mm0=tr[p].mr0=a[l]^1;\r\n return;\r\n }\r\n int mid=(l+r)>>1;\r\n make(l,mid,p<<1);\r\n make(mid+1,r,p<<1|1);\r\n pu(p);\r\n}\r\ninline void pd(int p)\r\n{\r\n int lz=tr[p].lazy,p1=p<<1,p2=p<<1|1;\r\n if(lz==0)\r\n {\r\n tr[p1].lazy=tr[p2].lazy=0;\r\n tr[p1].sum=0;\r\n tr[p2].sum=0;\r\n tr[p1].ml1=tr[p1].mr1=tr[p1].mm1=0;\r\n tr[p2].ml1=tr[p2].mr1=tr[p2].mm1=0;\r\n tr[p1].ml0=tr[p1].mr0=tr[p1].mm0=tr[p1].s;\r\n tr[p2].ml0=tr[p2].mr0=tr[p2].mm0=tr[p2].s;\r\n }\r\n else if(lz==1)\r\n {\r\n tr[p1].lazy=tr[p2].lazy=1;\r\n tr[p1].sum=tr[p1].s;\r\n tr[p2].sum=tr[p2].s;\r\n tr[p1].ml1=tr[p1].mr1=tr[p1].mm1=tr[p1].s;\r\n tr[p2].ml1=tr[p2].mr1=tr[p2].mm1=tr[p2].s;\r\n tr[p1].ml0=tr[p1].mr0=tr[p1].mm0=0;\r\n tr[p2].ml0=tr[p2].mr0=tr[p2].mm0=0;\r\n }\r\n else if(lz==2)\r\n {\r\n if(tr[p1].lazy==1) tr[p1].lazy=0;\r\n else if(tr[p1].lazy==0) tr[p1].lazy=1;\r\n else if(tr[p1].lazy==2) tr[p1].lazy=-1;\r\n else tr[p1].lazy=2;\r\n if(tr[p2].lazy==1) tr[p2].lazy=0;\r\n else if(tr[p2].lazy==0) tr[p2].lazy=1;\r\n else if(tr[p2].lazy==2) tr[p2].lazy=-1;\r\n else tr[p2].lazy=2;\r\n tr[p1].sum=tr[p1].s-tr[p1].sum;\r\n tr[p2].sum=tr[p2].s-tr[p2].sum;\r\n change(p1);change(p2);\r\n }\r\n tr[p].lazy=-1;\r\n}\r\ninline int find1(int l,int r,int p)\r\n{\r\n pd(p);\r\n if(tr[p].l==l&&tr[p].r==r) return tr[p].sum;\r\n int mid=(tr[p].l+tr[p].r)>>1;\r\n if(mid>=r) return find1(l,r,p<<1);\r\n else if(mid<l) return find1(l,r,p<<1|1);\r\n else return find1(l,mid,p<<1)+find1(mid+1,r,p<<1|1);\r\n}\r\ninline int findl(int l,int r,int p)\r\n{\r\n pd(p);\r\n if(tr[p].ml1+l>r) return r-l+1;\r\n else return tr[p].ml1;\r\n}\r\ninline int findr(int l,int r,int p)\r\n{\r\n pd(p);\r\n if(l+tr[p].mr1>r) return r-l+1;\r\n else return tr[p].mr1;\r\n}\r\ninline int find2(int l,int r,int p)\r\n{\r\n pd(p);\r\n if(tr[p].l==l&&tr[p].r==r) return max(tr[p].ml1,max(tr[p].mm1,tr[p].mr1));\r\n int mid=(tr[p].l+tr[p].r)>>1;\r\n if(mid>=r) return find2(l,r,p<<1);\r\n else if(mid<l) return find2(l,r,p<<1|1);\r\n else return max(max(find2(l,mid,p<<1),find2(mid+1,r,p<<1|1)),findl(mid+1,r,p<<1|1)+findr(l,mid,p<<1));\r\n}\r\ninline void xg(int l,int r,int c,int p)\r\n{\r\n pd(p);\r\n if(tr[p].l==l&&tr[p].r==r)\r\n {\r\n tr[p].lazy=c;\r\n if(c==0)\r\n {\r\n tr[p].ml1=tr[p].mr1=tr[p].mm1=0;\r\n tr[p].ml0=tr[p].mr0=tr[p].mm0=tr[p].s;\r\n tr[p].sum=0;\r\n }\r\n else if(c==1)\r\n {\r\n tr[p].ml0=tr[p].mr0=tr[p].mm0=0;\r\n tr[p].ml1=tr[p].mr1=tr[p].mm1=tr[p].s;\r\n tr[p].sum=tr[p].s;\r\n }\r\n else\r\n {\r\n tr[p].sum=tr[p].s-tr[p].sum;\r\n change(p);\r\n }\r\n return;\r\n }\r\n int mid=(tr[p].l+tr[p].r)>>1;\r\n if(mid>=r) xg(l,r,c,p<<1);\r\n else if(mid<l) xg(l,r,c,p<<1|1);\r\n else \r\n {\r\n xg(l,mid,c,p<<1);\r\n xg(mid+1,r,c,p<<1|1);\r\n }\r\n pu(p);\r\n}\r\nint main()\r\n{\r\n n=read(),m=read();\r\n for(int i=1;i<=n;i++) a[i]=read();\r\n make(1,n,1);\r\n for(int i=0;i<m;i++)\r\n {\r\n op=read();x=read();y=read();\r\n if(op<3) xg(x+1,y+1,op,1);\r\n else if(op==3) printf(\"%d\\n\",find1(x+1,y+1,1));\r\n else printf(\"%d\\n\",find2(x+1,y+1,1));\r\n }\r\n return 0;\r\n}<\/pre>\n <\/p>\n
\n
<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
1858: [Scoi2010]\u5e8f\u5217\u64cd\u4f5c Time Limit:\u00a010 Sec\u00a0\u00a0Memory Limit:\u00a0 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[10],"class_list":["post-313","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-10"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/313","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=313"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/313\/revisions"}],"predecessor-version":[{"id":314,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/313\/revisions\/314"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}