显然最优走法是先一直停在初始位置然后一次性走完一圈。将序列倍长后，相当于找一个长度为n的区间[l,l+n)，使其中ti+l+n-1-i的最大值最小。容易发现ti-i>ti+n-(i+n)，所以也就相当于是后缀最大值最小。设ti-i=ai，即要求min{l+max{al..2n}}+n-1 (l=1..n)。如果没有修改的话只要扫一遍就行了。

　　线段树看起来很难维护，考虑分块。每一块求出仅考虑该块的ai时上述值的前缀min和ai的后缀max。对于查询，从后往前考虑所选区间左端点在哪一块。如果该块某个位置出现了整个序列的后缀最大值，序列后面的部分就不会对该块之前位置的答案产生影响，可以直接使用之前求出的答案。于是根据后缀最大值将该块划分成两部分，后一部分由于max{ai}被固定为后缀最大值，当然选择尽量左的点时最优。修改时暴力重构块即可。块大小取sqrt(nlogn)时最优，为O(msqrt(nlogn))。没有卡常也在慢如狗的bzoj上只跑了11s。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

#define inf 2000000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,op,a[N],L[N],R[N],pos[N],mx[N],mn[N],block,num,ans=inf;

void build(int x)

{

    mx[R[x]]=a[R[x]];mn[R[x]]=R[x]+a[R[x]];

    for (int i=R[x]-;i>=L[x];i--)

    mn[i]=i+(mx[i]=max(mx[i+],a[i]));

    for (int i=L[x]+;i<=R[x];i++)

    mn[i]=min(mn[i-],mn[i]);

}

int query()

{

    int u=-inf,ans=inf;

    for (int i=*num;i>num;i--) u=max(u,mx[L[i]]);

    for (int i=num;i>=;i--)

    {

        int l=L[i],r=R[i],x=R[i]+;

        while (l<=r)

        {

            int mid=l+r>>;

            if (mx[mid]<=u) x=mid,r=mid-;

            else l=mid+;

        }

        ans=min(ans,x+u);if (x>L[i]) ans=min(ans,mn[x-]);

        u=max(u,mx[L[i]]);

    }

    return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5286.in","r",stdin);

    freopen("bzoj5286.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),op=read();block=sqrt(n*log(n+));num=(n-)/block+;

    for (int i=;i<=n;i++) a[i]=a[i+n]=read();

    for (int i=;i<=n*;i++) a[i]-=i;

    for (int i=;i<=num;i++)

    {

        L[i]=R[i-]+,R[i]=min(n,L[i]+block-);

        for (int j=L[i];j<=R[i];j++)

        pos[j]=i;

        build(i);

    }

    for (int i=num+;i<=*num;i++)

    {

        L[i]=R[i-]+,R[i]=min(*n,L[i]+block-);

        for (int j=L[i];j<=R[i];j++)

        pos[j]=i;

        build(i);

    }

    ans=query()+n-;cout<<ans<<endl;

    while (m--)

    {

        int x=read()^ans*op,y=read()^ans*op;

        a[x]=y-x,a[x+n]=y-x-n;build(pos[x]),build(pos[x+n]);

        printf("%d\n",ans=query()+n-);

    }

    return ;

}

　　事实上这个做法可以扩展到线段树上（其实完全没有任何相似的地方吧？）。考虑每个节点维护该区间的最大值和仅考虑该区间ai时左半部分的最优答案。只要解决如何合并两个区间就可以了。类似的，右边的区间可以直接返回答案，然后考虑左节点的右半部分和右节点最大值的大小，如果左节点较大，直接返回左节点的左半部分答案并递归右节点，否则递归左节点。于是复杂度即为O(nlog2n)。鬼知道我在干什么莫名其妙写了一晚上。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

#define inf 2000000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,op,a[N],ans=inf;

struct data{int l,r,max,ans;

}tree[N<<];

int query(int k,int mx)

{

    if (tree[k].l==tree[k].r) return tree[k].l+max(mx,tree[k].max);

    if (tree[k<<|].max>=mx) return min(tree[k].ans,query(k<<|,mx));

    else return min((tree[k].l+tree[k].r>>)++mx,query(k<<,mx));

}

void build(int k,int l,int r)

{

    tree[k].l=l,tree[k].r=r;

    if (l==r) {tree[k].max=a[l];return;}

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    tree[k].max=max(tree[k<<].max,tree[k<<|].max);

    tree[k].ans=query(k<<,tree[k<<|].max);

}

void modify(int k,int p,int x)

{

    if (tree[k].l==tree[k].r) {tree[k].max=x;return;}

    int mid=tree[k].l+tree[k].r>>;

    if (p<=mid) modify(k<<,p,x);

    else modify(k<<|,p,x);

    tree[k].max=max(tree[k<<].max,tree[k<<|].max);

    tree[k].ans=query(k<<,tree[k<<|].max);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5286.in","r",stdin);

    freopen("bzoj5286.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),op=read();

    for (int i=;i<=n;i++) a[i]=a[i+n]=read();

    for (int i=;i<=n*;i++) a[i]-=i;

    build(,,*n);

    ans=tree[].ans+n-;cout<<ans<<endl;

    while (m--)

    {

        int x=read()^ans*op,y=read()^ans*op;

        modify(,x,y-x),modify(,x+n,y-x-n);

        printf("%d\n",ans=tree[].ans+n-);

    }

    return ;

}

最新文章

  1. 【原创】开源Math.NET基础数学类库使用(08)C#进行数值积分
  2. log4j输出模板
  3. SpringFramework的简介
  4. CGCDSSQ
  5. Apache网页有时能访问，有时超时打不开
  6. vs2012编译出错“LC.exe”已退出解决方法
  7. asp.net连接oracle的问题及方法总结
  8. Ubuntu频率较高的操作
  9. 匹配html标签的正则式
  10. 在打包程序中自动安装SQL Server数据库 .
  11. VS生产的编辑方法和编辑窗体
  12. hdu1394 分治 or 线段树
  13. 创建线程时如果既传入了runnable对象，又继承thread重写了run方法，会执行的哪里的代码
  14. iOS-拍照后裁剪,不可拖动照片的问题
  15. luogu 1484\1792 种树 奇怪的贪心可反悔
  16. Linux文件检索
  17. CFG文件格式
  18. Bootstrap相关网站中简单的等待提醒
  19. Linux学习笔记之一及虚拟机的安装
  20. Vue2.1.7源码学习

热门文章

  1. 交换机 路由器 OSI7层模型
  2. lastIndexOf()
  3. 我在华为，软件测试人员在工作中如何运用Linux？
  4. svn图文教程-宋正河整理
  5. jsp servlet路径问题
  6. linux上网络问题
  7. 正确配置 debian squeeze apt 源
  8. Tree - Decision Tree with sklearn source code
  9. Django之Form
  10. Scrum Meeting 11.05