（真的是动态动态规划，我没有口吃！！！）

1. 题目

传送门=￣ω￣=

（当然 BZOJ 传题真是十分不负责任的，可以去看洛谷传送门=￣ω￣=）

2. 题解

题面看了半天才看懂。。。真不知道写题面的大爷语文谁教的。。。

大概就是给你一个长度为 $n$的环，你任选环上一点作为起点，每次可以顺时针走一步，或者是呆在原地不动，每次花费 1 个单位时间。环上每个点都有一个权值 $T _ i$，如果你当前所在的点的权值小于等于你的当前所用时间，那么当前这个点就会被标记。要求最小化标记所有点的时间。

emmmm… 根据 benoble_大佬的启示，我们可以把题目转换成如下形式：

首先选定一个最终时间 $t$，每个物品会在 $T _ i$的时刻消失，你可以任选一个起点，每个单位时间可以逆时针走一步或者是呆着不动，要求访问到所有物品（消失了的物品无法访问），最小化这个 $t$

好的我们能二分答案了（逃

其实就是把问题反过来了

题目转化成这个形式以后显然就很棒棒了，因为这种情况下显然你会一直逆时针移动（停在原地不动一定不会更优）。

所以反过来，你在原问题里也肯定是选定某个起点，然后一直顺时针移动而不会停下（因为每个逆过来走的方案都有一个对应的顺着走的方案）

然后对于一直走转两圈，不如选择某一个起点等，然后等完了直接转一圈（也就是通过等待使得每个点的出现时间都大于等于到达该点时间）

这样就比较好办了。

设起点为 $s$，然后拆环为链（复制两遍，链的长度为 $2n$）‘

这样有以下式子：

$$Ans = min _ {s \in [1,n]} \{ max _ {i \in [s, s + n – 1]} [T _ i – (i – s)] \} + n – 1$$

其中 $i – s$表示从 $s$出发到达 $i$所用的时间，$T _ i – (i – s)$自然就是该点需要你在 $s$点至少等待的时间，取 $max$就是从 $s$出发需要等待的时间。

最后一个 $n – 1$表示转一圈所需要的时间。

为了简化式子我们设 $A _ i = T _ i – i$

则式子可以转化为：

$$Ans = min _ {s \in [1,n]} \{ max _ {i \in [s, s + n – 1]} (A _ i) + s \} + n – 1$$

然后因为 $A _ i = T _ i – i$，所以 $A _ i > A _ {i + n}$，所以可以放宽 $i$取值的范围：

$$Ans = min _ {s \in [1,n]} \{ max _ {i \in [s, 2n]} (A _ i) + s \} + n – 1$$

设满足 $A _ x \ge A _ i(x < i)$的最大的 $x$为 $pre _ i$

对于某个 $A _ i$，如果对于任意的 $j \in [i + 1, 2n]$，都有 $A _ i > A _ j$（也就是 $A _ i$为后缀最大值），那么区间 $[pre _ i + 1, i]$这个区间内最小的 $max _ {i \in [s, s + n – 1]} (A _ i) + s$就等于 $A _ i + i$

那么就用线段树维护序列 $A$，对于一个区间 $[l, r]$，我们维护其最大值 $mx$，再维护一个 $min _ {s \in [l, mid]} \{ max _ i \in [s, r](A _ i) + s \}$（其中 $mid=\frac {l + r} 2$）

第一个 $mx$很好维护，第二个东西怎么维护呢？

其实这里的思想有点类似于单调栈，我们等于用线段树维护了一个单调递减的单调栈，我们要做的是合并当前区间的左右子区间的单调栈。

那就用右子区间的队首元素 $A _ x$（也就是最大元素），到左子区间里查找到大于等于 $A _ x$且最靠右（下标最大，最靠近 $x$的）的元素 $A _ y$，那么 $s \in [y, mid]$的时候，后缀最大值就是 $A _ x$，能取到的最小答案就是 $A _ x + s$。

然后对于 $A _ y$左边的那些 $s \in [1, y – 1]$，则可以在查找 $A _ y$的时候由查找时所在的区间的左子区间的答案取 $min$得到。

这一段比较复杂，可以看下这段代码：

struct N {int l, r, mx, d;} e[NS << 2];

int cal(int mx, int a) // mx 是用来查找的 Ax，a 是当前节点
{
    //如果已经确定了 y，这里取 max(e[a].mx, mx) 是防止 Ay 不存在
    if (e[a].l == e[a].r) return e[a].l + max(e[a].mx, mx);
    //如果右子区间的最大值是大于 Ax，那么 Ay 在右子区间，然后顺手获取一波 Ay 左边的答案
    if (e[RS(a)].mx >= mx) return min(e[a].d, cal(mx, RS(a)));
    //否则 Ay 在左子区间，这里取 min 是因为左子区间可能没有数字比 Ax 小了
    return min(cal(mx, LS(a)), e[RS(a)].l + mx);
}

emmmmm… 好吧就讲到这里。。。赶紧放代码跑路啦 23333～

#include <bits/stdc++.h>

#define NS (200005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct N {int l, r, mx, d;} e[NS << 2];

int n, m, p, N, arr[NS];

int cal(int mx, int a)
{
    if (e[a].l == e[a].r) return e[a].l + max(e[a].mx, mx);
    if (e[RS(a)].mx >= mx) return min(e[a].d, cal(mx, RS(a)));
    return min(cal(mx, LS(a)), e[RS(a)].l + mx);
}

void pup(int a)
{
    e[a].mx = max(e[LS(a)].mx, e[RS(a)].mx);
    e[a].d = cal(e[RS(a)].mx, LS(a));
}

void Build(int l, int r, int a)
{
    e[a].l = l, e[a].r = r;
    if (l == r)
    {
        e[a].mx = arr[l], e[a].d = arr[l] + l;
        return;
    }
    int mid = ((l + r) >> 1);
    Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

void Update(int x)
{
    int a = 1;
    while (e[a].l < e[a].r)
        if (e[LS(a)].r >= x) a = LS(a);
        else a = RS(a);
    e[a].mx = arr[x], e[a].d = arr[x] + x;
    while (a >>= 1, a) pup(a);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(p), N = (n << 1);
    for (int i = 1; i <= n; i += 1) IN(arr[i]), arr[i + n] = arr[i];
    for (int i = 1; i <= N; i += 1) arr[i] -= i;
    Build(1, N, 1); int lst = e[1].d + n - 1, x, y; printf("%d\n", lst);
    while (m--)
    {
        IN(x), IN(y);
        if (p) x ^= lst, y ^= lst;
        arr[x] = y - x, arr[x + n] = y - x - n;
        Update(x), Update(x + n), printf("%d\n", lst = e[1].d + n - 1);
    }
    return 0;
}