[HNOI2018]转盘

给你一个 \(n\) 元环, 你可以在 \(0\) 时刻从任意一个位置出发, 每一秒可以选择往后或者留在原地每个点有个参数 \(T_i\) , 当你走到 \(i\) 的时间 \(t\ge T_i\) 时你就可以把 \(i\) 标记问你把整个环上的点都标记最小需要多长时间, 带修改 \(T_i\), 强制在线.

\(\text{Solution:}\)

只看题目比较难发现其中的性质，我们来手模一下。

比如 \(T = 1, 2, 5, 4, 5​\)

标记每个点的时间为 \(1, 2, 5, 6, 7\)

显然 \(3, 4, 5, 6, 7\) 也是一组合法解。

这启示我们如果从将题目转换一下，变成：

显然一直走会不会更差，如 \(3, 4, 5, 6, 7\) 不会比 \(1, 2, 5, 6, 7\) 差。

这下时间就是连续的，这也方便我们讨论。

---

再次简化：

在一个长度为 \(2n\) 的序列上（断环成链），从点 \(i\in[n,2n)\)出发

\[\forall j\in(1,2n],\\
t-(i-j) \ge T_j\\
\Rightarrow t \ge T_j+i - j\\
\Rightarrow t_{min}= max\{ T_j-j\}+i
\]

求 \(t_{min}\)

---

仔细观察式子：

考虑枚举 \(j\) 看哪些 \(i\) 满足i的后缀最大值为 \(a_j\) ，从后往前扫，扫到一个数就更新后缀最大值，然后 \(chkmin\) 。

这样扫描每次 O(n),复杂度不对，没有充分利用每次修该前的信息，于是我们考虑将没有影响的一部分合并，可以用线段树来实现。

线段树每个节点维护该区间的最大 \(a\) ，以及答案，

向上合并的时候是在左区间递归找满足条件的 \(i​\) ，往左还是往右找分类讨论一下，再选取最小的答案即可（比较难理解画一画，想一想）。

#include <set>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <assert.h>

#include <algorithm>

using namespace std;

#define LL long long

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define GO debug("GO\n")

inline int rint() {

    register int x = 0, f = 1; register char c;

    while (!isdigit(c = getchar())) if (c == '-') f = -1;

    while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));

    return x * f;

}

template<typename T> inline void chkmin(T &a, T b) { a > b ? a = b : 0; }

template<typename T> inline void chkmax(T &a, T b) { a < b ? a = b : 0; }

const int maxN = 2e5 + 10;

int n, m, q;

int ans[maxN * 4], mx[maxN * 4], T[maxN];

#define ls (x<<1)

#define rs (x<<1|1)

int query(int x, int l, int r, int y) {

    if (l == r) return l + max(mx[x], y);

    int mid = (l + r) >> 1;

    if (mx[rs] >= y) return min(ans[x], query(rs, mid + 1, r, y));

    else return min(mid + 1 + y, query(ls, l, mid, y));

}

void pu(int x, int l, int r) {

    mx[x] = max(mx[ls], mx[rs]);

    ans[x] = query(ls, l, (l + r) >> 1, mx[rs]);

}

void Build(int x, int l, int r) {

    if (l == r) {

        mx[x] = ans[x] = T[l] - l;

        return;

    }

    int mid = (l + r) >> 1;

    Build(ls, l, mid);

    Build(rs, mid + 1, r);

    pu(x, l, r);

}

void change(int x, int l, int r, int y) {

    if (l == r) {

        ans[x] = mx[x] = T[l] - l;

        return;

    }

    int mid = (l + r) >> 1;

    if (y <= mid) change(ls, l, mid, y);

    else change(rs, mid + 1, r, y);

    pu(x, l, r);

}

int main() {

#ifndef ONLINE_JUDGE

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

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

#endif

    n = rint(), m = rint(), q = rint();

    for (int i = 1; i <= n; ++ i)

        T[i] = T[i + n] = rint();

    Build(1, 1, n * 2);

    int lastans = ans[1] + n - 1;

    printf("%d\n", lastans);

    while (m --) {

        int x = rint(), y = rint();

        if (q) x ^= lastans, y ^= lastans;

        T[x] = T[x + n] = y;

        change(1, 1, 2 * n, x);

        change(1, 1, 2 * n, x + n);

        lastans = ans[1] + n - 1;

        printf("%d\n", lastans);

    }

}