学步园

接近5k的代码啊，手都打断了

#include <iostream><br /> #include <algorithm><br /> using namespace std;</p> <p>#define maxn 100003</p> <p>struct NODE {<br /> int l,r,mid,len;<br /> int count0,max0,left0,right0;//0的个数,连续0的最大值，左边连续0的个数，右边连续0的个数<br /> int count1,max1,left1,right1;//1的个数...<br /> bool fill0,fill1,chg;//注意置0和置1，翻转不同<br /> };<br /> NODE tree[maxn*3];<br /> int n,m;<br /> int pa[maxn];</p> <p>void fill0(int i)//将某一段置0<br /> {<br /> int lt=i<<1,rt=i<<1|1;<br /> tree[i].count0=tree[i].max0=tree[i].left0=tree[i].right0=tree[i].len;<br /> tree[i].count1=tree[i].max1=tree[i].left1=tree[i].right1=0;<br /> tree[i].fill0=0;<br /> if(tree[i].l+1==tree[i].r)<br /> return;<br /> tree[lt].fill0=tree[rt].fill0=1;<br /> tree[lt].fill1=tree[rt].fill1=0;<br /> tree[lt].chg=tree[rt].chg=0;<br /> }<br /> void fill1(int i)//将某一段置1<br /> {<br /> int lt=i<<1,rt=i<<1|1;<br /> tree[i].count0=tree[i].max0=tree[i].left0=tree[i].right0=0;<br /> tree[i].count1=tree[i].max1=tree[i].left1=tree[i].right1=tree[i].len;<br /> tree[i].fill1=0;<br /> if(tree[i].l+1==tree[i].r)<br /> return ;<br /> tree[lt].fill1=tree[rt].fill1=1;<br /> tree[lt].fill0=tree[rt].fill0=0;<br /> tree[lt].chg=tree[rt].chg=0;<br /> }<br /> void chg(int i)<br /> {<br /> int lt=i<<1,rt=i<<1|1;<br /> swap(tree[i].count0,tree[i].count1);<br /> swap(tree[i].max1,tree[i].max0);<br /> swap(tree[i].left0,tree[i].left1);<br /> swap(tree[i].right0,tree[i].right1);<br /> tree[i].chg=0;<br /> if(tree[i].l+1==tree[i].r)<br /> return;<br /> tree[lt].chg^=1;<br /> tree[rt].chg^=1;<br /> }<br /> void updata(int i)//更新当前段<br /> {<br /> int lt=i<<1,rt=i<<1|1;<br /> tree[i].count0=tree[lt].count0+tree[rt].count0;<br /> tree[i].count1=tree[rt].count1+tree[lt].count1;</p> <p> tree[i].max0=max(tree[lt].max0,tree[rt].max0);<br /> tree[i].max0=max(tree[i].max0,tree[lt].right0+tree[rt].left0);</p> <p> tree[i].left0=tree[lt].left0;<br /> tree[i].right0=tree[rt].right0;</p> <p> if(tree[lt].left0==tree[lt].len)<br /> tree[i].left0+=tree[rt].left0;</p> <p> if(tree[rt].right0==tree[rt].len)<br /> tree[i].right0+=tree[lt].right0;</p> <p> tree[i].max1 = max(tree[lt].max1,tree[rt].max1);<br /> tree[i].max1 = max(tree[i].max1,tree[lt].right1+tree[rt].left1);</p> <p> tree[i].left1=tree[lt].left1;<br /> tree[i].right1=tree[rt].right1;</p> <p> if(tree[lt].left1 == tree[lt].len)<br /> tree[i].left1 += tree[rt].left1;<br /> if(tree[rt].right1 == tree[rt].len)<br /> tree[i].right1 += tree[lt].right1;<br /> }<br /> void down(int i)// 向下传递<br /> {<br /> if(tree[i].fill0)fill0(i);<br /> if(tree[i].fill1)fill1(i);<br /> if(tree[i].chg)chg(i);//这样可以减少修改的次数啊<br /> }<br /> void make(int l,int r,int i)<br /> {<br /> tree[i].l=l;<br /> tree[i].r=r;<br /> tree[i].mid=(l+r)/2;<br /> tree[i].len=r-l;<br /> tree[i].fill0=tree[i].fill1=tree[i].chg=0;<br /> if(l+1==r)<br /> {<br /> tree[i].count0=tree[i].max0=tree[i].left0=tree[i].right0=0;<br /> tree[i].count1=tree[i].max1=tree[i].left1=tree[i].right1=0;<br /> if(pa[l])<br /> tree[i].count1=tree[i].max1=tree[i].left1=tree[i].right1=1;<br /> else tree[i].count0=tree[i].max0=tree[i].left0=tree[i].right0=1;<br /> return;<br /> }<br /> make(l,tree[i].mid,i<<1);<br /> make(tree[i].mid,r,i<<1|1);<br /> updata(i);<br /> }<br /> void oper(int a,int b,int i,int op)<br /> {<br /> down(i);<br /> if(tree[i].l==a&&tree[i].r == b)<br /> {<br /> switch(op)<br /> {<br /> case 0:tree[i].fill0=1;break;<br /> case 1:tree[i].fill1=1;break;<br /> case 2:tree[i].chg^=1;break;<br /> }<br /> down(i);<br /> return ;<br /> }<br /> if(b <= tree[i].mid )<br /> oper(a,b,i<<1,op);<br /> else if(a>=tree[i].mid)<br /> oper(a,b,i<<1|1,op);<br /> else<br /> {<br /> oper(a,tree[i].mid,i<<1,op);<br /> oper(tree[i].mid,b,i<<1|1,op);<br /> }<br /> down(i<<1);<br /> down(i<<1|1);<br /> updata(i);<br /> }<br /> int ones(int a,int b,int i)<br /> {<br /> down(i);<br /> if(a == tree[i].l&& b == tree[i].r)<br /> return tree[i].count1;</p> <p> if(b<=tree[i].mid)<br /> return ones(a,b,i<<1);<br /> else if(a>=tree[i].mid)<br /> return ones(a,b,i<<1|1);<br /> else return ones(a,tree[i].mid,i<<1)+ones(tree[i].mid,b,i<<1|1);<br /> }<br /> int ConOne(int a,int b,int i)//求连续1的个数<br /> {<br /> down(i);<br /> if(a == tree[i].l && b == tree[i].r)<br /> return tree[i].max1;</p> <p> if(b <= tree[i].mid)<br /> return ConOne(a,b,2*i);<br /> else if(a >= tree[i].mid)<br /> return ConOne(a,b,2*i+1);<br /> else<br /> {<br /> int m1,m2,res;<br /> m1 = ConOne(a,tree[i].mid,2*i);<br /> m2 = ConOne(tree[i].mid,b,2*i+1);<br /> res = min(tree[2*i].right1,tree[i].mid-a)+min(tree[2*i+1].left1,b-tree[i].mid);//注意这里<br /> return max(res,max(m1,m2));<br /> }<br /> }<br /> int main()<br /> {<br /> int Case;<br /> scanf("%d",&Case);<br /> while(Case--)<br /> {<br /> scanf("%d%d",&n,&m);<br /> for(int i=0;i<n;i++)<br /> scanf("%d",&pa[i]);<br /> make(0,n,1);<br /> int a,b,op;<br /> for(int i=0;i<m;i++)<br /> {<br /> scanf("%d%d%d",&op,&a,&b);<br /> if(op <= 2)<br /> oper(a,b+1,1,op);<br /> else if(op==3)<br /> {<br /> printf("%d/n",ones(a,b+1,1));<br /> }<br /> else printf("%d/n",ConOne(a,b+1,1));<br /> }<br /> }<br /> }