[关闭]
@ysner 2018-04-21T16:22:12.000000Z 字数 2174 阅读 2526

[HNOI/AHOI2018]转盘

线段树 DP


题面

游戏规则复杂无法概述
(为数据规模,为修改数)

解析

10pts 算法

报告,我会无脑暴搜!
复杂度

20pts 算法

发现最优策略总可以化成只转一圈的形式?
于是每次转圈时干等即可。
复杂度

30pts 算法

我们需要把统计答案的过程归纳成一个式子。
经过yy,发现答案为
很难处理,弄掉一个


于是得式
化简ing

于是线段树维护一下就可以做到

40pts算法

很明显复杂度中的那个是性能瓶颈。
仔细观察式子,发现?可以玩了?
式子可以化为

但既然连线段树都打出来了,没人打这档分吧??

100pts 算法

那么维护时把也顺便维护一下不就得了,反正前面的结果都已经出来了。
首先维护每段区间的最大值,
然后在时,对于,找到最小的并储存下来,这个递归可以做到。
于是复杂度降到了

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define ls x<<1
  12. #define rs x<<1|1
  13. #define mid (l+r>>1)
  14. #define max(a,b) ((a>b)?a:b)
  15. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  16. #define fq(i,a,b) for(re int i=s;i>=b;i--)
  17. using namespace std;
  18. const int N=1e6+100;
  19. int n,m,p,a[N],ans,t[N<<2],mx[N<<2],mn[N<<2];
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. il int Query(re int x,re int l,re int r,re int k)
  30. {
  31. if(l==r) return l+max(mx[x],k);
  32. re int res=-2e9;
  33. if(mx[rs]<k) return min(Query(ls,l,mid,k),mid+1+k);
  34. return min(mn[x],Query(rs,mid+1,r,k));
  35. }
  36. il void Build(re int x,re int l,re int r)
  37. {
  38. if(l==r) {t[x]=mx[x]=a[l]-l;mn[x]=a[l];return;}
  39. Build(ls,l,mid);Build(rs,mid+1,r);
  40. mx[x]=max(mx[ls],mx[rs]);
  41. mn[x]=Query(ls,l,mid,mx[rs]);
  42. }
  43. il void Modify(re int x,re int l,re int r,re int p,re int k)
  44. {
  45. if(p==l&&p==r) {t[x]=mx[x]=k-l;mn[x]=k;return;}
  46. if(l==r) return;
  47. if(p<=mid) Modify(ls,l,mid,p,k);
  48. else Modify(rs,mid+1,r,p,k);
  49. mx[x]=max(mx[ls],mx[rs]);
  50. mn[x]=Query(ls,l,mid,mx[rs]);
  51. }
  52. int main()
  53. {
  54. n=gi();m=gi();p=gi();
  55. fp(i,1,n) a[i]=a[i+n]=gi();
  56. Build(1,1,n+n);
  57. printf("%d\n",ans=mn[1]+n-1);
  58. fp(i,1,m)
  59. {
  60. re int x=gi()^p*ans,y=gi()^p*ans;
  61. a[x]=a[x+n]=y;
  62. Modify(1,1,n+n,x,y);Modify(1,1,n+n,x+n,y);
  63. printf("%d\n",ans=mn[1]+n-1);
  64. }
  65. return 0;
  66. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注