这题说的给了100000个数有100000次操作 询问 L和R 区间内 在D位上为P的个数，用树状数组存 要开[10][10][100000]的int 开不了但是能开 这么大的unsign short 这样我们将这个树状数组一分为二 50000 个位前面 50000 为后面 我们知道unshort 范围在60000多显然这样是可以开的了
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef __int64 ll;
const int maxn=;
unsigned short C[][][][];
int n;
int lowbit(int x){
return x&(-x);
}
void add(int op, int id, int floor, int x,int v){
int ma=op==?min(,n):n-;
while(x<=ma){
C[op][id][floor][x]+=v;
x+=lowbit(x);
}
}
int sum( int op, int id, int floor, int x){
int ans=;
while(x>){
ans+=C[op][id][floor][x];
x-=lowbit(x);
}
return ans;
}
int A[maxn];
int solve(int L, int R, int D, int P){
int s=;
if(R>){
s=sum(,P,D,R-)+sum(,P,D,);
}else s= sum(,P,D,R);
if(L>){
s=s-sum(,P,D,L--)-sum(,P,D,);
}else s-=sum(,P,D,L-);
return s;
}
int main()
{
int cas,m;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
memset(C,,sizeof(C));
for(int i=; i<=n; ++i)
{
scanf("%d",&A[i]);
int t =A[i];
int loc=;
int ko=i>?i-:i;
int op=i>?:;
while(loc<){
add(op,t%,loc,ko,);
loc++;
t/=;
}
}
char st[];
int L,R,D,P;
for(int i=; i<m; ++i){
scanf("%s",st);
if(st[]=='Q'){
scanf("%d%d%d%d",&L,&R,&D,&P);
int ans=solve(L,R,D-,P);
printf("%d\n",ans);
}else{
int x,y;
scanf("%d%d",&x,&y);
int t=A[x];
int loc=;
int lc=x;
int op;
if(x>) lc-=,op=;
else op=;
while(loc<){
add(op,t%,loc,lc,-);
loc++;
t/=;
}
A[x]=y;
t = y;
loc=;
while(loc<){
add(op,t%,loc,lc,);
loc++;
t/=;
}
}
}
}
return ;
}
还有一种操作 就是离线，将每个操作记下来， 10000次操作 做10次 先做在第一位 开一个【100000】【10】的数组，然后先存每个数的第一位，然后按照操作顺序回答所有有关第一位的询问，然后同样的操作第二位 第三位... 意思做了10次这样的整套查询操作
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
typedef __int64 ll;
const int maxn=;
int C[][maxn];
int n,m;
int eps[];
int chose(int V, int t){
return V / eps[t] % ;
}
int lowbit(int x){
return x&(-x);
}
void add( int x, int id , int v){
while(x<=n){
C[id][x]+=v;
x+=lowbit(x);
}
}
int sum( int x, int id ){
int ans=;
while(x>){
ans+=C[id][x];
x-=lowbit(x);
}
return ans;
}
int A[maxn];
int B[maxn];
int ans[maxn];
int op[maxn],L[maxn],R[maxn],D[maxn],P[maxn];
bool use[];
void inti(int lo){
memset( C , , sizeof( C ) );
for(int i=; i<=n; ++i){
B[i]=A[ i ];
int id=chose( B[ i ] , lo );
add(i,id,);
}
}
void solve(int los){
for(int i =; i<m; ++i){
if(op[i]==){
int x=L[i];
add(x,chose(B[x],los),-);
B[x]=R[ i ];
add( x , chose(B[x],los) , );
}else if( op[i]== && D[i]==los ){
ans[i]=sum(R[i],P[i])-sum(L[i]-,P[i]);
}
}
}
int main()
{
eps[]=;
for(int i=; i<=; ++i)
eps[i]=eps[i-]*;
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
for(int i=; i<=n; ++ i){
scanf("%d",&A[i]);
A[i];
}
memset(use,false,sizeof(use));
char ch[];
for(int i=; i<m; ++i ){
scanf("%s",ch);
if(ch[]=='S'){
op[i]=;
scanf("%d%d",&L[i],&R[i]);
}else{
op[i]=;
scanf("%d%d%d%d",&L[i],&R[i],&D[i],&P[i]);
use[ D[i] ] = true ;
}
}
for(int i=; i<=; ++i){
if(use[i]==false)continue;
inti(i);
solve(i);
}
for(int i=; i<m; ++i){
if(op[i]==) printf("%d\n",ans[i]);
}
}
return ;
}