HDU 3397 Sequence operation

Sequence operation

Time Limit: 5000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3397
64-bit integer IO format: %I64d Java class name: Main

lxhgww got a sequence contains n characters which are all '0's or '1's.
We have five operations here:
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]

Input

T(T<=10) in the first line is the case number.
Each case has two integers in the first line: n and m (1 <= n , m <= 100000).
The next line contains n characters, '0' or '1' separated by spaces.
Then m lines are the operations:
op a b: 0 <= op <= 4 , 0 <= a <= b < n.

Output

For each output operation , output the result.

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

Source

HDOJ Monthly Contest – 2010.05.01

解题：线段树。。。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 100010;
  4 struct node {
  5     int lt,rt,cover;
  6 } tree[maxn<<2];
  7 inline void pushup(int v) {
  8     if(tree[v<<1].cover == tree[v<<1|1].cover)
  9         tree[v].cover = tree[v<<1].cover;
 10     else tree[v].cover = -1;
 11 }
 12 inline void pushdown(int v) {
 13     if(tree[v].cover >= 0) {
 14         tree[v<<1].cover = tree[v<<1|1].cover = tree[v].cover;
 15         tree[v].cover = -1;
 16     }
 17 }
 18 void build(int L,int R,int v) {
 19     tree[v].lt = L;
 20     tree[v].rt = R;
 21     if(L == R) {
 22         scanf("%d",&tree[v].cover);
 23         return;
 24     }
 25     int mid = (L + R)>>1;
 26     build(L,mid,v<<1);
 27     build(mid+1,R,v<<1|1);
 28     pushup(v);
 29 }
 30 void update(int lt,int rt,int val,int v) {
 31     if(tree[v].cover == val) return;
 32     if(lt <= tree[v].lt && rt >= tree[v].rt) {
 33         tree[v].cover = val;
 34         return;
 35     }
 36     pushdown(v);
 37     if(lt <= tree[v<<1].rt) update(lt,rt,val,v<<1);
 38     if(rt >= tree[v<<1|1].lt) update(lt,rt,val,v<<1|1);
 39     pushup(v);
 40 }
 41 void update(int lt,int rt,int v) {
 42     if(lt <= tree[v].lt && rt >= tree[v].rt && tree[v].cover >= 0) {
 43         tree[v].cover ^= 1;
 44         return;
 45     }
 46     pushdown(v);
 47     if(lt <= tree[v<<1].rt) update(lt,rt,v<<1);
 48     if(rt >= tree[v<<1|1].lt) update(lt,rt,v<<1|1);
 49     pushup(v);
 50 }
 51 int ret;
 52 void query(int lt,int rt,int v) {
 53     if(!tree[v].cover) return;
 54     if(lt <= tree[v].lt && rt >= tree[v].rt && tree[v].cover >= 0) {
 55         ret += tree[v].cover?tree[v].rt - tree[v].lt + 1:0;
 56         return;
 57     }
 58     pushdown(v);
 59     if(lt <= tree[v<<1].rt) query(lt,rt,v<<1);
 60     if(rt >= tree[v<<1|1].lt) query(lt,rt,v<<1|1);
 61     pushup(v);
 62 }
 63 void query(int lt,int rt,int &r,int &ans,int v) {
 64     if(!tree[v].cover) return;
 65     if(lt <= tree[v].lt && rt >= tree[v].rt && tree[v].cover >= 0) {
 66         if(tree[v].cover) {
 67             if(r == tree[v].lt - 1) ans += tree[v].rt - tree[v].lt + 1;
 68             else ans = tree[v].rt - tree[v].lt + 1;
 69             r = tree[v].rt;
 70             ret = max(ret,ans);
 71         }
 72         return;
 73     }
 74     pushdown(v);
 75     if(lt <= tree[v<<1].rt) query(lt,rt,r,ans,v<<1);
 76     if(rt >= tree[v<<1|1].lt) query(lt,rt,r,ans,v<<1|1);
 77     pushup(v);
 78 }
 79 int main() {
 80     int T,n,m,op,a,b;
 81     scanf("%d",&T);
 82     while(T--) {
 83         scanf("%d %d",&n,&m);
 84         build(0,n-1,1);
 85         while(m--) {
 86             scanf("%d %d %d",&op,&a,&b);
 87             switch(op) {
 88             case 0:
 89             case 1:
 90                 update(a,b,op,1);
 91                 break;
 92             case 2:
 93                 update(a,b,1);
 94                 break;
 95             case 3:
 96                 ret = 0;
 97                 query(a,b,1);
 98                 printf("%d
",ret);
 99                 break;
100             case 4:int ans = ret = 0,r = -1;
101                 query(a,b,r,ans,1);
102                 printf("%d
",ret);
103                 break;
104             }
105         }
106     }
107     return 0;
108 }

View Code