1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include <iostream> #include <cstdio> #define MAXN 1000005 #define ll int using namespace std; struct node{ int sheng,jiang,seven,four; bool lazy; }tree[MAXN*4]; int max(int a,int b){ return a>b?a:b; } int n,m; void swap(int &a,int &b){ int t=a; a=b; b=t; } char str[MAXN]; void push_up(int i){ tree[i].seven=tree[i<<1].seven+tree[i<<1|1].seven; tree[i].four=tree[i<<1].four+tree[i<<1|1].four; int max1=max(tree[i<<1].sheng+tree[i<<1|1].seven,tree[i<<1].four+tree[i<<1|1].sheng); tree[i].sheng=max(max1,tree[i<<1].four+tree[i<<1|1].seven); int max2=max(tree[i<<1].jiang+tree[i<<1|1].four,tree[i<<1].seven+tree[i<<1|1].jiang); tree[i].jiang=max(max2,tree[i<<1].seven+tree[i<<1|1].four); } void buildtree(int l,int r,int i){ if (l==r){ tree[i].sheng=1; tree[i].jiang=1; tree[i].seven=(str[l]=='7'); tree[i].four=!tree[i].seven; return ; } int mid=(l+r)>>1; buildtree(l,mid,i<<1); buildtree(mid+1,r,i<<1|1); push_up(i); } void rev(int i){ tree[i].lazy=!tree[i].lazy; swap(tree[i].four,tree[i].seven); swap(tree[i].jiang,tree[i].sheng); } void update(int l,int r,int L,int R,int i){ if (r<L||l>R){ return ; } if (r<=R&&l>=L){ rev(i); return ; } if (tree[i].lazy){ tree[i].lazy=false; rev(i<<1); rev(i<<1|1); } int mid=(l+r)>>1; if (mid>=r){ update(l,mid,L,R,i<<1); } else if (l>mid){ update(mid+1,r,L,R,i<<1|1); } else { update(l,mid,L,R,i<<1); update(mid+1,r,L,R,i<<1|1); } push_up(i); } int main(){ scanf("%d%d%s",&n,&m,str+1); buildtree(1,n,1); int ans; for (int t=0;t<m;t++){ char ch[100]; scanf("%s",ch); if (ch[0]=='c'){ printf("%d\n",tree[1].sheng); } else { int l,r; scanf("%d%d",&l,&r); update(1,n,l,r,1); } } }
|