[关闭]
@KirinBill 2018-02-26T13:53:47.000000Z 字数 21523 阅读 863

莫队算法学习笔记

分块

目录


算法思想


练习

普通莫队


1.[BZOJ 3781] 小B的询问
- 第一道题,说的详细一点;
- 先用一个数组记录序列上的每个点是否加入答案,每次移动指针就调用add函数,如果当前点加入答案了就删掉,不然就加进去(这是为了兼容后面的树上莫队);
- 用一个桶记录当前区间中每种颜色的出现次数,之后正常计算就行了;
- 每次修改和查询都是计算,所以复杂度为

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using std::sqrt;
  5. using std::sort;
  6. const int MAXN=50005,MAXM=MAXN,MAXK=MAXN;
  7. int m;
  8. int a[MAXN],buc[MAXK];
  9. long long ans[MAXM];
  10. bool use[MAXN];
  11. struct query{
  12. int lp,rp,l_blk;
  13. long long *ans;
  14. static bool cmp(const query &a,const query &b){
  15. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
  16. }
  17. }qry[MAXM];
  18. inline long long sqr(register long long x){return x*x;}
  19. inline void ist(int u){
  20. ans[0]-=sqr(buc[a[u]]);
  21. ++buc[a[u]];
  22. ans[0]+=sqr(buc[a[u]]);
  23. }
  24. inline void del(int u){
  25. ans[0]-=sqr(buc[a[u]]);
  26. --buc[a[u]];
  27. ans[0]+=sqr(buc[a[u]]);
  28. }
  29. inline void add(int u){
  30. if(use[u]) del(u),use[u]=false;
  31. else ist(u),use[u]=true;
  32. }
  33. inline void MoCpt(){
  34. sort(qry+1,qry+m+1,query::cmp);
  35. for(int i=1,l=1,r=0;i<=m;++i){
  36. while(l<qry[i].lp) add(l++);
  37. while(l>qry[i].lp) add(--l);
  38. while(r<qry[i].rp) add(++r);
  39. while(r>qry[i].rp) add(r--);
  40. *qry[i].ans=ans[0];
  41. }
  42. }
  43. int main(){
  44. int n,k;
  45. scanf("%d%d%d",&n,&m,&k);
  46. int BLK_SZ=sqrt(n)+0.5;
  47. for(int i=1;i<=n;++i)
  48. scanf("%d",&a[i]);
  49. for(int i=1;i<=m;++i){
  50. scanf("%d%d",&qry[i].lp,&qry[i].rp);
  51. qry[i].l_blk=qry[i].lp/BLK_SZ;
  52. qry[i].ans=&ans[i];
  53. }
  54. MoCpt();
  55. for(int i=1;i<=m;++i)
  56. printf("%lld\n",ans[i]);
  57. return 0;
  58. }

2.[集训队互测 2009] 小Z的袜子

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cmath>
  4. using std::sort;
  5. using std::sqrt;
  6. const int MAXN=50005;
  7. int m;
  8. long long ans;
  9. int cnt[MAXN],col[MAXN];
  10. long long up[MAXN],dwn[MAXN];
  11. bool use[MAXN];
  12. struct query{
  13. int lp,rp,l_blk;
  14. long long *up;
  15. static bool cmp(const query &a,const query &b){
  16. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
  17. }
  18. }qry[MAXN];
  19. template<typename type>
  20. inline type gcd(register type a,register type b){
  21. register type r;
  22. while(b){r=a%b,a=b,b=r;}
  23. return a;
  24. }
  25. inline void ist(int u){
  26. ans-=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
  27. ++cnt[col[u]];
  28. ans+=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
  29. }
  30. inline void del(int u){
  31. ans-=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
  32. --cnt[col[u]];
  33. ans+=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
  34. }
  35. inline void add(int u){
  36. if(use[u]) del(u),use[u]=false;
  37. else ist(u),use[u]=true;
  38. }
  39. inline void MoCpt(){
  40. sort(qry+1,qry+m+1,query::cmp);
  41. for(int i=1,l=1,r=0;i<=m;++i){
  42. while(l<qry[i].lp) add(l++);
  43. while(l>qry[i].lp) add(--l);
  44. while(r<qry[i].rp) add(++r);
  45. while(r>qry[i].rp) add(r--);
  46. *qry[i].up=ans;
  47. }
  48. }
  49. int main(){
  50. int n;
  51. scanf("%d%d",&n,&m);
  52. int BLK_SZ=sqrt(n)+0.5;
  53. for(int i=1;i<=n;++i)
  54. scanf("%d",&col[i]);
  55. for(int i=1;i<=m;++i){
  56. scanf("%d%d",&qry[i].lp,&qry[i].rp);
  57. dwn[i]=(long long)(qry[i].rp-qry[i].lp+1)*(qry[i].rp-qry[i].lp)>>1;
  58. qry[i].l_blk=qry[i].lp/BLK_SZ;
  59. qry[i].up=&up[i];
  60. }
  61. MoCpt();
  62. long long gcd;
  63. for(int i=1;i<=m;++i){
  64. gcd=::gcd(up[i],dwn[i]);
  65. printf("%lld/%lld\n",up[i]/gcd,dwn[i]/gcd);
  66. }
  67. return 0;
  68. }

3.[BZOJ 3289] Mato的文件管理

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstring>
  5. using std::sqrt;
  6. using std::sort;
  7. using std::unique;
  8. using std::lower_bound;
  9. const int MAXN=50005,MAXQ=MAXN;
  10. int n,q,ta_n;
  11. int a[MAXN];
  12. long long ans[MAXQ];
  13. struct query{
  14. int lp,rp,l_blk;
  15. long long *ans;
  16. static bool cmp(const query &a,const query &b){
  17. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
  18. }
  19. }qry[MAXQ];
  20. class BIT{
  21. private:
  22. long long c[MAXN];
  23. int lowbit(register int x){return x&-x;}
  24. long long qry(int r){
  25. long long ret=0;
  26. for(;r;r-=lowbit(r))
  27. ret+=c[r];
  28. return ret;
  29. }
  30. public:
  31. void add(int l,int x){
  32. for(;l<=ta_n;l+=lowbit(l))
  33. c[l]+=x;
  34. }
  35. long long qry(int l,int r){return qry(r)-qry(l-1);}
  36. }ta;
  37. inline void MoCpt(){
  38. sort(qry+1,qry+q+1,query::cmp);
  39. for(int i=1,l=1,r=0;i<=q;++i){
  40. while(l<qry[i].lp){
  41. ans[0]-=ta.qry(1,a[l]-1);
  42. ta.add(a[l],-1);
  43. ++l;
  44. }
  45. while(l>qry[i].lp){
  46. --l;
  47. ans[0]+=ta.qry(1,a[l]-1);
  48. ta.add(a[l],1);
  49. }
  50. while(r<qry[i].rp){
  51. ++r;
  52. ans[0]+=ta.qry(a[r]+1,ta_n);
  53. ta.add(a[r],1);
  54. }
  55. while(r>qry[i].rp){
  56. ans[0]-=ta.qry(a[r]+1,ta_n);
  57. ta.add(a[r],-1);
  58. --r;
  59. }
  60. *qry[i].ans=ans[0];
  61. }
  62. }
  63. inline void decrete(){
  64. static int tmp[MAXN];
  65. memcpy(tmp,a,sizeof(tmp));
  66. sort(tmp+1,tmp+n+1);
  67. ta_n=unique(tmp+1,tmp+n+1)-tmp-1;
  68. for(int i=1;i<=n;++i)
  69. a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
  70. }
  71. int main(){
  72. scanf("%d",&n);
  73. int BLK_SZ=sqrt(n)+0.5;
  74. for(int i=1;i<=n;++i)
  75. scanf("%d",&a[i]);
  76. decrete();
  77. scanf("%d",&q);
  78. for(int i=1;i<=q;++i){
  79. scanf("%d%d",&qry[i].lp,&qry[i].rp);
  80. qry[i].l_blk=qry[i].lp/BLK_SZ;
  81. qry[i].ans=&ans[i];
  82. }
  83. MoCpt();
  84. for(int i=1;i<=q;++i)
  85. printf("%lld\n",ans[i]);
  86. return 0;
  87. }

4.[AHOI 2013] 作业

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using std::sqrt;
  5. using std::sort;
  6. const int MAXN=100005,MAXM=1000005,MAXSQRTN=320;
  7. int n,m;
  8. int w[MAXN];
  9. bool use[MAXN];
  10. struct answer{
  11. int cnt,tot;
  12. answer(){cnt=tot=0;}
  13. answer& operator +=(const answer &that){
  14. cnt+=that.cnt,tot+=that.tot;
  15. return *this;
  16. }
  17. }ans[MAXM];
  18. struct query{
  19. int lp,rp,l,r,l_blk;
  20. answer *ans;
  21. static bool cmp(const query &a,const query &b){
  22. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
  23. }
  24. }qry[MAXM];
  25. class Block{
  26. private:
  27. int m,BLK_SZ;
  28. int pos[MAXN],buc[MAXN];
  29. struct node{
  30. int l,r;
  31. answer ans;
  32. }d[MAXSQRTN];
  33. answer brute(int l,int r){
  34. answer ret;
  35. for(int i=l;i<=r;++i){
  36. if(buc[i]){
  37. ret.cnt+=buc[i];
  38. ++ret.tot;
  39. }
  40. }
  41. return ret;
  42. }
  43. public:
  44. void init(int n){
  45. BLK_SZ=sqrt(n)+0.5;
  46. m=(n-1)/BLK_SZ+1;
  47. for(int i=1;i<=n;++i)
  48. pos[i]=(i-1)/BLK_SZ+1;
  49. for(int i=1;i<=m;++i){
  50. d[i].l=(i-1)*BLK_SZ+1;
  51. d[i].r=i*BLK_SZ;
  52. }
  53. d[m].r=n;
  54. }
  55. void ist(int x){
  56. ++d[pos[x]].ans.cnt;
  57. if(buc[x]++==0) ++d[pos[x]].ans.tot;
  58. }
  59. void del(int x){
  60. --d[pos[x]].ans.cnt;
  61. if(--buc[x]==0) --d[pos[x]].ans.tot;
  62. }
  63. answer qry(int l,int r){
  64. answer ret;
  65. if(pos[l]==pos[r]) ret=brute(l,r);
  66. else{
  67. for(int i=pos[l]+1;i<pos[r];++i)
  68. ret+=d[i].ans;
  69. ret+=brute(l,d[pos[l]].r);
  70. ret+=brute(d[pos[r]].l,r);
  71. }
  72. return ret;
  73. }
  74. }blk;
  75. inline void add(int u){
  76. if(use[u]) blk.del(w[u]),use[u]=false;
  77. else blk.ist(w[u]),use[u]=true;
  78. }
  79. inline void MoCpt(){
  80. blk.init(n);
  81. sort(qry+1,qry+m+1,query::cmp);
  82. for(int i=1,l=1,r=0;i<=m;++i){
  83. while(l<qry[i].lp) add(l++);
  84. while(l>qry[i].lp) add(--l);
  85. while(r<qry[i].rp) add(++r);
  86. while(r>qry[i].rp) add(r--);
  87. *qry[i].ans=blk.qry(qry[i].l,qry[i].r);
  88. }
  89. }
  90. int main(){
  91. scanf("%d%d",&n,&m);
  92. int BLK_SZ=sqrt(n)+0.5;
  93. for(int i=1;i<=n;++i)
  94. scanf("%d",&w[i]);
  95. for(int i=1;i<=m;++i){
  96. scanf("%d%d%d%d",&qry[i].lp,&qry[i].rp,&qry[i].l,&qry[i].r);
  97. qry[i].l_blk=qry[i].lp/BLK_SZ;
  98. qry[i].ans=&ans[i];
  99. }
  100. MoCpt();
  101. for(int i=1;i<=m;++i)
  102. printf("%d %d\n",ans[i].cnt,ans[i].tot);
  103. return 0;
  104. }

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using std::sqrt;
  5. using std::sort;
  6. const int MAXN=100005,MAXM=1000005,MAXSQRTN=320;
  7. int n,m;
  8. int w[MAXN],ans[MAXM],pos[MAXN];
  9. bool use[MAXN];
  10. struct query{
  11. int lp,rp,l,r;
  12. int *ans;
  13. static bool cmp(const query &a,const query &b){
  14. return pos[a.lp]<pos[b.lp] || (pos[a.lp]==pos[b.lp] && a.rp<b.rp);
  15. }
  16. }qry[MAXM];
  17. class Block{
  18. private:
  19. int m,BLK_SZ;
  20. int buc[MAXN];
  21. struct node{int l,r,ans;}d[MAXSQRTN];
  22. int brute(int l,int r){
  23. int ret=0;
  24. for(int i=l;i<=r;++i){
  25. if(buc[i]) ++ret;
  26. }
  27. return ret;
  28. }
  29. public:
  30. void init(int n){
  31. BLK_SZ=sqrt(n)+0.5;
  32. m=(n-1)/BLK_SZ+1;
  33. for(int i=1;i<=n;++i)
  34. pos[i]=(i-1)/BLK_SZ+1;
  35. for(int i=1;i<=m;++i){
  36. d[i].l=(i-1)*BLK_SZ+1;
  37. d[i].r=i*BLK_SZ;
  38. }
  39. d[m].r=n;
  40. }
  41. void ist(int x){if(buc[x]++==0) ++d[pos[x]].ans;}
  42. void del(int x){if(--buc[x]==0) --d[pos[x]].ans;}
  43. int qry(int l,int r){
  44. int ret=0;
  45. if(pos[l]==pos[r]) ret=brute(l,r);
  46. else{
  47. for(int i=pos[l]+1;i<pos[r];++i)
  48. ret+=d[i].ans;
  49. ret+=brute(l,d[pos[l]].r);
  50. ret+=brute(d[pos[r]].l,r);
  51. }
  52. return ret;
  53. }
  54. }blk;
  55. inline void add(int u){
  56. if(use[u]) blk.del(w[u]),use[u]=false;
  57. else blk.ist(w[u]),use[u]=true;
  58. }
  59. inline void MoCpt(){
  60. blk.init(n);
  61. sort(qry+1,qry+m+1,query::cmp);
  62. for(int i=1,l=1,r=0;i<=m;++i){
  63. while(l<qry[i].lp) add(l++);
  64. while(l>qry[i].lp) add(--l);
  65. while(r<qry[i].rp) add(++r);
  66. while(r>qry[i].rp) add(r--);
  67. *qry[i].ans=blk.qry(qry[i].l,qry[i].r);
  68. }
  69. }
  70. int main(){
  71. scanf("%d%d",&n,&m);
  72. for(int i=1;i<=n;++i)
  73. scanf("%d",&w[i]);
  74. for(int i=1;i<=m;++i){
  75. scanf("%d%d%d%d",&qry[i].lp,&qry[i].rp,&qry[i].l,&qry[i].r);
  76. qry[i].ans=&ans[i];
  77. }
  78. MoCpt();
  79. for(int i=1;i<=m;++i)
  80. printf("%d\n",ans[i]);
  81. return 0;
  82. }

带修改莫队


1.[集训队互测 2011] 数颜色

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using std::pow;
  5. using std::sort;
  6. const int MAXN=10005,MAXM=MAXN,MAXC=1e6+5;
  7. int qcnt;
  8. int col[MAXN],lastcol[MAXN],buc[MAXC],ans[MAXM];
  9. bool use[MAXN];
  10. struct query{
  11. int tm,lp,rp,l_blk,r_blk;
  12. int *ans;
  13. static bool cmp(const query &a,const query &b){
  14. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm));
  15. }
  16. }qry[MAXM];
  17. struct option{int u,precol,newcol;}opt[MAXM];
  18. inline void ist(int u){if(buc[col[u]]++==0) ++ans[0];}
  19. inline void del(int u){if(--buc[col[u]]==0) --ans[0];}
  20. inline void add(int u){
  21. if(use[u]) del(u),use[u]=false;
  22. else ist(u),use[u]=true;
  23. }
  24. inline void mdf(int u,int c){
  25. if(use[u]) del(u);
  26. col[u]=c;
  27. if(use[u]) ist(u);
  28. }
  29. inline void MoCpt(){
  30. sort(qry+1,qry+qcnt+1,query::cmp);
  31. for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
  32. while(tm<qry[i].tm)
  33. ++tm,mdf(opt[tm].u,opt[tm].newcol);
  34. while(tm>qry[i].tm)
  35. mdf(opt[tm].u,opt[tm].precol),--tm;
  36. while(l<qry[i].lp) add(l++);
  37. while(l>qry[i].lp) add(--l);
  38. while(r<qry[i].rp) add(++r);
  39. while(r>qry[i].rp) add(r--);
  40. *qry[i].ans=ans[0];
  41. }
  42. }
  43. int main(){
  44. int n,m;
  45. scanf("%d%d",&n,&m);
  46. int BLK_SZ=pow(n,(double)2/3)+0.5;
  47. for(int i=1;i<=n;++i){
  48. scanf("%d",&col[i]);
  49. lastcol[i]=col[i];
  50. }
  51. char cmd;
  52. for(int i=1,x,y,tm=0;i<=m;++i){
  53. scanf("\n%c%d%d",&cmd,&x,&y);
  54. if(cmd=='Q'){
  55. ++qcnt;
  56. qry[qcnt].lp=x,qry[qcnt].rp=y;
  57. qry[qcnt].l_blk=x/BLK_SZ;
  58. qry[qcnt].r_blk=y/BLK_SZ;
  59. qry[qcnt].tm=tm;
  60. qry[qcnt].ans=&ans[qcnt];
  61. }
  62. else{
  63. ++tm;
  64. opt[tm].u=x,opt[tm].newcol=y;
  65. opt[tm].precol=lastcol[x];
  66. lastcol[x]=y;
  67. }
  68. }
  69. MoCpt();
  70. for(int i=1;i<=qcnt;++i)
  71. printf("%d\n",ans[i]);
  72. return 0;
  73. }

树上莫队

子树查询


1.[Codeforces 375D] Tree and Queries

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using std::sqrt;
  5. using std::sort;
  6. const int MAXN=1e5+5,MAXM=MAXN,MAXK=MAXN,MAXC=MAXN;
  7. int m;
  8. int he[MAXN];
  9. int col[MAXN];
  10. int buc[MAXK],cnt[MAXC];
  11. int ans[MAXM];
  12. int lp[MAXN],rp[MAXN],id[MAXN];
  13. bool use[MAXN];
  14. struct line{int to,nex;}ed[MAXN<<1];
  15. struct query{
  16. int k,lp,rp,l_blk;
  17. int *ans;
  18. static bool cmp(const query &a,const query &b){
  19. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
  20. }
  21. }qry[MAXM];
  22. inline void addE(int u,int v){
  23. static int cnt;
  24. ed[++cnt]=(line){v,he[u]};
  25. he[u]=cnt;
  26. }
  27. void DFS(int u,int fa){
  28. static int idx;
  29. lp[u]=++idx;
  30. id[idx]=u;
  31. for(int i=he[u],v;i;i=ed[i].nex){
  32. v=ed[i].to;
  33. if(v!=fa) DFS(v,u);
  34. }
  35. rp[u]=idx;
  36. }
  37. inline int ist(int u){++buc[++cnt[col[u]]];}
  38. inline void del(int u){--buc[cnt[col[u]]--];}
  39. inline void add(int u){
  40. if(use[u]) del(u),use[u]=false;
  41. else ist(u),use[u]=true;
  42. }
  43. inline void MoCpt(){
  44. sort(qry+1,qry+m+1,query::cmp);
  45. for(int i=1,l=1,r=0;i<=m;++i){
  46. while(l<qry[i].lp) add(id[l++]);
  47. while(l>qry[i].lp) add(id[--l]);
  48. while(r<qry[i].rp) add(id[++r]);
  49. while(r>qry[i].rp) add(id[r--]);
  50. *qry[i].ans=buc[qry[i].k];
  51. }
  52. }
  53. int main(){
  54. int n;
  55. scanf("%d%d",&n,&m);
  56. int BLK_SZ=sqrt(n)+0.5;
  57. for(int i=1;i<=n;++i)
  58. scanf("%d",&col[i]);
  59. for(int i=1,u,v;i<n;++i){
  60. scanf("%d%d",&u,&v);
  61. addE(u,v),addE(v,u);
  62. }
  63. DFS(1,0);
  64. for(int i=1,v;i<=m;++i){
  65. scanf("%d%d",&v,&qry[i].k);
  66. qry[i].lp=lp[v],qry[i].rp=rp[v];
  67. qry[i].l_blk=lp[v]/BLK_SZ;
  68. qry[i].ans=&ans[i];
  69. }
  70. MoCpt();
  71. for(int i=1;i<=m;++i)
  72. printf("%d\n",ans[i]);
  73. return 0;
  74. }

链上查询


1.[SPOJ 10707] Count on a tree II

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstring>
  5. using std::sqrt;
  6. using std::sort;
  7. using std::swap;
  8. using std::unique;
  9. using std::lower_bound;
  10. const int MAXN=40005,MAXM=100005;
  11. int n,m;
  12. int he[MAXN],col[MAXN];
  13. int lp[MAXN],rp[MAXN],id[MAXN<<1];
  14. int dfn[MAXN<<1],pos[MAXN],de[MAXN];
  15. int buc[MAXN],ans[MAXM];
  16. bool use[MAXN];
  17. struct line{int to,nex;}ed[MAXN<<1];
  18. struct query{
  19. int lp,rp,l_blk,lca;
  20. int *ans;
  21. static bool cmp(const query &a,const query &b){
  22. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
  23. }
  24. }qry[MAXM];
  25. class SparseTab{
  26. private:
  27. int c[17][MAXN<<1];
  28. public:
  29. void init(int a[],int n){
  30. memcpy(c[0]+1,a+1,n<<2);
  31. for(int i=1,lim=log2(n);i<=lim;++i){
  32. for(int j=1;j+(1<<i)-1<=n;++j){
  33. if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
  34. c[i][j]=c[i-1][j];
  35. else c[i][j]=c[i-1][j+(1<<i-1)];
  36. }
  37. }
  38. }
  39. int LCA(int u,int v){
  40. u=pos[u],v=pos[v];
  41. if(u>v) swap(u,v);
  42. int k=log2(v-u+1);
  43. if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
  44. return c[k][u];
  45. else return c[k][v-(1<<k)+1];
  46. }
  47. }st;
  48. inline void addE(int u,int v){
  49. static int cnt;
  50. ed[++cnt]=(line){v,he[u]};
  51. he[u]=cnt;
  52. }
  53. void DFS(int u,int fa){
  54. static int idx;
  55. de[u]=de[fa]+1;
  56. dfn[++dfn[0]]=u;
  57. pos[u]=dfn[0];
  58. lp[u]=++idx;
  59. id[idx]=u;
  60. for(int i=he[u],v;i;i=ed[i].nex){
  61. v=ed[i].to;
  62. if(v!=fa){
  63. DFS(v,u);
  64. dfn[++dfn[0]]=u;
  65. }
  66. }
  67. rp[u]=++idx;
  68. id[idx]=u;
  69. }
  70. inline void ist(int u){if(buc[col[u]]++==0) ++ans[0];}
  71. inline void del(int u){if(--buc[col[u]]==0) --ans[0];}
  72. inline void add(int u){
  73. u=id[u];
  74. if(use[u]) del(u),use[u]=false;
  75. else ist(u),use[u]=true;
  76. }
  77. inline void MoCpt(){
  78. sort(qry+1,qry+m+1,query::cmp);
  79. for(int i=1,l=1,r=0;i<=m;++i){
  80. while(l<qry[i].lp) add(l++);
  81. while(l>qry[i].lp) add(--l);
  82. while(r<qry[i].rp) add(++r);
  83. while(r>qry[i].rp) add(r--);
  84. if(qry[i].lca) add(qry[i].lca);
  85. *qry[i].ans=ans[0];
  86. if(qry[i].lca) add(qry[i].lca);
  87. }
  88. }
  89. inline void decrete(){
  90. static int tmp[MAXN];
  91. memcpy(tmp,col,sizeof(tmp));
  92. sort(tmp+1,tmp+n+1);
  93. tmp[0]=unique(tmp+1,tmp+n+1)-tmp-1;
  94. for(int i=1;i<=n;++i)
  95. col[i]=lower_bound(tmp+1,tmp+tmp[0]+1,col[i])-tmp;
  96. }
  97. int main(){
  98. scanf("%d%d",&n,&m);
  99. int BLK_SZ=sqrt(n)+0.5;
  100. for(int i=1;i<=n;++i)
  101. scanf("%d",&col[i]);
  102. decrete();
  103. for(int i=1,u,v;i<n;++i){
  104. scanf("%d%d",&u,&v);
  105. addE(u,v),addE(v,u);
  106. }
  107. DFS(1,0);
  108. st.init(dfn,dfn[0]);
  109. for(int i=1,u,v,lca;i<=m;++i){
  110. scanf("%d%d",&u,&v);
  111. lca=st.LCA(u,v);
  112. if(lp[u]>lp[v]) swap(u,v);
  113. if(lca==u){
  114. qry[i].lp=lp[u];
  115. qry[i].rp=lp[v];
  116. }
  117. else{
  118. qry[i].lp=rp[u];
  119. qry[i].rp=lp[v];
  120. qry[i].lca=lp[lca];
  121. }
  122. qry[i].l_blk=qry[i].lp/BLK_SZ;
  123. qry[i].ans=&ans[i];
  124. }
  125. MoCpt();
  126. for(int i=1;i<=m;++i)
  127. printf("%d\n",ans[i]);
  128. return 0;
  129. }

带修改


1.[WC 2013] 糖果公园

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. using std::pow;
  6. using std::swap;
  7. using std::sort;
  8. const int MAXN=100005,MAXM=MAXN,MAXQ=MAXN;
  9. int qcnt;
  10. int v[MAXM],w[MAXN],col[MAXN],lastcol[MAXN];
  11. int vis[MAXM];
  12. int he[MAXN];
  13. int de[MAXN],dfn[MAXN<<1],pos[MAXN];
  14. int lp[MAXN],rp[MAXN],id[MAXN<<1];
  15. long long ans[MAXQ];
  16. bool use[MAXN];
  17. struct line{int to,nex;}ed[MAXN<<1];
  18. struct option{int u,newcol,precol;}opt[MAXQ];
  19. struct query{
  20. int tm,lp,rp,lca,l_blk,r_blk;
  21. long long *ans;
  22. static bool cmp(const query &a,const query &b){
  23. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && (a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm)));
  24. }
  25. }qry[MAXQ];
  26. class SparseTab{
  27. private:
  28. int c[18][MAXN<<1];
  29. public:
  30. void init(int a[],int n){
  31. memcpy(c[0]+1,a+1,n<<2);
  32. for(int i=1,lim=log2(n);i<=lim;++i){
  33. for(int j=1;j+(1<<i)-1<=n;++j){
  34. if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
  35. c[i][j]=c[i-1][j];
  36. else c[i][j]=c[i-1][j+(1<<i-1)];
  37. }
  38. }
  39. }
  40. int LCA(int u,int v){
  41. u=pos[u],v=pos[v];
  42. if(u>v) swap(u,v);
  43. int k=log2(v-u+1);
  44. if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
  45. return c[k][u];
  46. else return c[k][v-(1<<k)+1];
  47. }
  48. }st;
  49. inline void addE(int u,int v){
  50. static int cnt;
  51. ed[++cnt]=(line){v,he[u]};
  52. he[u]=cnt;
  53. }
  54. void DFS(int u,int fa){
  55. static int idx;
  56. de[u]=de[fa]+1;
  57. dfn[++dfn[0]]=u;
  58. pos[u]=dfn[0];
  59. lp[u]=++idx;
  60. id[idx]=u;
  61. for(int i=he[u],v;i;i=ed[i].nex){
  62. v=ed[i].to;
  63. if(v!=fa){
  64. DFS(v,u);
  65. dfn[++dfn[0]]=u;
  66. }
  67. }
  68. rp[u]=++idx;
  69. id[idx]=u;
  70. }
  71. inline void ist(int u){
  72. ans[0]+=(long long)v[col[u]]*w[++vis[col[u]]];
  73. }
  74. inline void del(int u){
  75. ans[0]-=(long long)v[col[u]]*w[vis[col[u]]--];
  76. }
  77. inline void add(int u){
  78. u=id[u];
  79. if(use[u]) del(u),use[u]=false;
  80. else ist(u),use[u]=true;
  81. }
  82. inline void mdf(int u,int c){
  83. if(use[u]) del(u);
  84. col[u]=c;
  85. if(use[u]) ist(u);
  86. }
  87. inline void MoCpt(){
  88. sort(qry+1,qry+qcnt+1,query::cmp);
  89. for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
  90. while(tm<qry[i].tm)
  91. ++tm,mdf(opt[tm].u,opt[tm].newcol);
  92. while(tm>qry[i].tm)
  93. mdf(opt[tm].u,opt[tm].precol),--tm;
  94. while(l<qry[i].lp) add(l++);
  95. while(l>qry[i].lp) add(--l);
  96. while(r<qry[i].rp) add(++r);
  97. while(r>qry[i].rp) add(r--);
  98. if(qry[i].lca) add(qry[i].lca);
  99. *qry[i].ans=ans[0];
  100. if(qry[i].lca) add(qry[i].lca);
  101. }
  102. }
  103. int main(){
  104. int n,m,q;
  105. scanf("%d%d%d",&n,&m,&q);
  106. int BLK_SZ=pow(n,(double)2/3)+0.5;
  107. for(int i=1;i<=m;++i)
  108. scanf("%d",&v[i]);
  109. for(int i=1;i<=n;++i)
  110. scanf("%d",&w[i]);
  111. for(int i=1,u,v;i<n;++i){
  112. scanf("%d%d",&u,&v);
  113. addE(u,v),addE(v,u);
  114. }
  115. DFS(1,0);
  116. st.init(dfn,dfn[0]);
  117. for(int i=1;i<=n;++i){
  118. scanf("%d",&col[i]);
  119. lastcol[i]=col[i];
  120. }
  121. for(int i=1,t,x,y,lca,tm=0;i<=q;++i){
  122. scanf("%d%d%d",&t,&x,&y);
  123. if(t==0){
  124. ++tm;
  125. opt[tm].u=x;
  126. opt[tm].newcol=y;
  127. opt[tm].precol=lastcol[x];
  128. lastcol[x]=y;
  129. }
  130. else{
  131. ++qcnt;
  132. qry[qcnt].tm=tm;
  133. qry[qcnt].ans=&ans[i];
  134. lca=st.LCA(x,y);
  135. if(lp[x]>lp[y]) swap(x,y);
  136. if(lca==x){
  137. qry[qcnt].lp=lp[x];
  138. qry[qcnt].rp=lp[y];
  139. }
  140. else{
  141. qry[qcnt].lp=rp[x];
  142. qry[qcnt].rp=lp[y];
  143. qry[qcnt].lca=lp[lca];
  144. }
  145. qry[qcnt].l_blk=qry[qcnt].lp/BLK_SZ;
  146. qry[qcnt].r_blk=qry[qcnt].rp/BLK_SZ;
  147. }
  148. }
  149. MoCpt();
  150. for(int i=1;i<=q;++i){
  151. if(ans[i]) printf("%lld\n",ans[i]);
  152. }
  153. return 0;
  154. }

2.[BZOJ 4129] Haruna’s Breakfast

代码:

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstring>
  5. using std::pow;
  6. using std::sqrt;
  7. using std::sort;
  8. using std::swap;
  9. using std::ceil;
  10. const int MAXN=5e4+5,MAXM=MAXN,MAXSQRTN=225;
  11. int n,qcnt;
  12. int he[MAXN],w[MAXN],lastw[MAXN];
  13. int de[MAXN],pos[MAXN],dfn[MAXN<<1];
  14. int lp[MAXN],rp[MAXN],id[MAXN<<1];
  15. int ans[MAXM];
  16. bool use[MAXN];
  17. struct line{int to,nex;}ed[MAXN<<1];
  18. struct query{
  19. int lp,rp,l_blk,r_blk,tm,lca;
  20. int *ans;
  21. static bool cmp(const query &a,const query &b){
  22. return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm));
  23. }
  24. }qry[MAXM];
  25. struct option{int u,prew,neww;}opt[MAXM];
  26. class SparseTab{
  27. private:
  28. int c[17][MAXN<<1];
  29. public:
  30. void init(int a[],int n){
  31. memcpy(c[0]+1,a+1,n<<2);
  32. for(int i=1,lim=log2(n);i<=lim;++i){
  33. for(int j=1;j+(1<<i)-1<=n;++j){
  34. if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
  35. c[i][j]=c[i-1][j];
  36. else c[i][j]=c[i-1][j+(1<<i-1)];
  37. }
  38. }
  39. }
  40. int LCA(int u,int v){
  41. u=pos[u],v=pos[v];
  42. if(u>v) swap(u,v);
  43. int k=log2(v-u+1);
  44. if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
  45. return c[k][u];
  46. else return c[k][v-(1<<k)+1];
  47. }
  48. }st;
  49. class Block{
  50. private:
  51. int n,m,BLK_SZ;
  52. int buc[MAXN];
  53. struct node{
  54. int l,r,cnt;
  55. int size(){return r-l+1;}
  56. }d[MAXSQRTN];
  57. public:
  58. void init(int n){
  59. this->n=n;
  60. BLK_SZ=sqrt(n)+0.5;
  61. m=(n-1)/BLK_SZ+1;
  62. for(int i=1;i<=n;++i)
  63. pos[i]=(i-1)/BLK_SZ+1;
  64. for(int i=1;i<=m;++i){
  65. d[i].l=(i-1)*BLK_SZ+1;
  66. d[i].r=i*BLK_SZ;
  67. }
  68. d[m].r=n;
  69. }
  70. void ist(int x){
  71. if(x<=n && buc[x]++==0)
  72. ++d[pos[x]].cnt;
  73. }
  74. void del(int x){
  75. if(x<=n && --buc[x]==0)
  76. --d[pos[x]].cnt;
  77. }
  78. int qry(){
  79. int cur;
  80. for(cur=1;cur<=m;++cur){
  81. if(d[cur].cnt<d[cur].size())
  82. break;
  83. }
  84. for(int i=d[cur].l;i<=d[cur].r;++i){
  85. if(buc[i]==0) return i;
  86. }
  87. }
  88. }blk;
  89. inline void addE(int u,int v){
  90. static int cnt;
  91. ed[++cnt]=(line){v,he[u]};
  92. he[u]=cnt;
  93. }
  94. void DFS(int u,int fa){
  95. static int idx;
  96. de[u]=de[fa]+1;
  97. dfn[++dfn[0]]=u;
  98. pos[u]=dfn[0];
  99. lp[u]=++idx;
  100. id[idx]=u;
  101. for(int i=he[u],v;i;i=ed[i].nex){
  102. v=ed[i].to;
  103. if(v!=fa){
  104. DFS(v,u);
  105. dfn[++dfn[0]]=u;
  106. }
  107. }
  108. rp[u]=++idx;
  109. id[idx]=u;
  110. }
  111. inline void add(int u){
  112. u=id[u];
  113. if(use[u]) blk.del(w[u]),use[u]=false;
  114. else blk.ist(w[u]),use[u]=true;
  115. }
  116. inline void mdf(int u,int x){
  117. if(use[u]) blk.del(w[u]);
  118. w[u]=x;
  119. if(use[u]) blk.ist(w[u]);
  120. }
  121. inline void MoCpt(){
  122. blk.init(n+1);
  123. sort(qry+1,qry+qcnt+1,query::cmp);
  124. for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
  125. while(tm<qry[i].tm)
  126. ++tm,mdf(opt[tm].u,opt[tm].neww);
  127. while(tm>qry[i].tm)
  128. mdf(opt[tm].u,opt[tm].prew),--tm;
  129. while(l<qry[i].lp) add(l++);
  130. while(l>qry[i].lp) add(--l);
  131. while(r<qry[i].rp) add(++r);
  132. while(r>qry[i].rp) add(r--);
  133. if(qry[i].lca) add(qry[i].lca);
  134. *qry[i].ans=blk.qry();
  135. if(qry[i].lca) add(qry[i].lca);
  136. }
  137. }
  138. int main(){
  139. int m;
  140. scanf("%d%d",&n,&m);
  141. int BLK_SZ=pow(n,(double)2/3)+0.5;
  142. for(int i=1;i<=n;++i){
  143. scanf("%d",&w[i]);
  144. lastw[i]=++w[i];
  145. }
  146. for(int i=1,u,v;i<n;++i){
  147. scanf("%d%d",&u,&v);
  148. addE(u,v),addE(v,u);
  149. }
  150. DFS(1,0);
  151. st.init(dfn,dfn[0]);
  152. for(int i=1,cmd,x,y,tm=0,lca;i<=m;++i){
  153. scanf("%d%d%d",&cmd,&x,&y);
  154. if(cmd==0){
  155. ++tm;
  156. opt[tm].u=x,opt[tm].neww=++y;
  157. opt[tm].prew=lastw[x];
  158. lastw[x]=y;
  159. }
  160. else{
  161. ++qcnt;
  162. lca=st.LCA(x,y);
  163. if(lp[x]>lp[y]) swap(x,y);
  164. if(lca==x){
  165. qry[qcnt].lp=lp[x];
  166. qry[qcnt].rp=lp[y];
  167. }
  168. else{
  169. qry[qcnt].lp=rp[x];
  170. qry[qcnt].rp=lp[y];
  171. qry[qcnt].lca=lp[lca];
  172. }
  173. qry[qcnt].l_blk=qry[qcnt].lp/BLK_SZ;
  174. qry[qcnt].r_blk=qry[qcnt].rp/BLK_SZ;
  175. qry[qcnt].tm=tm;
  176. qry[qcnt].ans=&ans[qcnt];
  177. }
  178. }
  179. MoCpt();
  180. for(int i=1;i<=qcnt;++i)
  181. printf("%d\n",ans[i]-1);
  182. return 0;
  183. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注