分块，v[i][j][k]表示第i块内第j位是k的元素数。非常好写。注意初始化
要注意题意，①第i位是从右往左算的。
②若x没有第i位，则用前导零补齐10位。比如103---->0000000103。
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 using namespace std; 5 const int MOD[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; 6 int T,n,m,ql,qr,x,y,a[100001],l[400],r[400],v[330][11][10],sz,num[100001],sum; 7 char op[1]; 8 inline int Bit(const int &x,const int &p) {return (x/MOD[p-1])%10;} 9 void makeblock() 10 { 11 memset(v,0,sizeof(v)); 12 sz=sqrt(n); sum=0; 13 for(sum=1;sum*sz<n;sum++) 14 { 15 l[sum]=(sum-1)*sz+1; 16 r[sum]=sum*sz; 17 for(int i=l[sum];i<=r[sum];i++) 18 { 19 int t=a[i],cnt=0; 20 while(t) {v[sum][++cnt][t%10]++; t/=10;} 21 for(cnt++;cnt<=10;cnt++) v[sum][cnt][0]++; 22 num[i]=sum; 23 } 24 } 25 l[sum]=sz*(sum-1)+1; r[sum]=n; 26 for(int i=l[sum];i<=r[sum];i++) 27 { 28 int t=a[i],cnt=0; 29 while(t) {v[sum][++cnt][t%10]++; t/=10;} 30 for(cnt++;cnt<=10;cnt++) v[sum][cnt][0]++; 31 num[i]=sum; 32 } 33 } 34 inline void query() 35 { 36 int ans=0; 37 if(num[ql]+1>=num[qr]) {for(int i=ql;i<=qr;i++) if(Bit(a[i],x)==y) ans++;} 38 else 39 { 40 for(int i=ql;i<=r[num[ql]];i++) if(Bit(a[i],x)==y) ans++; 41 for(int i=l[num[qr]];i<=qr;i++) if(Bit(a[i],x)==y) ans++; 42 for(int i=num[ql]+1;i<num[qr];i++) ans+=v[i][x][y]; 43 } 44 printf("%d ",ans); 45 } 46 void update() 47 { 48 int cnt=0; 49 while(a[x]) {v[num[x]][++cnt][a[x]%10]--; a[x]/=10;} 50 for(cnt++;cnt<=10;cnt++) v[num[x]][cnt][0]--; 51 int t=y; a[x]=y; cnt=0; 52 while(t) {v[num[x]][++cnt][t%10]++; t/=10;} 53 for(cnt++;cnt<=10;cnt++) v[num[x]][cnt][0]++; 54 } 55 int main() 56 { 57 scanf("%d",&T); 58 for(;T>0;T--) 59 { 60 scanf("%d%d",&n,&m); 61 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 62 makeblock(); 63 for(int i=1;i<=m;i++) 64 { 65 scanf("%s",op); 66 if(op[0]=='Q') {scanf("%d%d%d%d",&ql,&qr,&x,&y); query();} 67 else {scanf("%d%d",&x,&y); update();} 68 } 69 } 70 return 0; 71 }