题目

CF145E Lucky Queries

给定一个序列，每一个数是 \(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('\n');
			continue;
		}
		read(l),read(r);
		Modify(1,1,n,l,r);
	}
	return 0;
}