[关闭]
@Scarlet 2017-03-27T11:21:31.000000Z 字数 26301 阅读 519

根号算法

——如何让复杂度去掉

数据结构 算法

By



分块


一般分块

板子&原理

  1. SIZ=(int)sqrt(n); //块大小
  2. for(int i=(x-1)*SIZ+1;i<=x*SIZ;i++); //遍历块x(当然)
  3. bl[i]=(i-1)/SIZ+1 //i$所在块编号
  4. f[bl[a]+1][bl[b]-1] //a、b之间块内答案

大概只有一类题:
(在线)维护XJB玩意儿。

无修
维护一些JB玩意儿比如块内答案、块间答案,然后询问的时候大力出奇迹。
带修
考虑打标记或者以一定频率重构块。

BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊

感觉地球人都会听说过而且都会做.
以及我去年2月份代码真好看.

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cmath>
  7. #define maxn 200011
  8. using namespace std;
  9. int n,m,bl[maxn],f[maxn],to[maxn],k[maxn];
  10. inline int ask(int x){int he=0;while (x<n)he+=k[x],x=to[x];return he;}
  11. inline void change(int x,int y)
  12. {
  13. int i,j=bl[x],r;
  14. f[x]=y;r=y;
  15. if (bl[r]==bl[x]) to[x]=to[r],k[x]=k[r]+1;
  16. else to[x]=y,k[x]=1;
  17. for (i=x-1;i>=0;i--)
  18. {
  19. if (bl[i]!=j) break;r=f[i];
  20. if (bl[r]==bl[i]&&r<n) to[i]=to[r],k[i]=k[r]+1;
  21. else to[i]=r,k[i]=1;
  22. }
  23. }
  24. int main()
  25. {
  26. scanf("%d",&n);
  27. int i,j,aa,bb,cc,r,sq=int(sqrt(n)),o=sq,t=0;
  28. for (i=0;i<n;i++)
  29. {
  30. if (o==sq)bl[i]=++t,o=1;else bl[i]=t,o++;
  31. scanf("%d",&f[i]);f[i]+=i;
  32. }
  33. for (i=n-1;i>=0;i--)
  34. {
  35. r=f[i];
  36. if (bl[r]!=bl[i]||r>=n) to[i]=r,k[i]=1;
  37. else to[i]=to[r],k[i]=k[r]+1;
  38. }
  39. scanf("%d",&m);
  40. while (m--)
  41. {
  42. scanf("%d",&aa);
  43. if (aa==1)scanf("%d",&bb),printf("%d\n",ask(bb));
  44. else scanf("%d%d",&bb,&cc),cc+=bb,change(bb,cc);
  45. }
  46. return 0;
  47. }

BZOJ 2724: [Violet 6]蒲公英

题意:在线区间众数
cls有技巧,但是代码复杂度太大只敢写带的.
大致思路是分块,处理出块间众数,答案只可能在块间或者零碎的部分中产生。
枚举一下是哪个,时间计算一下出现了几次,就了.

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100005
  6. #define maxm 350
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline LL read()
  11. {
  12. LL x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. int n,m,SIZ,id,v[maxn],bl[maxn];
  18. int f[maxm][maxm];
  19. map<int,int>mp;
  20. int val[maxn],cnt[maxn];
  21. vector<int>ve[maxn];
  22. void pre(int x)
  23. {
  24. memset(cnt,0,sizeof(cnt));
  25. int mx=0,ans=0,t;
  26. for(int i=(x-1)*SIZ+1;i<=n;i++)
  27. {
  28. cnt[v[i]]++;
  29. t=bl[i];
  30. if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))
  31. ans=v[i],mx=cnt[v[i]];
  32. f[x][t]=ans;
  33. }
  34. }
  35. int Q(int l,int r,int x)
  36. {
  37. return upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);
  38. }
  39. int query(int a,int b)
  40. {
  41. int ans,mx,t;
  42. ans=f[bl[a]+1][bl[b]-1];
  43. mx=Q(a,b,ans);
  44. for(int i=a;i<=min(bl[a]*SIZ,b);i++)
  45. {
  46. t=Q(a,b,v[i]);
  47. if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;
  48. }
  49. if(bl[a]!=bl[b])
  50. for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)
  51. {
  52. t=Q(a,b,v[i]);
  53. if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;
  54. }
  55. return ans;
  56. }
  57. int main()
  58. {
  59. n=read(),m=read();
  60. SIZ=(int)sqrt(n);
  61. int ans=0;
  62. for(int i=1;i<=n;i++)
  63. {
  64. v[i]=read();
  65. if(!mp[v[i]])mp[v[i]]=++id,val[id]=v[i];
  66. v[i]=mp[v[i]];
  67. ve[v[i]].push_back(i);
  68. }
  69. for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;
  70. for(int i=1;i<=bl[n];i++)pre(i);
  71. for(int i=1;i<=m;i++)
  72. {
  73. int a=read(),b=read();
  74. a=(a+ans-1)%n+1;b=(b+ans-1)%n+1;
  75. if(a>b)swap(a,b);
  76. ans=val[query(a,b)];
  77. printf("%d\n",ans);
  78. }
  79. return 0;
  80. }

但是我不知怎地就看到了PoPoQQQ的无分块技巧,比在下带的好写到不知道哪里去了(但是并不短)。
姿势水平++。

RunID User Problem Result Memory Time Language Code_Length Submit_Time
1777662 xmc54300 2724 Accepted 35516 kb 3832 ms C++/Edit 1980 B 2017-01-06
1777222 xmc54300 2724 Accepted 3676 kb 18892 ms C++/Edit 1723 B 2017-01-06

Interesting..

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 40010
  6. #define maxm 210
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. #define ZZ t=++cnt[v[i]];if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;
  11. inline LL read()
  12. {
  13. LL x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. int n,m,SIZ,id,v[maxn],bl[maxn];
  19. int f[maxm][maxm],ff[maxm][maxm],g[maxm][maxn];
  20. map<int,int>mp;
  21. int val[maxn],cnt[maxn],tim[maxn],T;
  22. void pre(int x)
  23. {
  24. memset(cnt,0,sizeof(cnt));
  25. int mx=0,ans=0,t;
  26. for(int i=(x-1)*SIZ+1;i<=n;i++)
  27. {
  28. cnt[v[i]]++;t=bl[i];
  29. if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))ans=v[i],mx=cnt[v[i]];
  30. f[x][t]=ans;ff[x][t]=mx;
  31. }
  32. }
  33. int query(int a,int b)
  34. {
  35. int ans,mx,t;++T;
  36. ans=f[bl[a]+1][bl[b]-1];
  37. mx=ff[bl[a]+1][bl[b]-1];
  38. if(bl[a]==bl[b])
  39. for(int i=a;i<=b;i++)
  40. {
  41. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=0;
  42. ZZ
  43. }
  44. else
  45. {
  46. for(int i=a;i<=bl[a]*SIZ;i++)
  47. {
  48. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];
  49. ZZ
  50. }
  51. for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)
  52. {
  53. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];
  54. ZZ
  55. }
  56. }
  57. return ans;
  58. }
  59. int main()
  60. {
  61. n=read(),m=read();
  62. SIZ=(int)sqrt(n);
  63. int ans=0;
  64. for(int i=1;i<=n;i++)
  65. {
  66. v[i]=read();
  67. if(!mp[v[i]])mp[v[i]]=++id,val[id]=v[i];
  68. v[i]=mp[v[i]];
  69. }
  70. for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;
  71. for(int i=1;i<=n;i++)
  72. g[bl[i]][v[i]]++;
  73. for(int i=1;i<=bl[n];i++)
  74. for(int j=1;j<=n;j++)
  75. g[i][j]+=g[i-1][j];
  76. for(int i=1;i<=bl[n];i++)pre(i);
  77. for(int i=1;i<=m;i++)
  78. {
  79. int a=read(),b=read();
  80. a=(a+ans-1)%n+1;b=(b+ans-1)%n+1;
  81. if(a>b)swap(a,b);
  82. ans=val[query(a,b)];
  83. printf("%d\n",ans);
  84. }
  85. return 0;
  86. }

BZOJ 4241: 历史研究

原理一样,答案不在块间就在边角料里。
过不去

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. #define maxm 350
  7. #define INF 200000000000000ll
  8. using namespace std;
  9. typedef long long LL;
  10. #define G c=getchar()
  11. #define ZZ t=val[v[i]]*++cnt[v[i]];t>mx?mx=t:0;
  12. inline LL read()
  13. {
  14. LL x=0,f=1;char G;
  15. while(c>57||c<48){if(c=='-')f=-1;G;}
  16. while(c>47&&c<58)x=x*10+c-48,G;
  17. return x*f;
  18. }
  19. int n,m,SIZ,id,v[maxn],bl[maxn];
  20. LL f[maxm][maxm];int g[maxm][maxn];
  21. map<int,int>mp;
  22. LL val[maxn],cnt[maxn];
  23. int tim[maxn],T;
  24. void pre(int x)
  25. {
  26. memset(cnt,0,sizeof(cnt));
  27. LL mx=-INF;
  28. for(int i=(x-1)*SIZ+1;i<=n;i++)
  29. {
  30. cnt[v[i]]++;
  31. if(cnt[v[i]]*val[v[i]]>mx)mx=cnt[v[i]]*val[v[i]];
  32. f[x][bl[i]]=mx;
  33. }
  34. }
  35. LL query(int a,int b)
  36. {
  37. ++T;LL t,mx=f[bl[a]+1][bl[b]-1];
  38. if(bl[a]==bl[b])
  39. for(int i=a;i<=b;i++)
  40. {
  41. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=0;
  42. ZZ
  43. }
  44. else
  45. {
  46. for(int i=a;i<=bl[a]*SIZ;i++)
  47. {
  48. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];
  49. ZZ
  50. }
  51. for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)
  52. {
  53. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];
  54. ZZ
  55. }
  56. }
  57. return mx;
  58. }
  59. int main()
  60. {
  61. n=read(),m=read();
  62. SIZ=(int)sqrt(n);
  63. for(int i=1;i<=n;i++)
  64. {
  65. v[i]=read();
  66. if(!mp[v[i]])mp[v[i]]=++id,val[id]=v[i];
  67. v[i]=mp[v[i]];
  68. }
  69. for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;
  70. for(int i=1;i<=n;i++)
  71. g[bl[i]][v[i]]++;
  72. for(int i=1;i<=bl[n];i++)
  73. for(int j=1;j<=n;j++)
  74. g[i][j]+=g[i-1][j];
  75. for(int i=1;i<=bl[n];i++)pre(i);
  76. for(int i=1;i<=m;i++)
  77. {
  78. int a=read(),b=read();
  79. printf("%lld\n",query(a,b));
  80. }
  81. return 0;
  82. }

BZOJ 2821: 作诗(Poetize)

做题前先吟一句诗:
这套路贼JB明显。

但是出题人您为什么要卡内存啊,幸好在下分块可以调节块的大小,但还是MLE+RE了不知道几发

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100005
  6. #define maxm 305
  7. #define INF 200000000000000ll
  8. using namespace std;
  9. typedef long long LL;
  10. #define G c=getchar()
  11. inline LL read()
  12. {
  13. LL x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. int n,m,SIZ,id,v[maxn],bl[maxn];
  19. int f[maxm][maxm],g[maxm][maxn],cnt[maxn];
  20. int tim[maxn],T,c;
  21. void pre(int x)
  22. {
  23. memset(cnt,0,sizeof(cnt));
  24. int ans=0;
  25. for(int i=(x-1)*SIZ+1;i<=n;i++)
  26. {
  27. cnt[v[i]]++;
  28. if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;
  29. else ans++;
  30. f[x][bl[i]]=ans;
  31. }
  32. }
  33. int query(int a,int b)
  34. {
  35. ++T;
  36. int ans=f[bl[a]+1][bl[b]-1],t;
  37. if(bl[a]==bl[b])
  38. for(int i=a;i<=b;i++)
  39. {
  40. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=0;
  41. t=++cnt[v[i]];
  42. if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;
  43. else ans++;
  44. }
  45. else
  46. {
  47. for(int i=a;i<=bl[a]*SIZ;i++)
  48. {
  49. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];
  50. t=++cnt[v[i]];
  51. if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;
  52. else ans++;
  53. }
  54. for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)
  55. {
  56. if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];
  57. t=++cnt[v[i]];
  58. if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;
  59. else ans++;
  60. }
  61. }
  62. return ans;
  63. }
  64. int main()
  65. {
  66. n=read(),c=read(),m=read();
  67. int ans=0;
  68. SIZ=(int)sqrt(n);
  69. if((n-1)/SIZ+1>300)SIZ=350;
  70. for(int i=1;i<=n;i++)
  71. v[i]=read();
  72. for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;
  73. for(int i=1;i<=n;i++)
  74. g[bl[i]][v[i]]++;
  75. for(int i=1;i<=bl[n];i++)
  76. for(int j=1;j<=n;j++)
  77. g[i][j]+=g[i-1][j];
  78. for(int i=1;i<=bl[n];i++)pre(i);
  79. for(int i=1;i<=m;i++)
  80. {
  81. int a=read(),b=read();
  82. a=(a+ans)%n+1;b=(b+ans)%n+1;
  83. if(a>b)swap(a,b);
  84. printf("%d\n",ans=query(a,b));
  85. }
  86. return 0;
  87. }


树分块

板子&原理

建树
在原树上遍历并暴力建块(判断父亲块是否满块),暴力记录每块内容,并在块间连单向边,构成“块树”。
点修改
只更新所在块内容。
加点
只判断父亲块是否满而选择新建块还是和父亲搞基
子树询问
和根在同一块的单独统计,否则可以大力在“块树”上成块统计。
  1. /*
  2. Author:Scarlet
  3. */
  4. void dfs(int x)//“分块”处理,可能不是最快的姿势,另一种可以看树上莫队第一题
  5. {
  6. if(blo[bel[fa[x]]].size==block)//块满
  7. blo[bel[x]=++cnt].ist(a[x]),AE(bidx,bel[fa[x]],cnt);//新开一块并和父亲块连(单向)边
  8. else
  9. blo[bel[x]=bel[fa[x]]].ist(a[x]);//在原块内加入
  10. for(int i=idx[x];i;i=nxt[i])//遍历原树
  11. if(to[i]!=fa[x])
  12. fa[to[i]]=x,dfs(to[i]);
  13. }
  14. void BDFS(int x,int y)
  15. {
  16. //块内点统计
  17. for(int i=bidx[x];i;i=nxt[i])
  18. BDFS(to[i],y);//遍历相邻的块,因为是单向的而且处理的是子树问题所以只要无脑遍历就行了。
  19. }
  20. void DFS(int x,int y)//求解
  21. {
  22. //块外点统计
  23. for(int i=idx[x];i;i=nxt[i])//遍历原树
  24. if(to[i]!=fa[x])
  25. if(bel[to[i]]==bel[x])//在根所在的块内要单独统计
  26. DFS(to[i],y);
  27. else
  28. BDFS(bel[to[i]],y);//不在块内的就可以成块统计了
  29. }
  30. //调用:
  31. dfs(1);//构树
  32. blo[bel[x]].mdf(...);//对点x修改
  33. AE(idx,x,n);fa[n]=x;//新建点的实力伪代码
  34. if(x块满)新块加入n,x块->n块;else x块加入n;
  35. DFS(x,...);//对x的子树查询

大概只有一类题:

(在线)在树上维护XJB玩意儿。

大力出奇迹。


BZOJ 3720: Gty的妹子树

树分块板子题,也是板子来源..
在板子里讲得很清楚了w

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 30300
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline int read()
  10. {
  11. int x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. struct poi
  17. {
  18. int a[210],size;
  19. void ist(int x)//
  20. {
  21. ++size;
  22. int i=size;
  23. for(;i>1&&a[i-1]>x;i--)a[i]=a[i-1];
  24. a[i]=x;
  25. }
  26. void mdf(int x,int y)//
  27. {
  28. int t=lower_bound(a+1,a+size+1,x)-a;
  29. for(;t<size&&a[t+1]<y;t++)a[t]=a[t+1];
  30. for(;t>1&&a[t-1]>y;t--)a[t]=a[t-1];
  31. a[t]=y;
  32. }
  33. int qry(int x)//
  34. {
  35. int t=upper_bound(a+1,a+size+1,x)-a;
  36. return size-t+1;
  37. }
  38. }blo[10100];
  39. #define AE(idx,u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  40. int idx[maxn*2],bidx[maxn],nxt[maxn*4],to[maxn*4],Si=1;
  41. int a[maxn*2],fa[maxn*2],bel[maxn*2];
  42. int n,m,block,ans,cnt;
  43. void dfs(int x)
  44. {
  45. if(blo[bel[fa[x]]].size==block)
  46. blo[bel[x]=++cnt].ist(a[x]),AE(bidx,bel[fa[x]],cnt);
  47. else
  48. blo[bel[x]=bel[fa[x]]].ist(a[x]);
  49. for(int i=idx[x];i;i=nxt[i])
  50. if(to[i]!=fa[x])fa[to[i]]=x,dfs(to[i]);
  51. }
  52. void BDFS(int x,int y)
  53. {
  54. ans+=blo[x].qry(y);
  55. for(int i=bidx[x];i;i=nxt[i])BDFS(to[i],y);
  56. }
  57. void DFS(int x,int y)
  58. {
  59. if(a[x]>y)++ans;
  60. for(int i=idx[x];i;i=nxt[i])
  61. if(to[i]!=fa[x])
  62. if(bel[to[i]]==bel[x])DFS(to[i],y);
  63. else BDFS(bel[to[i]],y);
  64. }
  65. int main()
  66. {
  67. n=read();
  68. for(int i=1,x,y;i<n;i++)
  69. x=read(),y=read(),AE(idx,x,y),AE(idx,y,x);
  70. for(int i=1;i<=n;i++)
  71. a[i]=read();
  72. block=(int)(sqrt(n)+1e-7);
  73. dfs(1);
  74. m=read();
  75. for(;m--;)
  76. {
  77. int p=read(),x=read(),y=read();
  78. x^=ans,y^=ans;
  79. if(p==0)ans=0,DFS(x,y),printf("%d\n",ans);
  80. else if(p==1)blo[bel[x]].mdf(a[x],y),a[x]=y;
  81. else
  82. {
  83. a[++n]=y;AE(idx,x,n);fa[n]=x;
  84. if(blo[bel[x]].size==block)
  85. blo[bel[n]=++cnt].ist(y),AE(bidx,bel[x],cnt);
  86. else
  87. blo[bel[n]=bel[x]].ist(y);
  88. }
  89. }
  90. return 0;
  91. }

BZOJ 1086: [SCOI2005]王室联邦

PoPoQQQ:《手把手教你树分块系列》

简单来说就是用一遍dfs实现自下而上的贪心
(以下来自hzwer)

一个省至少要有B,如果子树大小超过B,直接子树划个省,根为省会
。。。
剩余的部分小于B的话随便扔哪都是合法的吧

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 1005
  6. #define maxm 2010
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. int n,B,top,pro;
  18. #define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  19. int idx[maxn],nxt[maxm],to[maxm],Si=1;
  20. int q[maxn],size[maxn],belong[maxn],cap[maxn];
  21. void dfs(int x,int fa)
  22. {
  23. q[++top]=x;
  24. for(int i=idx[x];i;i=nxt[i])
  25. if(to[i]!=fa)
  26. {
  27. dfs(to[i],x);
  28. if(size[x]+size[to[i]]>=B)
  29. {
  30. size[x]=0;cap[++pro]=x;
  31. while(q[top]!=x)
  32. belong[q[top--]]=pro;
  33. }
  34. else size[x]+=size[to[i]];
  35. }
  36. size[x]++;
  37. }
  38. void paint(int x,int fa,int c)
  39. {
  40. if(belong[x])c=belong[x];else belong[x]=c;
  41. for(int i=idx[x];i;i=nxt[i])
  42. if(to[i]!=fa)
  43. paint(to[i],x,c);
  44. }
  45. int main()
  46. {
  47. n=read();B=read();
  48. if(n<B)return puts(""),0;
  49. for(int i=1,u,v;i<n;i++)
  50. u=read(),v=read(),AE(u,v),AE(v,u);
  51. dfs(1,0);
  52. if(!pro)cap[++pro]=1;
  53. paint(1,0,pro);
  54. printf("%d\n",pro);
  55. for(int i=1;i<=n;i++)printf("%d ",belong[i]);puts("");
  56. for(int i=1;i<=pro;i++)printf("%d ",cap[i]);
  57. return 0;
  58. }

咦...树分块好像没有会做的题目了?
没智商可减.jpg


膜队


一般莫队

板子&&原理

序列上的莫队一般是先维护一个区间的答案(一般来说这个维护起来十分simple),再通过对离线询问的特殊排序,做到均摊的高妙复杂度。

相信直接看上面一段都看不懂。

  1. inline bool cmp(const poi &a,const poi &b){return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;}//对询问排序
  2. for(int i=1,L=1,R=0;i<=m;i++)
  3. {
  4. for(;R<Q[i].r;)ins(a[++R]);
  5. for(;L>Q[i].l;)ins(a[--L]);
  6. for(;R>Q[i].r;)del(a[R--]);
  7. for(;L<Q[i].l;)del(a[L++]);
  8. ans[Q[i].i]=//计算答案
  9. }

是不是感觉这个算法强无敌?


BZOJ 3585: mex

先离线套个莫队冷静以下,然后问题就变成了如何快速求mex。

考虑到莫队转移,计算的特性,明显我们希望有一个插入,查询的数据结构,这样可以把复杂度降到

还能怎么办?分块!

对权值分块,记录每个块中数字出现个数以及是否已满。
插入、删除:找到所在块,cnt更新,判断size,
询问:找到第一个未满的块,在块内查询,
没了?没了。。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 200100
  6. #define maxm 450
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. struct poi{int l,r,i;}Q[maxn];
  18. int a[maxn],bel[maxn],f[maxn],ba[maxm],ans[maxn];
  19. int l[maxm],r[maxm];
  20. int n,m,SIZ;
  21. inline bool cmp(const poi &a,const poi &b){return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;}
  22. void ins(int x)
  23. {
  24. if(x>n)return;
  25. if(!f[x]++)ba[bel[x]]++;
  26. }
  27. void del(int x)
  28. {
  29. if(x>n)return;
  30. if(!--f[x])ba[bel[x]]--;
  31. }
  32. int qry()
  33. {
  34. if(!f[0])return 0;
  35. int i;
  36. for(i=1;l[i];i++)if(ba[i]!=r[i]-l[i]+1)break;
  37. for(int j=l[i];j<=r[i];j++)if(!f[j])return j;
  38. return n;
  39. }
  40. int main()
  41. {
  42. n=read(),m=read();
  43. SIZ=(int)(sqrt(n)+1e-7);
  44. for(int i=1;i<=n;i++)bel[i]=(i-1)/SIZ+1,a[i]=read();
  45. for(int i=1;(i-1)*SIZ+1<=n;i++)
  46. l[i]=(i-1)*SIZ+1,r[i]=min(i*SIZ,n);
  47. for(int i=1,x,y;i<=m;i++)x=read(),y=read(),Q[i]=(poi){x,y,i};
  48. sort(Q+1,Q+1+m,cmp);
  49. for(int i=1,L=1,R=0;i<=m;i++)
  50. {
  51. for(;R<Q[i].r;)ins(a[++R]);
  52. for(;L>Q[i].l;)ins(a[--L]);
  53. for(;R>Q[i].r;)del(a[R--]);
  54. for(;L<Q[i].l;)del(a[L++]);
  55. ans[Q[i].i]=qry();
  56. }
  57. for(int i=1;i<=m;i++)//我m打成n也A了= =
  58. printf("%d\n",ans[i]);
  59. return 0;
  60. }

当然这道题有十分优秀的树状数组离线主席树在线算法然而并不在讨论范围之中

当你点进hzwer的BIT题解时发现他并没有写BIT,反而是写了一个奇慢无比的线段树然后想来把我批判一番时,那么抱歉在下已经用这个算法艹进第一页了


BZOJ 3809: Gty的二逼妹子序列

还是十分simple的一道题,一模一样的处理吧。
块间枚举、边角料枚举。
时限挺宽的,卡个毛线常数啊。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100100
  6. #define maxm 350
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. struct poi{int l,r,a,b,i;}Q[1000100];
  18. int a[maxn],bel[maxn],f[maxn],ba[maxm],ans[1000100];
  19. int l[maxm],r[maxm];
  20. int n,m,SIZ;
  21. inline bool cmp(const poi &a,const poi &b){return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;}
  22. void ins(int x){if(!f[x]++)ba[bel[x]]++;}
  23. void del(int x){if(!--f[x])ba[bel[x]]--;}
  24. int qry(int a,int b)
  25. {
  26. int ans=0;
  27. if(bel[a]==bel[b]){for(int i=a;i<=b;i++)if(f[i])ans++;}
  28. else
  29. {
  30. for(int i=a;i<=r[bel[a]];i++)if(f[i])ans++;
  31. for(int i=l[bel[b]];i<=b;i++)if(f[i])ans++;
  32. for(int i=bel[a]+1;i<bel[b];i++)ans+=ba[i];
  33. }
  34. return ans;
  35. }
  36. int main()
  37. {
  38. n=read(),m=read();
  39. SIZ=(int)(sqrt(n)+1e-7);
  40. for(int i=1;i<=n;i++)bel[i]=(i-1)/SIZ+1,a[i]=read();
  41. for(int i=1;(i-1)*SIZ+1<=n;i++)
  42. l[i]=(i-1)*SIZ+1,r[i]=min(i*SIZ,n);
  43. for(int i=1,x,y,a,b;i<=m;i++)
  44. x=read(),y=read(),a=read(),b=read(),Q[i]=(poi){x,y,a,b,i};
  45. sort(Q+1,Q+1+m,cmp);
  46. for(int i=1,L=1,R=0;i<=m;i++)
  47. {
  48. for(;R<Q[i].r;)ins(a[++R]);
  49. for(;L>Q[i].l;)ins(a[--L]);
  50. for(;R>Q[i].r;)del(a[R--]);
  51. for(;L<Q[i].l;)del(a[L++]);
  52. ans[Q[i].i]=qry(Q[i].a,Q[i].b);
  53. }
  54. for(int i=1;i<=m;i++)
  55. printf("%d\n",ans[i]);
  56. return 0;
  57. }

树上莫队

板子&&原理

树上莫队一般是先求出一个dfs序,然后把树分块。就可以十分simple地维护一条链的答案。再通过对离线询问的特殊排序,做到均摊的高妙复杂度。

相信直接看上面一段都看不懂。

  1. inline bool cmp(const poi &a,const poi &b){return bel[a.u]==bel[b.u]?dfn[a.v]<dfn[b.v]:bel[a.u]<bel[b.u];}//对询问排序
  2. void rev(int x)
  3. {
  4. vis[x]^=1;
  5. if(vis[x]){p[c[x]]++;if(p[c[x]]==1)upd();}
  6. else{p[c[x]]--;if(p[c[x]]==0)upd();}
  7. }
  8. void move(int u,int v)
  9. {
  10. for(;u^v;)
  11. if(dep[u]>dep[v])rev(u),u=fa[u][0];
  12. else rev(v),v=fa[v][0];
  13. }//爬
  14. for(int i=1;i<=m;i++)//main
  15. {
  16. move(q[i-1].u,q[i].u);
  17. move(q[i-1].v,q[i].v);
  18. //搞事情
  19. }

是不是感觉这个算法强无敌?
UPD:貌似通过拆点变成贡献+1-1的dfs序就可以直接上莫队了啊QAQ


BZOJ 3757: 苹果树

维护链上颜色数。。
暴力莫队啊QAQ。

BZOJ不能交了。
跑了5sRE安慰自己。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 50010
  6. #define maxm 100010
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. #define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  18. int idx[maxn],nxt[maxm],to[maxm],Si=1;
  19. int bin[20],n,m,ans,top,ind,blo,blonum,root;
  20. int res[maxm],p[maxn],fa[maxn][17],dep[maxn];
  21. int c[maxn],st[maxn],dfn[maxn],bel[maxn];
  22. bool vis[maxn];
  23. struct poi{int u,v,a,b,i;}q[maxm];
  24. inline bool cmp(const poi &a,const poi &b){return bel[a.u]==bel[b.u]?dfn[a.v]<dfn[b.v]:bel[a.u]<bel[b.u];}
  25. int dfs(int x)
  26. {
  27. int size=0;
  28. dfn[x]=++ind;
  29. for(int i=1;i<=16;i++)
  30. fa[x][i]=fa[fa[x][i-1]][i-1];
  31. for(int i=idx[x];i;i=nxt[i])
  32. if(to[i]!=fa[x][0])
  33. {
  34. dep[to[i]]=dep[x]+1;
  35. fa[to[i]][0]=x;
  36. size+=dfs(to[i]);
  37. if(size>=blo)//这里用的是hzwer的【1086】分块技巧,听说比PoPoQQQ写的那种(即树分块模板里的)要快
  38. {
  39. blonum++;
  40. for(int k=1;k<=size;k++)
  41. bel[st[top--]]=blonum;
  42. size=0;
  43. }
  44. }
  45. st[++top]=x;
  46. return size+1;
  47. }
  48. int lca(int x,int y)
  49. {
  50. if(dep[x]<dep[y])swap(x,y);
  51. for(int i=0,t=dep[x]-dep[y];bin[i]<=t;i++)
  52. if(t&bin[i])x=fa[x][i];
  53. if(x==y)return x;
  54. for(int i=16;i>=0;i--)
  55. if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
  56. return fa[x][0];
  57. }
  58. void rev(int x)
  59. {
  60. vis[x]^=1;
  61. if(vis[x]){p[c[x]]++;if(p[c[x]]==1)ans++;}
  62. else {p[c[x]]--;if(p[c[x]]==0)ans--;}
  63. }
  64. void move(int u,int v)
  65. {
  66. for(;u^v;)
  67. if(dep[u]>dep[v])rev(u),u=fa[u][0];
  68. else rev(v),v=fa[v][0];
  69. }
  70. int main()
  71. {
  72. freopen("w.in","r",stdin);
  73. bin[0]=1;
  74. for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
  75. n=read();m=read();
  76. blo=sqrt(n);
  77. for(int i=1;i<=n;i++)c[i]=read();
  78. for(int i=1,u,v;i<=n;i++)
  79. {
  80. u=read(),v=read();
  81. if(!u)root=v;else if(!v)root=u;
  82. else AE(u,v),AE(v,u);
  83. }
  84. dfs(root);
  85. blonum++;
  86. while(top)bel[st[top--]]=blonum;
  87. for(int i=1;i<=m;i++)
  88. {
  89. int u=read(),v=read(),a=read(),b=read();
  90. if(dfn[u]>dfn[v])swap(u,v);
  91. q[i]=(poi){u,v,a,b,i};
  92. }
  93. sort(q+1,q+1+m,cmp);
  94. int t=lca(q[1].u,q[1].v);
  95. move(q[1].u,q[1].v);
  96. rev(t);//因为是边链,所以怎么处理大家都懂得
  97. res[q[1].i]=ans;
  98. if(p[q[1].a]&&p[q[1].b]&&q[1].a!=q[1].b)res[q[1].i]--;
  99. rev(t);
  100. for(int i=2;i<=m;i++)
  101. {
  102. move(q[i-1].u,q[i].u);
  103. move(q[i-1].v,q[i].v);
  104. t=lca(q[i].u,q[i].v);
  105. rev(t);res[q[i].i]=ans;
  106. if(p[q[i].a]&&p[q[i].b]&&q[i].a!=q[i].b)res[q[i].i]--;
  107. rev(t);
  108. }
  109. for(int i=1;i<=m;i++)
  110. printf("%d\n",res[i]);
  111. return 0;
  112. }

带修莫队

板子&原理

带修莫队,就是带修改的莫队,同样适合序列上和树上。
考虑每次修改实际上就是时间推移,那么我们把询问带上时间戳,修改一下块的大小为就能在内跑了。

  1. void timeleap(int x,int y)//修改操作(好中二的名字)
  2. {
  3. if(vis[x])rev(x),C[x]=y,rev(x);
  4. else C[x]=y;
  5. }
  6. for(int j=q[i-1].t+1;j<=q[i].t;j++)
  7. timeleap(c[j].x,c[j].y);//时间跳跃
  8. for(int j=q[i-1].t;j>q[i].t;j--)
  9. timeleap(c[j].x,c[j].pre);

出题人好像只喜欢在树上带修= =

要上什么例题了大家都懂的哈。


BZOJ 3052: [wc2013]糖果公园

因为糖果是按序吃按序得分的,而且同样的糖果,123吃法和321的得分是一样的。那么就可以大力莫队了

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. #define maxm 200010
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. #define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  18. int idx[maxn],nxt[maxm],to[maxm],Si=1;
  19. LL V[maxn],W[maxn],C[maxn],pre[maxn],ans,res[maxn];
  20. int bin[20],n,m,top,ind,blo,blonum;
  21. int fa[maxn][17],dep[maxn],num[maxn];
  22. int st[maxn],dfn[maxn],bel[maxn];
  23. bool vis[maxn];
  24. struct poi{int x,y,t,i;}q[maxn];
  25. struct UUZ{int x,y,pre;}c[maxn];
  26. inline bool cmp(const poi &a,const poi &b)
  27. {
  28. if(bel[a.x]==bel[b.x]&&bel[a.y]==bel[b.y])return a.t<b.t;
  29. else if(bel[a.x]==bel[b.x])return bel[a.y]<bel[b.y];
  30. else return bel[a.x]<bel[b.x];
  31. }
  32. int dfs(int x)
  33. {
  34. int size=0;
  35. dfn[x]=++ind;
  36. for(int i=1;i<=16;i++)
  37. fa[x][i]=fa[fa[x][i-1]][i-1];
  38. for(int i=idx[x];i;i=nxt[i])
  39. if(to[i]!=fa[x][0])
  40. {
  41. dep[to[i]]=dep[x]+1;
  42. fa[to[i]][0]=x;
  43. size+=dfs(to[i]);
  44. if(size>=blo)
  45. {
  46. blonum++;
  47. for(int k=1;k<=size;k++)
  48. bel[st[top--]]=blonum;
  49. size=0;
  50. }
  51. }
  52. st[++top]=x;
  53. return size+1;
  54. }
  55. int lca(int x,int y)
  56. {
  57. if(dep[x]<dep[y])swap(x,y);
  58. for(int i=0,t=dep[x]-dep[y];bin[i]<=t;i++)
  59. if(t&bin[i])x=fa[x][i];
  60. if(x==y)return x;
  61. for(int i=16;i>=0;i--)
  62. if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
  63. return fa[x][0];
  64. }
  65. void rev(int x)
  66. {
  67. if(vis[x])ans-=W[num[C[x]]]*V[C[x]],num[C[x]]--;
  68. else num[C[x]]++,ans+=W[num[C[x]]]*V[C[x]];
  69. vis[x]^=1;
  70. }
  71. void timeleap(int x,int y)
  72. {
  73. if(vis[x])rev(x),C[x]=y,rev(x);
  74. else C[x]=y;
  75. }
  76. void move(int u,int v)
  77. {
  78. for(;u^v;)
  79. if(dep[u]>dep[v])rev(u),u=fa[u][0];
  80. else rev(v),v=fa[v][0];
  81. }
  82. int main()
  83. {
  84. bin[0]=1;
  85. for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
  86. n=read();m=read();int Q=read();
  87. blo=pow(n,2.0/3)*0.5;
  88. for(int i=1;i<=m;i++)V[i]=read();
  89. for(int i=1;i<=n;i++)W[i]=read();
  90. for(int i=1,u,v;i<n;i++)
  91. u=read(),v=read(),AE(u,v),AE(v,u);
  92. for(int i=1;i<=n;i++)pre[i]=C[i]=read();
  93. dfs(1);
  94. blonum++;
  95. while(top)bel[st[top--]]=blonum;
  96. int c1=0,c2=0;
  97. for(int i=1;i<=Q;i++)
  98. {
  99. int typ=read(),x=read(),y=read();
  100. if(!typ)
  101. c[++c1]=(UUZ){x,y,pre[x]},pre[x]=y;
  102. else
  103. {
  104. if(dfn[x]>dfn[y])swap(x,y);
  105. q[++c2]=(poi){x,y,c1,c2};
  106. }
  107. }
  108. sort(q+1,q+1+c2,cmp);
  109. for(int i=1;i<=q[1].t;i++)
  110. timeleap(c[i].x,c[i].y);
  111. move(q[1].x,q[1].y);
  112. int t=lca(q[1].x,q[1].y);
  113. rev(t);res[q[1].i]=ans;rev(t);
  114. for(int i=2;i<=c2;i++)
  115. {
  116. for(int j=q[i-1].t+1;j<=q[i].t;j++)
  117. timeleap(c[j].x,c[j].y);
  118. for(int j=q[i-1].t;j>q[i].t;j--)
  119. timeleap(c[j].x,c[j].pre);
  120. move(q[i-1].x,q[i].x);
  121. move(q[i-1].y,q[i].y);
  122. t=lca(q[i].x,q[i].y);
  123. rev(t);res[q[i].i]=ans;rev(t);
  124. }
  125. for(int i=1;i<=c2;i++)
  126. printf("%lld\n",res[i]);
  127. return 0;
  128. }

BZOJ 4129: Haruna’s Breakfast

树上求mex,不能再套路了吧。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 50010
  6. #define maxm 100010
  7. #define maxb 250
  8. using namespace std;
  9. typedef long long LL;
  10. #define G c=getchar()
  11. inline int read()
  12. {
  13. int x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. #define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  19. int idx[maxn],nxt[maxm],to[maxm],Si=1;
  20. int a[maxn];
  21. int bin[20],n,top,ind,blo,blonum;
  22. int fa[maxn][17],dep[maxn],num[maxn];
  23. int st[maxn],res[maxn],pre[maxn],dfn[maxn],bel[maxn];
  24. bool vis[maxn];
  25. struct poi{int x,y,t,i;}q[maxn];
  26. struct UUZ{int x,y,pre;}c[maxn];
  27. inline bool cmp(const poi &a,const poi &b)
  28. {
  29. if(bel[a.x]==bel[b.x]&&bel[a.y]==bel[b.y])return a.t<b.t;
  30. else if(bel[a.x]==bel[b.x])return bel[a.y]<bel[b.y];
  31. else return bel[a.x]<bel[b.x];
  32. }
  33. int dfs(int x)
  34. {
  35. int size=0;
  36. dfn[x]=++ind;
  37. for(int i=1;i<=16;i++)
  38. fa[x][i]=fa[fa[x][i-1]][i-1];
  39. for(int i=idx[x];i;i=nxt[i])
  40. if(to[i]!=fa[x][0])
  41. {
  42. dep[to[i]]=dep[x]+1;
  43. fa[to[i]][0]=x;
  44. size+=dfs(to[i]);
  45. if(size>=blo)
  46. {
  47. blonum++;
  48. for(int k=1;k<=size;k++)
  49. bel[st[top--]]=blonum;
  50. size=0;
  51. }
  52. }
  53. st[++top]=x;
  54. return size+1;
  55. }
  56. int lca(int x,int y)
  57. {
  58. if(dep[x]<dep[y])swap(x,y);
  59. for(int i=0,t=dep[x]-dep[y];bin[i]<=t;i++)
  60. if(t&bin[i])x=fa[x][i];
  61. if(x==y)return x;
  62. for(int i=16;i>=0;i--)
  63. if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
  64. return fa[x][0];
  65. }
  66. int f[maxn],ba[maxb],bb[maxn],SIZ,l[maxb],r[maxb];
  67. void rev(int x)
  68. {
  69. if(a[x]>n)return;
  70. if(vis[x])
  71. {
  72. if(!--f[a[x]])ba[bb[a[x]]]--;
  73. }
  74. else
  75. if(!f[a[x]]++)ba[bb[a[x]]]++;
  76. vis[x]^=1;
  77. }
  78. void timeleap(int x,int y)
  79. {
  80. if(vis[x])rev(x),a[x]=y,rev(x);
  81. else a[x]=y;
  82. }
  83. void move(int u,int v)
  84. {
  85. for(;u^v;)
  86. if(dep[u]>dep[v])rev(u),u=fa[u][0];
  87. else rev(v),v=fa[v][0];
  88. }
  89. int qry()
  90. {
  91. if(!f[0])return 0;
  92. int i;
  93. for(i=1;l[i];i++)if(ba[i]!=r[i]-l[i]+1)break;
  94. for(int j=l[i];j<=r[i];j++)if(!f[j])return j;
  95. return n;
  96. }
  97. int main()
  98. {
  99. bin[0]=1;
  100. for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
  101. n=read();int Q=read();
  102. SIZ=(int)(sqrt(n)+1e-7);
  103. blo=pow(n,2.0/3)*0.5;
  104. for(int i=1;i<=n;i++)bb[i]=(i-1)/SIZ+1,pre[i]=a[i]=read();
  105. for(int i=1;(i-1)*SIZ+1<=n;i++)
  106. l[i]=(i-1)*SIZ+1,r[i]=min(i*SIZ,n);
  107. for(int i=1,u,v;i<n;i++)
  108. u=read(),v=read(),AE(u,v),AE(v,u);
  109. dfs(1);
  110. blonum++;
  111. while(top)bel[st[top--]]=blonum;
  112. int c1=0,c2=0;
  113. for(int i=1;i<=Q;i++)
  114. {
  115. int typ=read(),x=read(),y=read();
  116. if(!typ)
  117. c[++c1]=(UUZ){x,y,pre[x]},pre[x]=y;
  118. else
  119. {
  120. if(dfn[x]>dfn[y])swap(x,y);
  121. q[++c2]=(poi){x,y,c1,c2};
  122. }
  123. }
  124. sort(q+1,q+1+c2,cmp);
  125. for(int i=1;i<=q[1].t;i++)
  126. timeleap(c[i].x,c[i].y);
  127. move(q[1].x,q[1].y);
  128. int t=lca(q[1].x,q[1].y);
  129. rev(t);res[q[1].i]=qry();rev(t);
  130. for(int i=2;i<=c2;i++)
  131. {
  132. for(int j=q[i-1].t+1;j<=q[i].t;j++)
  133. timeleap(c[j].x,c[j].y);
  134. for(int j=q[i-1].t;j>q[i].t;j--)
  135. timeleap(c[j].x,c[j].pre);
  136. move(q[i-1].x,q[i].x);
  137. move(q[i-1].y,q[i].y);
  138. t=lca(q[i].x,q[i].y);
  139. rev(t);res[q[i].i]=qry();rev(t);
  140. }
  141. for(int i=1;i<=c2;i++)
  142. printf("%d\n",res[i]);
  143. return 0;
  144. }

数论加速

从丧心病狂的分块莫队过渡到了这儿。
没错,我只是想做几道数论题冷静一下。


分块计算

板子&原理

大家都知道最多有个取值。
那么只要把个取值出现了几次搞一搞就好了。

  1. for(ans=0,i=1;i<=n&&i<=m;i=j+1)//单指标求和
  2. {
  3. j=n/(n/i);//到块尾
  4. ans+=(j-i+1)*(n/i);
  5. }

BZOJ 4407: 于神之怒加强版

题解:From Claris


,则的狄利克雷卷积。
对于的计算,质数时直接快速幂,质数的幂递推计算,其它数可以通过线性筛得到。
对于每次询问,分块求和即可。

时间复杂度

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define N 5000001
  6. #define mod 1000000007
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. inline int Pow(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)t=1LL*t*a%mod;return t;}
  18. int T,n,m,k,tot,p[N],f[N],g[N],F[N],ans;bool v[N];
  19. int main()
  20. {
  21. T=read(),k=read();
  22. F[1]=1;
  23. for(int i=2;i<N;i++)
  24. {
  25. if(!v[i])f[i]=Pow(i,k),g[i]=i,F[i]=f[i]-1,p[tot++]=i;
  26. for(int j=0;j<tot&&i*p[j]<N;j++)
  27. {
  28. v[i*p[j]]=1;
  29. if(i%p[j])
  30. {
  31. g[i*p[j]]=p[j];
  32. F[i*p[j]]=1LL*F[i]*F[p[j]]%mod;
  33. }
  34. else
  35. {
  36. g[i*p[j]]=g[i]*p[j];
  37. F[i*p[j]]=g[i]!=i?1LL*F[i/g[i]]*F[g[i]*p[j]]%mod:1LL*F[i]*f[p[j]]%mod;
  38. break;
  39. }
  40. }
  41. }
  42. for(int i=2;i<N;i++)F[i]=(F[i-1]+F[i])%mod;
  43. for(int i,j;T--;)
  44. {
  45. n=read(),m=read();
  46. for(ans=0,i=1;i<=n&&i<=m;i=j+1)
  47. {
  48. j=min(n/(n/i),m/(m/i));
  49. ans=(1LL*(F[j]-F[i-1]+mod)*(n/i)%mod*(m/i)+ans)%mod;
  50. }
  51. printf("%d\n",ans);
  52. }
  53. return 0;
  54. }

分块打表

原理

没什么好说的,大块答案记录,边角料暴力


BZOJ 3798: 特殊的质数

题意:求中能被表示乘两数平方和的质数个数

懒癌


POJ 2689: Prime Distance加强

题意:在中找出距离相距最近和最远的两个相邻质数,

先假设大家都会做原题..
好,那么大家都会做加强版了。

块,每块大小用std跑出块内答案,记录首尾质数。边角料一样用std跑,块间XJB合并一下..

我TM就是个天才


询问分类


什么是询问分类?
就是把询问分成两类(或更多),由每一类的特性分别统计答案获得全局较低复杂度。


经典题 三元环的个数

题意:给定一个个点,条边的简单图,求三元环的个数,

当点的度不足时,称为轻点,否则为重点。
显然重点的数目不超过个,考虑枚举其中三个点直接统计,复杂度
又轻点的出边不足,可以枚举两条出边判断三个点是否为三元环,每条边被枚举了次。复杂度
总复杂度,十分优秀。

找不到OJ中有这道题啊。


BZOJ 2506: calc

题意:给一个长度为的非负整数序列。现有个询问,每次询问给出,问满足的值的个数。

离线,询问拆分并分成两类

前者可以用f1[i][j]表示加入的元素对i取模余数为j的个数
后者用f2[i]表示大小为i的数的个数,因为只要将f[k],f[k+p],f[k+2*p]……最多个数相加即可

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. #define maxp 10000
  7. #define sqrp 100
  8. using namespace std;
  9. typedef long long LL;
  10. #define G c=getchar()
  11. inline int read()
  12. {
  13. int x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. int f1[10010],f2[101][101],a[maxn],ans[maxn],tot;
  19. struct poi{int a,p,k,i;}q[maxn*2];
  20. inline bool cmp(const poi &a,const poi &b){return a.a<b.a;}
  21. int main()
  22. {
  23. int n=read(),m=read();
  24. for(int i=1;i<=n;i++)a[i]=read();
  25. for(int i=1,l,r,p,k;i<=m;i++)
  26. {
  27. l=read(),r=read(),p=read(),k=read();
  28. q[tot]=(poi){r,p,k,tot},tot++;
  29. q[tot]=(poi){l-1,p,k,tot},tot++;
  30. }
  31. sort(q,q+tot,cmp);int now=0;
  32. while(!q[now].a&&now<tot)now++;
  33. for(int i=1;i<=n;i++)
  34. {
  35. f1[a[i]]++;
  36. for(int p=1;p<=sqrp;p++)
  37. f2[p][a[i]%p]++;
  38. for(;q[now].a==i&&now<tot;now++)
  39. {
  40. poi& a=q[now];
  41. int re=0;
  42. if(a.p<=sqrp)re=f2[a.p][a.k];
  43. else
  44. for(int w=a.k;w<=maxp;w+=a.p)
  45. re+=f1[w];
  46. if(a.i&1)ans[a.i>>1]-=re;
  47. else ans[a.i>>1]+=re;
  48. }
  49. }
  50. for(int i=0;i<m;i++)
  51. printf("%d\n",ans[i]);
  52. return 0;
  53. }

HDU 4858: 项目管理

度大于的点叫重点,否则叫轻点。
把重点之间构一个“重图”。

轻点更新:更新邻居答案,
轻点查询:求所有邻居和,
重点更新:更新自己,
重点查询:把来自于轻点的答案加上“重图”上的邻居和,

完美解决

然而我这题模拟直接过我并没有写代码


结语

当我花一个星期写完这些文章的时候,发现分块和莫队都已经成为了时代的眼泪(HNOI:???)。
幸好数论求和这类JB玩意儿仍是现今的考点(但是你推不出公式并没有什么乱用)。
所以大家还是要从套路性根号算法中学到一些优化思想,再用到更加现代化的题目上去。

祝一题一题看到这里的选手省选暴力进队。


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注