越来越高级了
区间重置非常好弄
此题的关键在于查询区间内一个数的个数
其实可以发现，在多次操作之后，整个序列就变成仅由几段不同数值所组成的序列了
我们可以维护每一个分块是否只有一种权值，在询问的时候，针对这种块可以O（1）统计答案
否则暴力统计然后修改标记，不完整的块暴力就可以了
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int maxn=100005; 7 long long read() 8 { 9 long long x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,blo; 15 int v[maxn],bl[maxn],tag[maxn]; 16 void reset(int x) 17 { 18 if(tag[x]==-1) return; 19 for(int i=(x-1)*blo+1;i<=blo*x;i++) v[i]=tag[x]; 20 tag[x]=-1; 21 } 22 int solve(int a,int b,int c) 23 { 24 int ans=0; 25 reset(bl[a]); 26 for(int i=a;i<=min(bl[a]*blo,b);i++) 27 if(v[i]!=c) v[i]=c; 28 else ans++; 29 if(bl[a]!=bl[b]) 30 { 31 reset(bl[b]); 32 for(int i=(bl[b]-1)*blo+1;i<=b;i++) 33 if(v[i]!=c) v[i]=c; 34 else ans++; 35 } 36 for(int i=bl[a]+1;i<=bl[b]-1;i++) 37 if(tag[i]!=-1) 38 { 39 if(tag[i]!=c) tag[i]=c; 40 else ans+=blo; 41 } 42 else 43 { 44 for(int j=(i-1)*blo+1;j<=i*blo;j++) 45 if(v[j]!=c) v[j]=c; 46 else ans++; 47 tag[i]=c; 48 } 49 return ans; 50 } 51 int main() 52 { 53 memset(tag,-1,sizeof(tag)); 54 n=read();blo=sqrt(n); 55 for(int i=1;i<=n;i++) v[i]=read(); 56 for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1; 57 for(int i=1;i<=n;i++) 58 { 59 int a=read(),b=read(),c=read(); 60 printf("%d ",solve(a,b,c)); 61 } 62 return 0; 63 }