[HNOI/AHOI2018]转盘

线段树 DP

题面

游戏规则复杂无法概述
($n$为数据规模，$m$为修改数）

• 对于$10pts$ $n\leq10,m\leq10$
• 对于$20pts$ $n\leq1000,m=0$
• 对于$30pts$ $n\leq100000,m=0$
• 对于$40pts$ $n\leq5000,m\leq5000$
• 对于$100pts$ $n\leq100000,m\leq100000$

解析

10pts 算法

报告，我会无脑暴搜！
复杂度$O(2^n*m)$

20pts 算法

发现最优策略总可以化成只转一圈的形式？
于是每次转圈时干等即可。
复杂度$O(n^2)$

30pts 算法

我们需要把统计答案的过程归纳成一个式子。
经过yy，发现答案为$min_{1\leq i\leq n}(max_{0\leq j\leq n-1}(t[i+j]-j+n-1))$
$i+j$很难处理，弄掉一个
$min_{1\leq i\leq n}(max_{i\leq j\leq i+n-1}(t[j]-j+i+n-1))$
设$x_j=t[j]-j$
于是得式$min_{1\leq i\leq n}(max_{i\leq j\leq i+n-1}(x_j+i+n-1))$
化简ing
$min_{1\leq i\leq n}(max_{i\leq j\leq i+n-1}x_j)+i+n-1$
于是线段树维护一下就可以做到$O(nmlogn)$了

40pts算法

很明显复杂度中的那个$n$是性能瓶颈。
仔细观察式子，发现$i\leq j$？可以玩$CDQ$了？
式子可以化为
$min_{1\leq i\leq n}(max_{i\leq j\leq i+n-1}x_j+i)+n-1$
但既然连线段树都打出来了，没人打这档分吧？？

100pts 算法

那么维护$max$时把$min$也顺便维护一下不就得了，反正$j$前面的结果都已经出来了。
首先维护每段区间$x_i$的最大值，
然后在$push$时，对于$i\in[l，mid]$，找到最小的$i+x_j$并储存下来，这个$O(logn)$递归可以做到。
于是复杂度降到了$O(mlog^2n)$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define mid (l+r>>1)
#define max(a,b) ((a>b)?a:b)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=s;i>=b;i--)
using namespace std;
const int N=1e6+100;
int n,m,p,a[N],ans,t[N<<2],mx[N<<2],mn[N<<2];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int Query(re int x,re int l,re int r,re int k)
{
  if(l==r) return l+max(mx[x],k);
  re int res=-2e9;
  if(mx[rs]<k) return min(Query(ls,l,mid,k),mid+1+k);
  return min(mn[x],Query(rs,mid+1,r,k));
}
il void Build(re int x,re int l,re int r)
{
  if(l==r) {t[x]=mx[x]=a[l]-l;mn[x]=a[l];return;}
  Build(ls,l,mid);Build(rs,mid+1,r);
  mx[x]=max(mx[ls],mx[rs]);
  mn[x]=Query(ls,l,mid,mx[rs]);
}
il void Modify(re int x,re int l,re int r,re int p,re int k)
{
  if(p==l&&p==r) {t[x]=mx[x]=k-l;mn[x]=k;return;}
  if(l==r) return;
  if(p<=mid) Modify(ls,l,mid,p,k);
  else Modify(rs,mid+1,r,p,k);
  mx[x]=max(mx[ls],mx[rs]);
  mn[x]=Query(ls,l,mid,mx[rs]);
}
int main()
{
  n=gi();m=gi();p=gi();
  fp(i,1,n) a[i]=a[i+n]=gi();
  Build(1,1,n+n);
  printf("%d\n",ans=mn[1]+n-1);
  fp(i,1,m)
    {
      re int x=gi()^p*ans,y=gi()^p*ans;
      a[x]=a[x+n]=y;
      Modify(1,1,n+n,x,y);Modify(1,1,n+n,x+n,y);
      printf("%d\n",ans=mn[1]+n-1);
    }
  return 0;
}