首页 > 代码库 > HDU 3397 线段树区间修改
HDU 3397 线段树区间修改
Sequence operation
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8308 Accepted Submission(s): 2507
Problem Description
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]
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.
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
5
2
6
5
Author
lxhgww&&shǎ崽
及其恶心的一道题目，要维护许多变量= =
由于mx1函数写错找bug找了半天，最后发现自己的思路错了诶，可算A了。
中间维护的变量: 1的个数，0的个数，以第一个开始的最长连续0，以第一个开始的最长连续1，以最后一个开始的最长连续0，以最后一个开始的最长连续1，
区间最长连续1，区间最长连续0，可能有一些变量是互补的我写的有点多余不过感觉很方便把看起来，另外注意当操作为0/1时可以覆盖之前所有的标记。
我用0，1,2表示三种标记全0全1和翻转。len储存区间信息 一维表示‘0‘/‘1‘ 二维表示 head，tail，max_continue_1 三维表示区间对应的结点值。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define MAXN ((100000<<2)+15) 4 int g[3][3]={0,0,0,1,1,1,1,0,-1}; 5 struct SegmentTree 6 { 7 #define M ((L+R)>>1) 8 #define lc (id<<1) 9 #define rc (id<<1|1) 10 int num[MAXN][2],X; 11 int len[2][3][MAXN]; 12 short int laz[MAXN]; 13 void show(int L,int R,int id) 14 { 15 if(L==R) {cout<<num[id][1]<<" ";return;} 16 push_down(L,R,id); 17 show(L,M,lc); 18 show(M+1,R,rc); 19 push_up(L,R,id); 20 } 21 void init() 22 { 23 memset(num,0,sizeof(num)); 24 memset(laz,-1,sizeof(laz)); 25 memset(len,0,sizeof(len)); 26 } 27 void push_up(int L,int R,int id) 28 { 29 num[id][0]=num[lc][0]+num[rc][0]; 30 num[id][1]=num[lc][1]+num[rc][1]; 31 for(int i=0;i<=1;++i){ 32 len[i][0][id]=len[i][0][lc]; 33 len[i][1][id]=len[i][1][rc]; 34 len[i][2][id]=max(max(len[i][2][lc],len[i][2][rc]),len[i][1][lc]+len[i][0][rc]); 35 if(!num[lc][i^1]) len[i][0][id]=max(len[i][0][id],len[i][0][lc]+len[i][0][rc]); 36 if(!num[rc][i^1]) len[i][1][id]=max(len[i][1][id],len[i][1][rc]+len[i][1][lc]); 37 } 38 } 39 void push_down(int L,int R,int id) 40 { 41 if(laz[id]==-1) return; 42 laz[lc]=laz[lc]==-1?laz[id]:g[laz[id]][laz[lc]]; 43 laz[rc]=laz[rc]==-1?laz[id]:g[laz[id]][laz[rc]]; 44 if(laz[id]<2){ 45 num[lc][laz[id]^1]=num[rc][laz[id]^1]=0; 46 num[lc][laz[id]]=M-L+1; 47 num[rc][laz[id]]=R-M; 48 len[laz[id]^1][0][lc]=len[laz[id]^1][1][lc]=len[laz[id]^1][2][lc]=0; 49 len[laz[id]^1][0][rc]=len[laz[id]^1][1][rc]=len[laz[id]^1][2][rc]=0; 50 len[laz[id]][0][lc]=len[laz[id]][1][lc]=len[laz[id]][2][lc]=M-L+1; 51 len[laz[id]][0][rc]=len[laz[id]][1][rc]=len[laz[id]][2][rc]=R-M; 52 } 53 else { 54 swap(num[lc][0],num[lc][1]); 55 swap(num[rc][0],num[rc][1]); 56 swap(len[0][0][lc],len[1][0][lc]); swap(len[0][1][lc],len[1][1][lc]); swap(len[0][2][lc],len[1][2][lc]); 57 swap(len[0][0][rc],len[1][0][rc]); swap(len[0][1][rc],len[1][1][rc]); swap(len[0][2][rc],len[1][2][rc]); 58 } 59 laz[id]=-1; 60 } 61 void build(int L,int R,int id) 62 { 63 if(L==R) 64 { 65 scanf("%d",&X);num[id][X]++; 66 len[X][2][id]=len[X][0][id]=len[X][1][id]=1; 67 return; 68 } 69 build(L,M,lc); 70 build(M+1,R,rc); 71 push_up(L,R,id); 72 } 73 void change(int L,int R,int id,int l,int r,int x) 74 { 75 if(L>=l&&R<=r){ 76 num[id][x^1]=0; 77 num[id][x]=R-L+1; 78 len[x][0][id]=len[x][1][id]=len[x][2][id]=R-L+1; 79 len[x^1][0][id]=len[x^1][1][id]=len[x^1][2][id]=0; 80 laz[id]=laz[id]==-1?x:g[x][laz[id]]; 81 return; 82 } 83 push_down(L,R,id); 84 if(l<=M) change(L,M,lc,l,r,x); 85 if(r>M) change(M+1,R,rc,l,r,x); 86 push_up(L,R,id); 87 } 88 void swp(int L,int R,int id,int l,int r) 89 { 90 if(L>=l&&R<=r){ 91 swap(num[id][0],num[id][1]); 92 laz[id]=laz[id]==-1?2:g[2][laz[id]]; 93 swap(len[0][0][id],len[1][0][id]); 94 swap(len[0][1][id],len[1][1][id]); 95 swap(len[0][2][id],len[1][2][id]); 96 return; 97 } 98 push_down(L,R,id); 99 if(l<=M) swp(L,M,lc,l,r); 100 if(r>M) swp(M+1,R,rc,l,r); 101 push_up(L,R,id); 102 } 103 int num1(int L,int R,int id,int l,int r) 104 { 105 if(L>=l&&R<=r) return num[id][1]; 106 push_down(L,R,id); 107 int s=0; 108 if(l<=M) s+=num1(L,M,lc,l,r); 109 if(r>M) s+=num1(M+1,R,rc,l,r); 110 push_up(L,R,id); 111 return s; 112 } 113 int mx1(int L,int R,int id,int l,int r) 114 { 115 if(L>=l&&R<=r) return len[1][2][id]; 116 push_down(L,R,id); 117 int s=0; 118 if(r<=M) s=max(s, mx1(L,M,lc,l,r)); 119 else if(l>M) s=max(s,mx1(M+1,R,rc,l,r)); 120 else { 121 int lm=len[1][1][lc],rm=len[1][0][rc]; 122 if(lm>M-l+1) lm=M-l+1; 123 if(rm>r-M) rm=r-M; 124 s=max(s,max(max(mx1(L,M,lc,l,r),mx1(M+1,R,rc,l,r)),lm+rm)); 125 } 126 push_up(L,R,id); 127 return s; 128 } 129 }seg; 130 131 int main() 132 { 133 int t,n,m,i,j,k,opt,a,b; 134 scanf("%d",&t); 135 while(t--){ 136 scanf("%d%d",&n,&m); 137 seg.init(); 138 seg.build(1,n,1); 139 while(m--){ 140 scanf("%d%d%d",&opt,&a,&b);a++;b++; 141 if(opt==0) seg.change(1,n,1,a,b,0); 142 else if(opt==1) seg.change(1,n,1,a,b,1); 143 else if(opt==2) seg.swp(1,n,1,a,b); 144 else if(opt==3) printf("%d\n",seg.num1(1,n,1,a,b)); 145 else printf("%d\n",seg.mx1(1,n,1,a,b)); 146 } 147 } 148 return 0; 149 }
HDU 3397 线段树区间修改
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。