解题报告：luogu P2787

尝试 Ynoi 无果，滚来切屑题了。

题目链接：P2787 语文1（chin1）- 理理思维

区间排序一看就很谔谔，记得有一道 Ynoi 也是这样的。

Ynoi? 那不行，看到有枚举暴力的标签，感觉到可以搞事情。

值域很小（只有 (26)），所以可以枚举值域得到个数，修改即可。

比如说我们先查询 (A/a) 出现的次数，然后把这个区间前这些全修改成 (A/a)，然后对每个数都这样操作，这样只有 (mathcal O(26log n)) 的复杂度。

这样就只有 (2) 个操作了。

剩下的一些和序列操作类似，好写多了。

注意懒标记即可。

(Code:)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

#define read(x) scanf("%d",&x)
#define MAXN 50005

struct node
{
	int sum[30],l,r,lazy;
	node(){lazy=0;memset(sum,0,sizeof(sum));l=r=0;}
}a[MAXN<<2];
int n,m;
char s[MAXN],c;
int t,l,r;

inline int get(char a){return (a<='z'&&a>='a')?a-'a'+1:a-'A'+1;}

inline void update(int k){for(register int i=1;i<=26;i++) a[k].sum[i]=a[k<<1].sum[i]+a[k<<1|1].sum[i];}

inline void build(int k,int l,int r)
{
	a[k].l=l,a[k].r=r;
	if(l==r)
	{
		int v=get(s[l]);
		a[k].sum[v]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	update(k);
}

inline void lazydown(int k)
{
	if(a[k].l==a[k].r){a[k].lazy=0;return;}
	for(register int i=1;i<=26;i++) a[k<<1].sum[i]=a[k<<1|1].sum[i]=0;
	a[k<<1].sum[a[k].lazy]=a[k<<1].r-a[k<<1].l+1;
	a[k<<1|1].sum[a[k].lazy]=a[k<<1|1].r-a[k<<1|1].l+1;
	a[k<<1].lazy=a[k].lazy;
	a[k<<1|1].lazy=a[k].lazy;
	a[k].lazy=0;
	return;  
}

inline void turn(int k,int l,int r,int x)
{
	if(a[k].l==l&&a[k].r==r)
	{
		for(register int i=1;i<=26;i++) a[k].sum[i]=0;
		a[k].sum[x]=a[k].r-a[k].l+1;
		a[k].lazy=x;
		return;
	}
	if(a[k].lazy) lazydown(k);
	int mid=(a[k].l+a[k].r)>>1;
	if(r<=mid) turn(k<<1,l,r,x);
	else if(l>mid) turn(k<<1|1,l,r,x);
	else turn(k<<1,l,mid,x),turn(k<<1|1,mid+1,r,x);
	update(k);
}

inline int query(int k,int l,int r,int x)
{
	if(a[k].lazy) lazydown(k);
	if(a[k].l==l&&a[k].r==r) return a[k].sum[x];
	int mid=(a[k].l+a[k].r)>>1;
	if(r<=mid) return query(k<<1,l,r,x);
	else if(l>mid) return query(k<<1|1,l,r,x);
	else return query(k<<1,l,mid,x)+query(k<<1|1,mid+1,r,x);
}

int main()
{
	read(n),read(m);
	scanf("%s",s);
	for(register int i=n;i>=1;i--) s[i]=s[i-1];
	build(1,1,n);
	for(register int j=1;j<=m;j++)
	{
		read(t),read(l),read(r);
		if(t==1) cin>>c,printf("%d
",query(1,l,r,get(c)));
		else if(t==2) cin>>c,turn(1,l,r,get(c));
		else
		{
			int ll=l,now[30]={0};
			for(register int i=1;i<=26;i++) now[i]=query(1,l,r,i);
			for(register int i=1;i<=26;i++)
			{
				if(ll>r) break;
				if(now[i])
				{
					turn(1,ll,ll+now[i]-1,i);
					ll+=now[i];
				}
			}
		}
	}
	return 0;
}

不开 (O2) 死得有点惨，不知道为什么。