luogu P2787 语文1（chin1）- 理理思维

题面传送门 感觉这道题比$Ynoi$还卡常。 显然可以直接开$26$个线段树暴力做，复杂度$O(26nlogn)$ 但是这样拿不了几分。 但我们注意到这是权值树。而且所有的权值树的权值之和等于$n$，而我们开了$25n$的空间。所以势必有很大的空间与时间浪费。所以在当前点没有权值时就不必查找，当前点已经有标记就不用深入了。 这样完全随机数据复杂度降至$\sqrt{26}nlogn$ 代码实现:

#include<cstdio> #include<iostream> using namespace std; int n,m,k,x,y,z,sx,f[27][200039],sum[27][200039],fs[30],ans; char _s; inline void push(int l,int r,int snow,int now) { int m=(l+r)>>1; f[snow][now<<1]=f[snow][now<<1|1]=f[snow][now]; sum[snow][now<<1]=(f[snow][now]-1)*(m-l+1); sum[snow][now<<1|1]=(f[snow][now]-1)*(r-m); f[snow][now]=0; } inline void get(int x,int y,int z,int snow,int l,int r,int now) { if(f[snow][now]==z) return; if(x<=l&&r<=y) { f[snow][now]=z; sum[snow][now]=(r-l+1)*(z-1); return; } if(f[snow][now]) push(l,r,snow,now); int m=(l+r)>>1; if(x<=m) get(x,y,z,snow,l,m,now<<1); if(y>m) get(x,y,z,snow,m+1,r,now<<1|1); sum[snow][now]=sum[snow][now<<1]+sum[snow][now<<1|1]; } inline int find(int x,int y,int snow,int l,int r,int now) { if(!sum[snow][now]) return 0; if(x<=l&&r<=y) return sum[snow][now]; if(f[snow][now]) push(l,r,snow,now); int m=(l+r)>>1,fs=0; if(x<=m) fs+=find(x,y,snow,l,m,now<<1); if(y>m) fs+=find(x,y,snow,m+1,r,now<<1|1); return fs; } inline void read(int &x){ char s=getchar();x=0; while(s<'0'||s>'9') s=getchar(); while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar(); } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); register int i,j; read(n);read(m); for(i=1; i<=n; i++) { cin>>_s; if(_s>=97) _s-=32; get(i,i,2,_s-64,1,n,1); } for(i=1; i<=m; i++) { read(sx); if(sx==1) { read(x);read(y); cin>>_s; if(_s>=97) _s-=32; printf("%d\n",find(x,y,_s-64,1,n,1)); } else if(sx==2){ read(x);read(y); for(j=1;j<=26;j++) get(x,y,1,j,1,n,1); cin>>_s; if(_s>=97) _s-=32; get(x,y,2,_s-64,1,n,1); } else{ read(x);read(y); ans=x; for(j=1;j<=26;j++) fs[j]=find(x,y,j,1,n,1),get(x,y,1,j,1,n,1); for(j=1;j<=26;j++) if(fs[j]) get(ans,ans+fs[j]-1,2,j,1,n,1),ans+=fs[j]; } } }