hdu 3397 线段树

题意： Change operations:
0 a b change all characters into '0's in [a , b]
1 a b change all characters into '1's in [a , b]
2 a b change all '0's into '1's and change all '1's into '0's in [a, b]
Output operations:
3 a b output the number of '1's in [a, b]
4 a b output the length of the longest continuous '1' string in [a , b]

Sample Input
1
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

嗯嗯

2015-07-26:专题复习

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 #define cl(a) memset(a,0,sizeof(a))
 13 #define ts printf("*****
");
 14 #define lson l,mid,rt<<1
 15 #define rson mid+1,r,rt<<1|1
 16 #define root 1,n,1
 17 #define mid ((l+r)>>1)
 18 const int MAXN=100010;
 19 int n,m,t,Min,tt;
 20 int msum1[MAXN<<2],col[MAXN<<2],lsum1[MAXN<<2],rsum1[MAXN<<2];
 21 int msum0[MAXN<<2],lsum0[MAXN<<2],rsum0[MAXN<<2],xxor[MAXN<<2];
 22 int sum1[MAXN<<2],sum0[MAXN<<2];
 23 void fun1(int rt,int m,int val)     //改变区间内0/1的变化
 24 {
 25     msum1[rt]=lsum1[rt]=rsum1[rt]=sum1[rt]=val?m:0;
 26     msum0[rt]=lsum0[rt]=rsum0[rt]=sum0[rt]=val?0:m;
 27 }
 28 void fun2(int rt)
 29 {
 30     swap(msum1[rt],msum0[rt]);
 31     swap(lsum1[rt],lsum0[rt]);
 32     swap(rsum1[rt],rsum0[rt]);
 33     swap(sum1[rt],sum0[rt]);
 34 }
 35 
 36 void pushup(int rt,int m)
 37 {
 38     sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1];
 39     lsum1[rt]=lsum1[rt<<1];
 40     rsum1[rt]=rsum1[rt<<1|1];
 41     if(lsum1[rt]==(m-(m>>1)))    lsum1[rt]+=lsum1[rt<<1|1];
 42     if(rsum1[rt]==(m>>1))    rsum1[rt]+=rsum1[rt<<1];
 43     msum1[rt]=max(lsum1[rt<<1|1]+rsum1[rt<<1],max(msum1[rt<<1],msum1[rt<<1|1]));
 44 
 45     sum0[rt]=sum0[rt<<1]+sum0[rt<<1|1];
 46     lsum0[rt]=lsum0[rt<<1];
 47     rsum0[rt]=rsum0[rt<<1|1];
 48     if(lsum0[rt]==(m-(m>>1)))    lsum0[rt]+=lsum0[rt<<1|1];
 49     if(rsum0[rt]==(m>>1))    rsum0[rt]+=rsum0[rt<<1];
 50     msum0[rt]=max(lsum0[rt<<1|1]+rsum0[rt<<1],max(msum0[rt<<1],msum0[rt<<1|1]));
 51 }
 52 void build(int l,int r,int rt)
 53 {
 54     col[rt]=-1;
 55     xxor[rt]=0;
 56     if(l==r)
 57     {
 58         int num;
 59         scanf("%d",&num);
 60         msum1[rt]=lsum1[rt]=rsum1[rt]=sum1[rt]=num?1:0;
 61         msum0[rt]=lsum0[rt]=rsum0[rt]=sum0[rt]=num?0:1;
 62         return;
 63     }
 64     build(lson);
 65     build(rson);
 66     pushup(rt,r-l+1);
 67 }
 68 void pushdown(int rt,int m)
 69 {
 70     if(col[rt]!=-1)
 71     {
 72         xxor[rt<<1]=xxor[rt<<1|1]=0;
 73         col[rt<<1]=col[rt<<1|1]=col[rt];
 74         fun1(rt<<1,m-(m>>1),col[rt]);
 75         fun1(rt<<1|1,m>>1,col[rt]);
 76         col[rt]=-1;
 77     }
 78     else if(xxor[rt])
 79     {
 80         if(col[rt<<1]!=-1)
 81         {
 82             col[rt<<1]^=1;
 83             fun1(rt<<1,m-(m>>1),col[rt<<1]);
 84         }
 85         else
 86         {
 87             xxor[rt<<1]^=1;
 88             fun2(rt<<1);                //最大连续1的变化有点麻烦，必须要重新开一个最大连续0的变量
 89         }
 90         if(col[rt<<1|1]!=-1)
 91         {
 92             col[rt<<1|1]^=1;
 93             fun1(rt<<1|1,(m>>1),col[rt<<1|1]);
 94         }
 95         else
 96         {
 97             xxor[rt<<1|1]^=1;
 98             fun2(rt<<1|1);
 99         }
100         xxor[rt]=0;
101     }
102 }
103 void update(int L,int R,int val,int l,int r,int rt)
104 {
105     if(l>=L&&r<=R)
106     {
107         if(val<=1)
108         {
109             xxor[rt]=0;
110             col[rt]=val;
111             fun1(rt,r-l+1,val);
112         }
113         else
114         {
115             if(col[rt]!=-1)
116             {
117                 col[rt]^=1;
118                 fun1(rt,r-l+1,col[rt]);
119             }
120             else
121             {
122                 xxor[rt]^=1;
123                 fun2(rt);
124             }
125         }
126         return;
127     }
128     pushdown(rt,r-l+1);
129     if(L<=mid) update(L,R,val,lson);
130     if(R>mid) update(L,R,val,rson);
131     pushup(rt,r-l+1);
132 }
133 int query1(int L,int R,int l,int r,int rt)  //查询区间内1的个数
134 {
135     if(l>=L&&r<=R)
136     {
137         return sum1[rt];
138     }
139     pushdown(rt,r-l+1);
140     int ans=0;
141     if(L<=mid) ans+=query1(L,R,lson);
142     if(R>mid) ans+=query1(L,R,rson);
143     return ans;
144 }
145 int query2(int L,int R,int l,int r,int rt)  //查询区间内最长连续1的个数
146 {
147     if(l>=L&&r<=R)
148     {
149         return msum1[rt];
150     }
151     pushdown(rt,r-l+1);
152 
153     if(R<=mid) return query2(L,R,lson);
154     if(L>mid) return query2(L,R,rson);
155     int a=query2(L,R,lson);
156     int b=query2(L,R,rson);
157     a=max(a,b);
158     b=min(mid-L+1,rsum1[rt<<1])+min(R-mid,lsum1[rt<<1|1]);
159     return max(a,b);
160 }
161 int main()
162 {
163     #ifndef ONLINE_JUDGE
164     freopen("1.in","r",stdin);
165     #endif
166     int t,n,m,op,a,b;
167     scanf("%d",&t);
168     while(t--)
169     {
170         scanf("%d%d",&n,&m);
171         build(root);
172         while(m--)
173         {
174             scanf("%d%d%d",&op,&a,&b);
175             a++,b++;
176             if(op<=2) update(a,b,op,root);
177             else
178             {
179                 if(op==3) printf("%d
",query1(a,b,root));
180                 else printf("%d
",query2(a,b,root));
181             }
182         }
183     }
184     return 0;
185 }

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int maxn = 100010;
  6 #define lson l,m,rt<<1
  7 #define rson m+1,r,rt<<1|1
  8 int num0[maxn<<2],num1[maxn<<2];
  9 int lb0[maxn<<2],lb1[maxn<<2];
 10 int rb0[maxn<<2],rb1[maxn<<2];
 11 int mx1[maxn<<2],mx0[maxn<<2];
 12 int col[maxn<<2];
 13 int xxor[maxn<<2];
 14 int num;
 15 int max(int a,int b){
 16     return a>b?a:b;
 17 }
 18 int min(int a,int b){
 19     return a<b?a:b;
 20 }
 21 void pushup(int rt,int m)
 22 {
 23     lb0[rt]=lb0[rt<<1];rb0[rt]=rb0[rt<<1|1];
 24     if(lb0[rt]==m-(m>>1)) lb0[rt]+=lb0[rt<<1|1];
 25     if(rb0[rt]==(m>>1))  rb0[rt]+=rb0[rt<<1];
 26 
 27     lb1[rt]=lb1[rt<<1];rb1[rt]=rb1[rt<<1|1];
 28     if(lb1[rt]==m-(m>>1)) lb1[rt]+=lb1[rt<<1|1];
 29     if(rb1[rt]==(m>>1))  rb1[rt]+=rb1[rt<<1];
 30 
 31     num0[rt]=num0[rt<<1]+num0[rt<<1|1];
 32     num1[rt]=num1[rt<<1]+num1[rt<<1|1];
 33 
 34     mx1[rt]=max(mx1[rt<<1],mx1[rt<<1|1]);
 35     mx1[rt]=max(mx1[rt],rb1[rt<<1]+lb1[rt<<1|1]);
 36 
 37     mx0[rt]=max(mx0[rt<<1],mx0[rt<<1|1]);
 38     mx0[rt]=max(mx0[rt],rb0[rt<<1]+lb0[rt<<1|1]);
 39 }
 40 void build(int l,int r,int rt){
 41     col[rt]=-1; xxor[rt]=0;
 42     if(l==r){
 43         scanf("%d",&num);
 44         num0[rt]=lb0[rt]=rb0[rt]=mx0[rt]=(num?0:1);
 45         num1[rt]=lb1[rt]=rb1[rt]=mx1[rt]=(num?1:0);
 46         return ;
 47     }
 48     int m=(l+r)>>1;
 49     build(lson);
 50     build(rson);
 51     pushup(rt,r-l+1);
 52 }
 53 void init(int rt,int m,int cmd){
 54    lb0[rt]=rb0[rt]=mx0[rt]=num0[rt]=m*(1-cmd);
 55    lb1[rt]=rb1[rt]=mx1[rt]=num1[rt]=m*cmd;
 56 }
 57 void change(int rt){
 58     swap(lb0[rt],lb1[rt]);
 59     swap(rb0[rt],rb1[rt]);
 60     swap(mx0[rt],mx1[rt]);
 61     swap(num0[rt],num1[rt]);
 62 }
 63 void pushdown(int rt,int m){
 64     if(col[rt]!=-1){
 65          col[rt<<1]=col[rt<<1|1]=col[rt];
 66          xxor[rt<<1]=xxor[rt<<1|1]=0;
 67          init(rt<<1,m-(m>>1),col[rt]);
 68          init(rt<<1|1,(m>>1),col[rt]);
 69          col[rt]=-1;
 70     }
 71     else if(xxor[rt]){
 72         if(col[rt<<1]!=-1){
 73             col[rt<<1]^=1;
 74             init(rt<<1,m-(m>>1),col[rt<<1]);
 75         }
 76         else {
 77             xxor[rt<<1]^=1;
 78             change(rt<<1);
 79         }
 80         if(col[rt<<1|1]!=-1){
 81             col[rt<<1|1]^=1;
 82             init(rt<<1|1,(m>>1),col[rt<<1|1]);
 83         }
 84         else {
 85             xxor[rt<<1|1]^=1;
 86             change(rt<<1|1);
 87         }
 88         xxor[rt]=0;
 89     }
 90 }
 91 void update(int L,int R,int cmd,int l,int r,int rt){
 92     if(L<=l&&r<=R){
 93         if(cmd<=1){
 94             xxor[rt]=0;//取消异或标记
 95             col[rt]=cmd;//真个区间被完全覆盖为cmd
 96             init(rt,r-l+1,cmd);
 97         }
 98         else {
 99             if(col[rt]!=-1){//被完全覆盖，全是0或者全是1，相当于取反
100                 col[rt]^=1;
101                 init(rt,r-l+1,col[rt]);
102             }
103             else {
104                 xxor[rt]^=1;
105                 change(rt);
106             }
107         }
108         return ;
109     }
110     pushdown(rt,r-l+1);
111     int m=(l+r)>>1;
112     if(L<=m) update(L,R,cmd,lson);
113     if(R>m) update(L,R,cmd,rson);
114     pushup(rt,r-l+1);
115 }
116 int query1(int L,int R,int l,int r,int rt){
117     if(L<=l&&r<=R)  return num1[rt];
118     pushdown(rt,r-l+1);
119     int m=(l+r)>>1;
120     int ans=0;
121     if(L<=m) ans+=query1(L,R,lson);
122     if(R>m) ans+=query1(L,R,rson);
123     return ans;
124 }
125 int  query2(int L,int R,int l,int r,int rt){
126     if(L<=l&&r<=R) {
127         return mx1[rt];
128     }
129     pushdown(rt,r-l+1);
130     int m=(l+r)>>1;
131     if(R<=m) return query2(L,R,lson);
132     if(L>m) return query2(L,R,rson);
133     int a=query2(L,R,lson);
134     int b=query2(L,R,rson);
135     a=a>b?a:b;
136     b=min(m-L+1,rb1[rt<<1])+min(R-m,lb1[rt<<1|1]);
137     return a>b?a:b;
138 }
139 int main(){
140     int t,n,m,op,a,b;
141     scanf("%d",&t);
142     while(t--){
143         scanf("%d%d",&n,&m);
144         build(0,n-1,1);
145         while(m--){
146             scanf("%d%d%d",&op,&a,&b);
147             if(op<=2) update(a,b,op,0,n-1,1);
148             else {
149                 if(op==3) printf("%d
",query1(a,b,0,n-1,1));
150                 else printf("%d
",query2(a,b,0,n-1,1));
151             }
152         }
153     }
154     return 0;
155 }