首页 > 代码库 > hdu5057 分块处理，当数值大于数据范围时树状数组 真是巧 将大数据分为小数据来处理
hdu5057 分块处理，当数值大于数据范围时树状数组 真是巧 将大数据分为小数据来处理
这题说的给了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=100005;unsigned short C[2][10][10][50005];int n;int lowbit(int x){ return x&(-x);}void add(int op, int id, int floor, int x,int v){ int ma=op==0?min(50000,n):n-50000; while(x<=ma){ C[op][id][floor][x]+=v; x+=lowbit(x); }}int sum( int op, int id, int floor, int x){ int ans=0; while(x>0){ 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=0; if(R>50000){ s=sum(1,P,D,R-50000)+sum(0,P,D,50000); }else s= sum(0,P,D,R); if(L>50000){ s=s-sum(1,P,D,L-50000-1)-sum(0,P,D,50000); }else s-=sum(0,P,D,L-1); return s;}int main(){ int cas,m; scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); memset(C,0,sizeof(C)); for(int i=1; i<=n; ++i) { scanf("%d",&A[i]); int t =A[i]; int loc=0; int ko=i>50000?i-50000:i; int op=i>50000?1:0; while(loc<10){ add(op,t%10,loc,ko,1); loc++; t/=10; } } char st[2]; int L,R,D,P; for(int i=0; i<m; ++i){ scanf("%s",st); if(st[0]==‘Q‘){ scanf("%d%d%d%d",&L,&R,&D,&P); int ans=solve(L,R,D-1,P); printf("%d\n",ans); }else{ int x,y; scanf("%d%d",&x,&y); int t=A[x]; int loc=0; int lc=x; int op; if(x>50000) lc-=50000,op=1; else op=0; while(loc<10){ add(op,t%10,loc,lc,-1); loc++; t/=10; } A[x]=y; t = y; loc=0; while(loc<10){ add(op,t%10,loc,lc,1); loc++; t/=10; } } } } return 0;}
还有一种操作 就是离线，将每个操作记下来， 10000次操作 做10次 先做在第一位 开一个【100000】【10】的数组，然后先存每个数的第一位，然后按照操作顺序回答所有有关第一位的询问，然后同样的操作第二位 第三位... 意思做了10次这样的整套查询操作
#include <iostream>#include <cstdio>#include <string.h>#include <vector>using namespace std;typedef __int64 ll;const int maxn=100005;int C[10][maxn];int n,m;int eps[10];int chose(int V, int t){ return V / eps[t] % 10;}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=0; while(x>0){ 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[11];void inti(int lo){ memset( C , 0 , sizeof( C ) ); for(int i=1; i<=n; ++i){ B[i]=A[ i ]; int id=chose( B[ i ] , lo ); add(i,id,1); }}void solve(int los){ for(int i =0; i<m; ++i){ if(op[i]==1){ int x=L[i]; add(x,chose(B[x],los),-1); B[x]=R[ i ]; add( x , chose(B[x],los) , 1 ); }else if( op[i]==2 && D[i]==los ){ ans[i]=sum(R[i],P[i])-sum(L[i]-1,P[i]); } }}int main(){ eps[1]=1; for(int i=2; i<=10; ++i) eps[i]=eps[i-1]*10; int cas; scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); for(int i=1; i<=n; ++ i){ scanf("%d",&A[i]); A[i]; } memset(use,false,sizeof(use)); char ch[2]; for(int i=0; i<m; ++i ){ scanf("%s",ch); if(ch[0]==‘S‘){ op[i]=1; scanf("%d%d",&L[i],&R[i]); }else{ op[i]=2; scanf("%d%d%d%d",&L[i],&R[i],&D[i],&P[i]); use[ D[i] ] = true ; } } for(int i=1; i<=10; ++i){ if(use[i]==false)continue; inti(i); solve(i); } for(int i=0; i<m; ++i){ if(op[i]==2) printf("%d\n",ans[i]); } } return 0;}
hdu5057 分块处理，当数值大于数据范围时树状数组 真是巧 将大数据分为小数据来处理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。