锐客网

  1. 首页 > it技术 > >

bzoj|bzoj2906 颜色 分块

分块bzoj

题目大意：
给一个长度为n的颜色序列，颜色不超过m种，询问位置在l~r中间，颜色在a~b之间的同种颜色出现次数的平方的和。
题目分析：
神分块orz
每n^(2/3)个数分成一个块，然后预处理出第i个块到第j个块的前k种颜色的答案是多少，和第i块到第j块第k种颜色有多少个。
【bzoj|bzoj2906 颜色 分块】然后对于l~r相同块就暴力一下，否则整块直接读答案，边边角角就暴力更新一下。
代码如下：

#include #include #define MAXN 42 #define N 52000 #define M 20010 using namespace std; typedef long long LL; int n,m,Q; int block_size,top; int st[MAXN],ed[MAXN],a[N],belong[N]; int cnt[MAXN][MAXN][M]; LL sum[MAXN][MAXN][M],ans; int tmp[N]; void build_blocks() { for(int i=1; i<=n; i++) belong[i]=(i-1)/block_size+1; top=belong[n]; for(int i=1; i<=top; i++) { st[i]=(i-1)*block_size+1; ed[i]=i==top?n:i*block_size; } for(int i=1; i<=top; i++) for(int j=i; j<=top; j++) { for(int k=1; k<=m; k++) cnt[i][j][k]=cnt[i][j-1][k]; for(int k=st[j]; k<=ed[j]; k++) cnt[i][j][a[k]]++; for(int k=1; k<=m; k++) sum[i][j][k]=sum[i][j][k-1]+1ll*cnt[i][j][k]*cnt[i][j][k]; } } LL query(int l,int r,int x,int y) { LL ans=0; if(belong[l]==belong[r]) { for(int i=l; i<=r; i++) if(x<=a[i] && y>=a[i]) ans+=1+2*tmp[a[i]],tmp[a[i]]++; for(int i=l; i<=r; i++) tmp[a[i]]=0; return ans; } ans=sum[belong[l]+1][belong[r]-1][y]-sum[belong[l]+1][belong[r]-1][x-1]; for(int i=l; i<=ed[belong[l]]; i++) if(x<=a[i] && y>=a[i]) { if(tmp[a[i]]==0) tmp[a[i]]=cnt[belong[l]+1][belong[r]-1][a[i]]; ans+=1+2*tmp[a[i]]; tmp[a[i]]++; } for(int i=st[belong[r]]; i<=r; i++) if(x<=a[i] && y>=a[i]) { if(tmp[a[i]]==0) tmp[a[i]]=cnt[belong[l]+1][belong[r]-1][a[i]]; ans+=1+2*tmp[a[i]]; tmp[a[i]]++; } for(int i=l; i<=ed[belong[l]]; i++) tmp[a[i]]=0; for(int i=st[belong[r]]; i<=r; i++) tmp[a[i]]=0; return ans; } int main() { scanf("%d%d%d",&n,&m,&Q); for(int i=1; i<=n; i++) scanf("%d",&a[i]); block_size=pow(n,2.0/3.0); build_blocks(); for(int i=1; i<=Q; i++) { LL l,r,x,y; scanf("%lld%lld%lld%lld",&l,&r,&x,&y); l^=ans; r^=ans; x^=ans; y^=ans; ans=query(l,r,x,y); printf("%lld\n",ans); } return 0; }

    推荐阅读


    上一篇：2015-2-2冬令营日志

    下一篇：bzoj|bzoj4241 历史研究 回滚莫队