题目
给定一个序列，每一个数是 (4) 或者 (7) ，每次两种操作，翻转一个区间的 (4,7) 或者询问这个序列的最长不降子序列长度。
分析
经典的线段树维护的题目。
考虑维护区间内 (4) 的个数 ，(7) 的个数以及最长不下降子序列长度和最长不上升子序列长度。
于是区间翻转就很好处理了，直接把四个值两两交换即可。
代码
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template<typename T>
inline void write(T x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=1e6+5,N1=1e4+5,M=1e7+5;
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ll long long
int n,m,a[N],tag[N<<2];
int valx[N<<2],valy[N<<2],num4[N<<2],num7[N<<2];//valx：最长不下降，valy：最长不上升
inline void Pushup(int x){
num4[x]=num4[x<<1]+num4[x<<1|1];
num7[x]=num7[x<<1]+num7[x<<1|1];
valx[x]=max(valx[x<<1]+num7[x<<1|1],num4[x<<1]+valx[x<<1|1]);
valy[x]=max(valy[x<<1]+num4[x<<1|1],num7[x<<1]+valy[x<<1|1]);
return ;
}
void Build(int x,int l,int r){
if(l==r) return num4[x]=(a[l]==4),num7[x]=!num4[x],valx[x]=valy[x]=1,void();
int mid=l+r>>1;
Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
Pushup(x);return ;
}
inline void Pushtag(int x){
swap(num4[x],num7[x]),swap(valx[x],valy[x]),tag[x]^=1;
return ;
}
void PushDown(int x){
if(tag[x]) Pushtag(x<<1),Pushtag(x<<1|1);
tag[x]=0;
return ;
}
void Modify(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return Pushtag(x),void();
PushDown(x);int mid=l+r>>1;
if(ql<=mid) Modify(x<<1,l,mid,ql,qr);
if(qr>mid) Modify(x<<1|1,mid+1,r,ql,qr);
Pushup(x);
return ;
}
signed main(){
read(n),read(m);
for(register int i=1;i<=n;i++) scanf("%1d",&a[i]);
Build(1,1,n);
while(m--){
int l,r;char op[5];
scanf("%s",op);
if(op[0]=='c'){
write(valx[1]);putchar('
');
continue;
}
read(l),read(r);
Modify(1,1,n,l,r);
}
return 0;
}