再來一個(gè)數(shù)組記錄區(qū)間是否被修改過...
上面的這些域完全可以支持操作2（見upt函數(shù)）和維護(hù)LIS了(見sumup函數(shù))....
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cassert>
5 using namespace std;
6 const int N = 100005;
7 template <typename T> inline void chkmax(T &a,T b){if(a<b) a=b;}
8 int seg[N<<2][2][2], side[N<<2][2], mx[N<<2][2], full[N<<2][2],chg[N<<2];
9 int upt(int pos){
10 for(int i=0;i<2;i++) side[pos][i] = 9- side[pos][i];
11 swap(mx[pos][0],mx[pos][1]);
12 swap(full[pos][0],full[pos][1]);
13 for(int i=0;i<2;i++){
14 swap(seg[pos][0][i],seg[pos][1][i]);
15 }
16 }
17 void pushdown(int pos,int L,int R){
18 if(chg[pos]){
19 upt(pos);
20 chg[pos] = 0;
21 if(L==R) return ;
22 chg[pos<<1] ^=1;
23 chg[pos<<1|1]^=1;
24 }
25 }
26 void sumup(int pos,int L,int R){
27 int mid = L+R >>1;
28 pushdown(pos<<1 , L, mid);
29 pushdown(pos<<1|1,mid+1,R);
30 side[pos][0] = side[pos<<1][0];
31 side[pos][1] = side[pos<<1|1][1];
32 full[pos][0] = full[pos<<1][0] && full[pos<<1|1][0] && side[pos<<1][1] <= side[pos<<1|1][0];
33 full[pos][1] = full[pos<<1][1] && full[pos<<1|1][1] && side[pos<<1][1] >= side[pos<<1|1][0];
34 seg[pos][0][0] = seg[pos<<1][0][0] + (full[pos<<1][0] && side[pos<<1][1] <= side[pos<<1|1][0] ? seg[pos<<1|1][0][0] : 0);
35 seg[pos][1][0] = seg[pos<<1][1][0] + (full[pos<<1][1] && side[pos<<1][1] >= side[pos<<1|1][0] ? seg[pos<<1|1][1][0] : 0);
36 seg[pos][0][1] = seg[pos<<1|1][0][1] + (full[pos<<1|1][0] && side[pos<<1][1] <= side[pos<<1|1][0] ? seg[pos<<1][0][1] : 0);
37 seg[pos][1][1] = seg[pos<<1|1][1][1] + (full[pos<<1|1][1] && side[pos<<1][1] >= side[pos<<1|1][0] ? seg[pos<<1][1][1] : 0);
38 // cout<<seg[pos][0][1]<<" "<<seg[pos<<1][0][1]<<" "<<seg[pos<<1|1][0][1]<<" "<<full[pos<<1|1]
39 for(int i=0;i<2;i++){
40 mx[pos][i] = max(seg[pos][i][0],seg[pos][i][1]);
41 chkmax(mx[pos][i], max(mx[pos<<1][i] , mx[pos<<1|1][i]) );
42 if( i ? side[pos<<1][1] >= side[pos<<1|1][0]:side[pos<<1][1] <= side[pos<<1|1][0])
43 chkmax(mx[pos][i], seg[pos<<1][i][1] + seg[pos<<1|1][i][0]);
44 }
45 }
46 char num[N];
47 int last;
48 void update(int l,int r,int pos,int L,int R,int flag){
49 if(l<=L && r>=R){
50 if(flag){
51 chg[pos] ^=1;
52 }
53 else {
54 side[pos][0] = side[pos][1] = num[last++] - '0';
55 mx[pos][0] = mx[pos][1] = full[pos][0] = full[pos][1] = 1;
56 for(int i=0;i<2;i++) for(int j=0;j<2;j++) seg[pos][i][j] =1;
57 }
58 return ;
59 }
60 pushdown(pos,L,R);
61 int mid = L+ R >>1;
62 if(l<=mid) update(l,r,pos<<1, L, mid, flag);
63 if(r > mid)update(l,r,pos<<1|1,mid+1,R, flag);
64 sumup(pos,L,R);
65 // cout<<L<<" "<<R<<" "<<seg[pos][0][1]<<" "<<mx[pos][0]<<endl;
66 }
67 int main(){
68 int t;
69 scanf("%d",&t);
70 while(t--){
71 int n,m;last = 0;
72 scanf("%d%d",&n,&m);
73 scanf("%s",num);
74 memset(chg,0,sizeof(chg));
75 for(int i=0;i<n;i++){
76 update(i,i,1,0,n-1,0);
77 }
78 assert(last==n);
79 char cmd[10];
80 while(m--){
81 scanf("%s",cmd);
82 if(cmd[0]=='q'){
83 pushdown(1,0,n-1);
84 printf("%d\n",mx[1][0]);
85 }
86 else {
87 int l,r;
88 scanf("%d%d",&l,&r);
89 l--;r--;
90 update(l,r,1,0,n-1,1);
91 }
92 }
93 puts("");
94 }
95 return 0;
96 }
97
...
...
...
...