【HDU】3397 Sequence operation

  1 #include<cstdio>
  2 #define MAXN 100010
  3 struct node
  4 {
  5     int sum;
  6     int v0,v1;
  7     int left0,left1;
  8     int right0,right1;
  9 };
 10 node tree[MAXN<<2];
 11 int lazy[MAXN<<2],cover[MAXN<<2];
 12 inline int MAX(int x,int y)
 13 {
 14     return x>y?x:y;
 15 }
 16 inline int MIN(int x,int y)
 17 {
 18     return x>y?y:x;
 19 }
 20 inline void swap(int &x,int &y)
 21 {
 22     int temp=x;
 23     x=y;
 24     y=temp;
 25 }
 26 inline void PushUp(int mid,int L,int R,int rt)
 27 {
 28     tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
 29     tree[rt].left0=tree[rt<<1].left0;
 30     tree[rt].right0=tree[rt<<1|1].right0;
 31     tree[rt].left1=tree[rt<<1].left1;
 32     tree[rt].right1=tree[rt<<1|1].right1;
 33     if(tree[rt].left0==mid-L+1)
 34         tree[rt].left0+=tree[rt<<1|1].left0;
 35     if(tree[rt].left1==mid-L+1)
 36         tree[rt].left1+=tree[rt<<1|1].left1;
 37     if(tree[rt].right0==R-mid)
 38         tree[rt].right0+=tree[rt<<1].right0;
 39     if(tree[rt].right1==R-mid)
 40         tree[rt].right1+=tree[rt<<1].right1;
 41     tree[rt].v0=MAX(tree[rt<<1].v0,tree[rt<<1|1].v0);
 42     tree[rt].v0=MAX(tree[rt].v0,tree[rt<<1].right0+tree[rt<<1|1].left0);
 43     tree[rt].v1=MAX(tree[rt<<1].v1,tree[rt<<1|1].v1);
 44     tree[rt].v1=MAX(tree[rt].v1,tree[rt<<1].right1+tree[rt<<1|1].left1);
 45 }
 46 inline void FXOR(int L,int R,int rt)
 47 {
 48     if(cover[rt]!=-1)
 49     {
 50         cover[rt]^=1;
 51         tree[rt].left1=tree[rt].right1=tree[rt].v1=tree[rt].sum=(R-L+1)*cover[rt];
 52         tree[rt].left0=tree[rt].right0=tree[rt].v0=(R-L+1)*(cover[rt]^1);
 53     }
 54     else
 55     {
 56         lazy[rt]^=1;
 57         tree[rt].sum=R-L+1-tree[rt].sum;
 58         swap(tree[rt].left0,tree[rt].left1);
 59         swap(tree[rt].right0,tree[rt].right1);
 60         swap(tree[rt].v0,tree[rt].v1);
 61     }
 62 }
 63 inline void PushDown(int mid,int L,int R,int rt)
 64 {
 65     if(cover[rt]!=-1)
 66     {
 67         cover[rt<<1]=cover[rt<<1|1]=cover[rt];
 68         lazy[rt<<1]=lazy[rt<<1|1]=0;
 69         tree[rt<<1].left1=tree[rt<<1].right1=tree[rt<<1].v1=tree[rt<<1].sum=(mid-L+1)*cover[rt];
 70         tree[rt<<1|1].left1=tree[rt<<1|1].right1=tree[rt<<1|1].v1=tree[rt<<1|1].sum=(R-mid)*cover[rt];
 71         tree[rt<<1].left0=tree[rt<<1].right0=tree[rt<<1].v0=(mid-L+1)*(cover[rt]^1);
 72         tree[rt<<1|1].left0=tree[rt<<1|1].right0=tree[rt<<1|1].v0=(R-mid)*(cover[rt]^1);
 73         cover[rt]=-1;
 74     }
 75     if(lazy[rt])
 76     {
 77         FXOR(L,mid,rt<<1);
 78         FXOR(mid+1,R,rt<<1|1);
 79         lazy[rt]=0;
 80     }
 81 }
 82 void Build(int L,int R,int rt)
 83 {
 84     cover[rt]=-1;
 85     lazy[rt]=0;
 86     if(L==R)
 87     {
 88         scanf("%d",&tree[rt].sum);
 89         tree[rt].v1=tree[rt].left1=tree[rt].right1=tree[rt].sum;
 90         tree[rt].v0=tree[rt].left0=tree[rt].right0=tree[rt].sum^1;
 91     }
 92     else
 93     {
 94         int mid=(L+R)>>1;
 95         Build(L,mid,rt<<1);
 96         Build(mid+1,R,rt<<1|1);
 97         PushUp(mid,L,R,rt);
 98     }
 99 }
100 void Update(int x,int y,int val,int L,int R,int rt)
101 {
102     if(x<=L&&R<=y)
103     {
104         cover[rt]=val;
105         lazy[rt]=0;
106         tree[rt].left1=tree[rt].right1=tree[rt].v1=tree[rt].sum=(R-L+1)*val;
107         tree[rt].left0=tree[rt].right0=tree[rt].v0=(R-L+1)*(val^1);
108     }
109     else
110     {
111         int mid=(L+R)>>1;
112         PushDown(mid,L,R,rt);
113         if(x<=mid)
114             Update(x,y,val,L,mid,rt<<1);
115         if(y>mid)
116             Update(x,y,val,mid+1,R,rt<<1|1);
117         PushUp(mid,L,R,rt);
118     }
119 }
120 void Change(int x,int y,int L,int R,int rt)
121 {
122     if(x<=L&&R<=y)
123         FXOR(L,R,rt);
124     else
125     {
126         int mid=(L+R)>>1;
127         PushDown(mid,L,R,rt);
128         if(x<=mid)
129             Change(x,y,L,mid,rt<<1);
130         if(y>mid)
131             Change(x,y,mid+1,R,rt<<1|1);
132         PushUp(mid,L,R,rt);
133     }
134 }
135 int Sum(int x,int y,int L,int R,int rt)
136 {
137     if(x<=L&&R<=y)
138         return tree[rt].sum;
139     int mid=(L+R)>>1,ans=0;
140     PushDown(mid,L,R,rt);
141     if(x<=mid)
142         ans+=Sum(x,y,L,mid,rt<<1);
143     if(y>mid)
144         ans+=Sum(x,y,mid+1,R,rt<<1|1);
145     return ans;
146 }
147 int Query(int x,int y,int L,int R,int rt)
148 {
149     if(x<=L&&R<=y)
150         return tree[rt].v1;
151     int temp,ans,mid=(L+R)>>1;
152     ans=0;
153     PushDown(mid,L,R,rt);
154     if(x<=mid)
155         ans=MAX(ans,Query(x,y,L,mid,rt<<1));
156     if(y>mid)
157         ans=MAX(ans,Query(x,y,mid+1,R,rt<<1|1));
158     temp=MIN(y-mid,tree[rt<<1|1].left1)+MIN(mid-x+1,tree[rt<<1].right1);
159     return MAX(ans,temp);
160 }
161 int main()
162 {
163     int c,n,m,type,x,y;
164     scanf("%d",&c);
165     while(c--)
166     {
167         scanf("%d%d",&n,&m);
168         Build(1,n,1);
169         while(m--)
170         {
171             scanf("%d%d%d",&type,&x,&y);
172             x++;
173             y++;
174             if(type==0)
175                 Update(x,y,0,1,n,1);
176             else if(type==1)
177                 Update(x,y,1,1,n,1);
178             else if(type==2)
179                 Change(x,y,1,n,1);
180             else if(type==3)
181                 printf("%d\n",Sum(x,y,1,n,1));
182             else
183                 printf("%d\n",Query(x,y,1,n,1));
184         }
185     }
186     return 0;
187 }
新博客：www.zhixiangli.com