题目：有n个数，2种操作，S X Y将arr[x]改为Y，Q L R D P，询问区间[L,R]中第D为是P的数的个数
思路：分块，sum[i][j][k]表示第i块第j位为k的数的个数
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<list> #include<numeric> using namespace std; #define PI acos(-1.0) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f #define mm(a,b) memset(a,b,sizeof(a)) #define PP puts("*********************"); template<class T> T f_abs(T a){ return a > 0 ? a : -a; } template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; } template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} // 0x3f3f3f3f3f3f3f3f // 0x3f3f3f3f const int maxn=1e5+50; int arr[maxn];//下标从0开始 int sum[500][11][10]; int siz,tot;//块的大小，数目，第一块为0~siz-1 int n; void maintain(int pos){ int lb=pos/siz*siz,rb=min(n,lb+siz)-1; int now=pos/siz; for(int i=rb;i>=lb;i--){ int x=arr[i]; for(int j=0;j<11;j++){ sum[now][j][x]++; x/=10; } } } void init(){//初始化块状数组 mm(sum,0); siz=(int)sqrt(n*1.0); tot=n/siz; if(n%siz!=0) tot++; for(int i=1;i<=tot;i++) maintain(min(i*siz,n)-1); } void update(int pos,int val){ int now=pos/siz; int x=arr[pos]; for(int j=0;j<11;j++){ sum[now][j][x]--; x/=10; } arr[pos]=val; x=arr[pos]; for(int j=0;j<11;j++){ sum[now][j][x]++; x/=10; } } int query(int L,int R,int D,int P){ int pos1=L/siz,pos2=R/siz; int res=0; if(pos1==pos2){ for(int i=L;i<=R;i++){ int x=arr[i]; for(int i=0;i<D;i++) x=x/10; if(x==P) res++; } return res; } for(int i=L;i<pos1*siz+siz;i++){ int x=arr[i]; for(int i=0;i<D;i++) x=x/10; if(x==P) res++; } for(int i=pos1+1;i<pos2;i++) res+=sum[i][D][P]; for(int i=pos2*siz;i<=R;i++){ int x=arr[i]; for(int i=0;i<D;i++) x=x/10; if(x==P) res++; } return res; } int main(){ int T,m,x,y,D,P; char str[20]; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&arr[i]); init(); while(m--){ scanf("%s",str); if(str[0]=='S'){ scanf("%d%d",&x,&y);x--; update(x,y); } else{ scanf("%d%d%d%d",&x,&y,&D,&P);x--;y--;D--; int ans=query(x,y,D,P); printf("%d\n",ans); } } } return 0; }