線段樹。 統計5個東西。1 統計 這一段4 的個數。2 統計這一段7的個數。3 統計這一段最長的遞增序列個數。4統計這一段最長的遞減序列的個數。5標記這段是否被翻轉。 那麼答案就是求3了。每次翻轉 1-2 3-4互換即可。 [cpp] #include <cmath> #include <ctime> #include <iostream> #include <string> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <map> #include <set> #include <algorithm> #include <cctype> #include <stack> #include <deque> using namespace std; typedef long long LL; #define eps 10e-9 #define inf 0x3f3f3f3f const int maxn = 1000000+100; char s[maxn],op[100],temp[100]; struct node{ int m4,m7,c4,c7; int flip; }T[maxn<<2]; void push_up(int id ){ T[id].c4=T[id<<1].c4+T[id<<1|1].c4; T[id].c7=T[id<<1].c7+T[id<<1|1].c7; T[id].m4=max(T[id<<1].m4+T[id<<1|1].c7,T[id<<1].c4+T[id<<1|1].m4); T[id].m7=max(T[id<<1].m7+T[id<<1|1].c4,T[id<<1].c7+T[id<<1|1].m7); } void build(int id,int l,int r){ if(l==r){ T[id].flip=0; if(s[l-1]=='4') T[id].c4=1; else T[id].c7=1; T[id].m4=T[id].m7=1; return ; } int m=(l+r)>>1; build(id<<1,l,m); build(id<<1|1,m+1,r); push_up(id); } void flip(int id){ T[id].flip^=1; swap(T[id].m4,T[id].m7); swap(T[id].c4,T[id].c7); } void update(int id,int l,int r,int L,int R){ if(l==L&&r==R){ flip(id); return ; } if(T[id].flip){ flip(id<<1); flip(id<<1|1); T[id].flip=0; } int m=(L+R)>>1; if(m>=r){ update(id<<1,l,r,L,m); } else if(l>m){ update(id<<1|1,l,r,m+1,R); } else { update(id<<1,l,m,L,m); update(id<<1|1,m+1,r,m+1,R); } push_up(id); } int main(){ int n,m,l,r; scanf("%d%d",&n,&m); scanf("%s",s); build(1,1,n); while(m--){ scanf("%s",op); if(op[0]=='s'){ scanf("%d %d",&l,&r); update(1,l,r,1,n); } else{ printf("%d\n",T[1].m4); } } return 0; }
