主要思路

第一次做到线段树维护单调栈的题，来写一写博客。

首先这个题求的就是 \(ans = \min_{i \in [n, 2n)} \max_{j \in [i – n + 1, i]} a_j + i – j\)，换一下就是 \(ans = (\min_{i \in [1, n)} \max_{j \in [i, i + n – 1]} a_j + i – j) + n – 1\)。

我们可以考虑做 \(B_i = a_i – i\)，然后再去做 \(\min\) 值。然而这样复杂度还是很高。我们考虑静态的问题时，发现其实这题可以做到 \(\Theta(n)\)，因为这个其实用一个反着的（从右到左）单调栈就行了。

放到动态问题上，可以尝试用线段树去搞搞：合并的时候，先保留右子树的内容，然后尝试在左子树里进行二分，找到队尾即可。

代码

// P4425.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200, INF = 0x3f3f3f3f;

int n, m, typ, Ti[MAX_N], nodes[MAX_N << 2], tag[MAX_N << 2];

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

int query(int qx, int l, int r, int p)
{
    if (l == r)
        return nodes[p] > qx ? qx + l : INF;
    return nodes[rson] > qx ? min(tag[p], query(qx, mid + 1, r, rson)) : query(qx, l, mid, lson);
}

void pushup(int p, int l, int r)
{
    nodes[p] = max(nodes[lson], nodes[rson]);
    tag[p] = query(nodes[rson], l, mid, lson);
}

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(nodes[p] = Ti[l] - l, tag[p] = INF);
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p, l, r);
}

void update(int qx, int l, int r, int p, int val)
{
    if (l == r)
        return (void)(nodes[p] = val - l);
    if (qx <= mid)
        update(qx, l, mid, lson, val);
    else
        update(qx, mid + 1, r, rson, val);
    pushup(p, l, r);
}

#undef mid
#undef rson
#undef lson

int main()
{
    scanf("%d%d%d", &n, &m, &typ);
    for (int i = 1; i <= n; i++)
        scanf("%d", &Ti[i]);
    int lastans;
    build(1, n, 1), printf("%d\n", lastans = query(nodes[1] - n, 1, n, 1) + n);
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y), x ^= typ * lastans, y ^= typ * lastans;
        update(x, 1, n, 1, y);
        printf("%d\n", lastans = query(nodes[1] - n, 1, n, 1) + n);
    }
    return 0;
}