[关闭]
@KirinBill 2017-10-11T07:14:53.000000Z 字数 7316 阅读 724

蒟蒻讲水题

讲义

目录


1.[BZOJ 2959] 长跑

题目大意:
给定个点,,支持加边操作,询问两点间每条边只能沿一个固定方向走所经过的路径上的点的点权和最大值(询问和操作总次数满足)。

思路

注意,由于LCT**常数巨大,两点连通性应用另一个并查集**维护,而不是LCT的find_rt()不然会T。

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. using std::swap;
  5. using std::queue;
  6. const int MAXN=1.5e5+5;
  7. int tmp[MAXN];
  8. struct node{
  9. int s[2],fa,w,sum;
  10. bool rev;
  11. };
  12. class UFset{
  13. private:
  14. int anc[MAXN];
  15. public:
  16. void init(int n){
  17. for(int i=1;i<=n;++i)
  18. anc[i]=i;
  19. }
  20. int find(int x){
  21. return anc[x]==x ? x:anc[x]=find(anc[x]);
  22. }
  23. void uni(int x,int y){anc[find(x)]=find(y);}
  24. };
  25. class LCT{
  26. private:
  27. bool vis[MAXN];
  28. node d[MAXN];
  29. UFset ufs,cnn;
  30. void upd(int u){
  31. d[u].sum=d[d[u].s[0]].sum+d[d[u].s[1]].sum+d[u].w;
  32. }
  33. void push_d(int u){
  34. if(!d[u].rev) return;
  35. d[d[u].s[0]].rev^=true;
  36. d[d[u].s[1]].rev^=true;
  37. swap(d[u].s[0],d[u].s[1]);
  38. d[u].rev=false;
  39. }
  40. bool is_rt(int u){
  41. int ufa=d[u].fa;
  42. return d[ufa].s[0]!=u && d[ufa].s[1]!=u;
  43. }
  44. void rot(int u){
  45. int ufa=d[u].fa;
  46. push_d(ufa),push_d(u);
  47. bool lr=d[ufa].s[1]==u;
  48. d[u].fa=d[ufa].fa;
  49. if(!is_rt(ufa))
  50. d[d[u].fa].s[d[d[u].fa].s[1]==ufa]=u;
  51. d[ufa].s[lr]=d[u].s[lr^1];
  52. d[d[ufa].s[lr]].fa=ufa;
  53. d[u].s[lr^1]=ufa;
  54. d[ufa].fa=u;
  55. upd(ufa),upd(u);
  56. }
  57. void spl(int u){
  58. push_d(u);
  59. int &ufa=d[u].fa,&ugfa=d[ufa].fa;
  60. while(!is_rt(u)){
  61. if(!is_rt(ufa)){
  62. if((d[ufa].s[0]==u)!=(d[ugfa].s[0]==ufa))
  63. rot(u);
  64. else rot(ufa);
  65. }
  66. rot(u);
  67. }
  68. }
  69. void acc(int u){
  70. for(int v=0;u;v=u,u=ufs.find(d[u].fa)){
  71. spl(u);
  72. d[u].s[1]=v;
  73. d[v].fa=u;
  74. upd(u);
  75. }
  76. }
  77. void be_rt(int u){
  78. acc(u),spl(u);
  79. d[u].rev^=true;
  80. }
  81. void spl_mge(int u,int v){
  82. be_rt(u),acc(v),spl(u);
  83. }
  84. void linkE(int u,int v){
  85. be_rt(u),d[u].fa=v;
  86. cnn.uni(u,v);
  87. }
  88. void mge_node(int u,int v){
  89. static queue<int> q;
  90. spl_mge(u,v);
  91. q.push(u);
  92. int now;
  93. while(q.size()){
  94. now=q.front();
  95. q.pop();
  96. ufs.uni(now,u);
  97. if(d[now].s[0])
  98. q.push(d[now].s[0]);
  99. if(d[now].s[1])
  100. q.push(d[now].s[1]);
  101. d[now].fa=d[now].s[0]=d[now].s[1]=0;
  102. }
  103. d[u].w=d[u].sum;
  104. }
  105. public:
  106. void init(int n){
  107. ufs.init(n),cnn.init(n);
  108. for(int i=1;i<=n;++i)
  109. d[i].sum=d[i].w=tmp[i];
  110. }
  111. void link(int u,int v){
  112. u=ufs.find(u),v=ufs.find(v);
  113. if(u==v) return;
  114. else if(cnn.find(u)!=cnn.find(v))
  115. linkE(u,v);
  116. else mge_node(u,v);
  117. }
  118. void mdf(int u,int w){
  119. int now_u=ufs.find(u);
  120. be_rt(now_u);
  121. d[now_u].w+=w-tmp[u];
  122. tmp[u]=w;
  123. upd(now_u);
  124. }
  125. int qry(int u,int v){
  126. u=ufs.find(u),v=ufs.find(v);
  127. if(u==v) return d[u].w;
  128. else if(cnn.find(u)!=cnn.find(v))
  129. return -1;
  130. spl_mge(u,v);
  131. return d[u].sum;
  132. }
  133. }T;
  134. int main(){
  135. int n,m;
  136. scanf("%d%d",&n,&m);
  137. for(int i=1;i<=n;++i)
  138. scanf("%d",&tmp[i]);
  139. T.init(n);
  140. for(int i=1,p,a,b;i<=m;++i){
  141. scanf("%d%d%d",&p,&a,&b);
  142. if(p==1) T.link(a,b);
  143. else if(p==2) T.mdf(a,b);
  144. else printf("%d\n",T.qry(a,b));
  145. }
  146. return 0;
  147. }

2.[UOJ 164] V

题目大意:
给定一个个元素的序列,要求支持5种操作(次数满足):
1.把~每个元素加上
2.把~每个元素赋值为
3.把~每个元素赋值为
4.询问当前的值;
5.询问的历史最大值.

思路

注意:push_down()不能将叶节点下传,因为我们是用计算询问,不能把推没了...而且其中有一步和,是防止溢出!

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <utility>
  4. #include <climits>
  5. using std::max;
  6. using std::pair;
  7. const int MAXN=5e5+5;
  8. const long long INF=1e18;
  9. int tmp[MAXN];
  10. struct option{
  11. pair<long long,long long> his,now;
  12. void clear(){
  13. now=pair<long long,long long>(0,-INF);
  14. his=pair<long long,long long>(0,-INF);
  15. }
  16. void mge(const option &a){
  17. his.first=max(his.first,a.his.first+now.first);
  18. his.second=max(his.second,max(a.his.first+now.second,a.his.second));
  19. now.first=max(now.first+a.now.first,-INF);
  20. now.second=max(now.second+a.now.first,a.now.second);
  21. }
  22. };
  23. struct node{
  24. int ls,rs,lp,rp,w;
  25. option tag;
  26. };
  27. class segT{
  28. private:
  29. node d[MAXN<<2];
  30. void push_d(int u){
  31. d[d[u].ls].tag.mge(d[u].tag);
  32. d[d[u].rs].tag.mge(d[u].tag);
  33. d[u].tag.clear();
  34. }
  35. void build(int u,int l,int r){
  36. static int cnt=1;
  37. d[u].lp=l,d[u].rp=r;
  38. d[u].tag.clear();
  39. if(l==r){
  40. d[u].w=tmp[l];
  41. return;
  42. }
  43. int mid=l+r>>1;
  44. d[u].ls=++cnt;
  45. build(cnt,l,mid);
  46. d[u].rs=++cnt;
  47. build(cnt,mid+1,r);
  48. }
  49. void mdf(int u,int l,int r,const option &k){
  50. if(l<=d[u].lp && d[u].rp<=r){
  51. d[u].tag.mge(k);
  52. return;
  53. }
  54. push_d(u);
  55. int mid=d[u].lp+d[u].rp>>1;
  56. if(l<=mid) mdf(d[u].ls,l,r,k);
  57. if(r>mid) mdf(d[u].rs,l,r,k);
  58. }
  59. long long qry(int u,int pos,bool type){
  60. if(d[u].lp==d[u].rp){
  61. const pair<long long,long long> &tmp= type ? d[u].tag.now:d[u].tag.his;
  62. return max(d[u].w+tmp.first,tmp.second);
  63. }
  64. push_d(u);
  65. int mid=d[u].lp+d[u].rp>>1;
  66. if(pos<=mid) return qry(d[u].ls,pos,type);
  67. else return qry(d[u].rs,pos,type);
  68. }
  69. public:
  70. void build(int n){build(1,1,n);}
  71. void mdf(int l,int r,option &k){mdf(1,l,r,k);}
  72. long long qry(int pos,bool type){return qry(1,pos,type);}
  73. }T;
  74. int main(){
  75. int n,m;
  76. scanf("%d%d",&n,&m);
  77. for(int i=1;i<=n;++i)
  78. scanf("%d",&tmp[i]);
  79. T.build(n);
  80. option opt;
  81. for(int i=1,t,l,r,x;i<=m;++i){
  82. scanf("%d",&t);
  83. if(t<=3){
  84. scanf("%d%d%d",&l,&r,&x);
  85. if(t==1){
  86. opt.now=pair<long long,long long>(x,-INF);
  87. opt.his=pair<long long,long long>(x,-INF);
  88. }
  89. else if(t==2){
  90. opt.now=pair<long long,long long>(-x,0);
  91. opt.his=pair<long long,long long>(-x,0);
  92. }
  93. else{
  94. opt.now=pair<long long,long long>(-INF,x);
  95. opt.his=pair<long long,long long>(-INF,x);
  96. }
  97. T.mdf(l,r,opt);
  98. }
  99. else{
  100. scanf("%d",&x);
  101. printf("%lld\n",T.qry(x,t==4));
  102. }
  103. }
  104. return 0;
  105. }

3.[BZOJ 2956] 模积和

题目大意:
.

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::min;
  4. const int P=19940417,inv_6=3323403;
  5. int n,m,ans;
  6. inline int blk_solve(int x,int y){
  7. int ret=0;
  8. for(int l=1,r;l<=y;l=r+1){
  9. r=min(x/(x/l),y);
  10. ret=(ret+(long long)((long long)(l+r)*(r-l+1)>>1)%P*(x/l)%P)%P;
  11. }
  12. return ret;
  13. }
  14. inline long long sqr_sum(int r){
  15. return (long long)r*(r+1)%P*(r<<1|1)%P*inv_6%P;
  16. }
  17. int main(){
  18. scanf("%d%d",&n,&m);
  19. ans=((long long)n*n%P-blk_solve(n,n)+P)%P;
  20. ans=(long long)ans*(((long long)m*m%P-blk_solve(m,m)+P)%P)%P;
  21. ans=(ans-(long long)min(n,m)*n%P*m%P+P)%P;
  22. ans=(ans+(long long)n*blk_solve(m,min(n,m))%P)%P;
  23. ans=(ans+(long long)m*blk_solve(n,min(n,m))%P)%P;
  24. for(int l=1,r;l<=min(n,m);l=r+1){
  25. r=min(min(n/(n/l),m/(m/l)),min(n,m));
  26. ans=(ans-(long long)(n/l)%P*(m/l)%P*(sqr_sum(r)-sqr_sum(l-1)+P)%P+P)%P;
  27. }
  28. printf("%d",ans);
  29. return 0;
  30. }

题太水了,巨佬们不要D我orz...

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