【题解】HNOI2018转盘

　　何学长口中所说的‘一眼题’……然而实际上出出来我大HN全省也只有一个人A……

　　首先我们需要发现一个性质：我们永远可以在最后一圈去标记所有的物品。倘若我们反复转圈，那么这完全是可以省下来的。所以我们破环为链，以\(S\) 物品作为第一个被访问的节点时所需要的时间就是 \( max(T_{x} - x) + S \)，其中 \( S <= x <= S + n - 1\)。问题转化为如何使用数据结构来维护这些值得最小值。注意到 \(T_{x} - x \)都只与 \(x\) 有关，我们就他将它们合为一个变量：\(A_{x} = T_{x} - x\)。由于 \(T_{x} == T_{x + n}\)，所以 \(A_{x} > A_{x +n}\) 。所以若 \(A_{x} = max(A_{j}) (S <= j <= S + n - 1)\)，那么 \(A_{x} = max(A_{j}) (S <= j <= 2 * n)\)。这里应该是一个启示吧，有时候观察数组的性质，不仅仅缩小范围是有效的，实际上扩大范围为前缀 / 后缀也一样是非常重要的一个方面。那么这个时候我们就发现：这实际上对于答案可能产生贡献的就是所有从后往前比任何一个元素都要大的 \(A_{x}\) 啦。

　　使用线段树我们可以维护这样的一个单调栈，由于我们已经固定了 \(A_{x}\)，我们只需要使得 \(S\) 最小即可。显然\(S\)尽量小就应该是 \(x\) 左侧第一个比它大的数的下标+1。使用线段树维护这个信息的最大值即可（楼房重建问题）。

　　其中 \(mx\) 维护区间内 \(A_{x}\) 的最大值，\(mn\) 维护区间内 \(A_{x} + S\) 的最小值， \(rec\) 记录区间内只考虑左边区间 & 右边区间最大值的贡献（但考虑右边对于左边的限制）。

#include <bits/stdc++.h>

using namespace std;

#define maxn 1000000

#define INF 999999999

int n, m, P, N, ans, T[maxn];

int mn[maxn], mx[maxn], rec[maxn];

int read()

{

    int x = , k = ;

    char c; c = getchar();

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

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

    return x * k;

}

int Query(int p, int l, int r, int K)

{

    if(l == r)

    {

        if(mx[p] > K) return min(mn[p], K + l + );

        else return INF;

    }

    int mid = (l + r) >> ;

    if(mx[p <<  | ] <= K) return Query(p << , l, mid, K);

    else return min(rec[p], Query(p <<  | , mid + , r, K));

}

void Push_Up(int p, int l, int r)

{

    int ls = p << , rs = p <<  | ;

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

    int mid = (l + r) >> ;

    mn[p] = min(rec[p] = Query(ls, l, mid, mx[rs]), mn[p <<  | ]);

}

void Build(int p, int l, int r)

{

    if(l == r)

    {

        mx[p] = T[l] - l; mn[p] = T[l];

        return;

    }

    int mid = (l + r) >> ;

    Build(p << , l, mid); Build(p <<  | , mid + , r);

    Push_Up(p, l, r);

}

void Update(int p, int l, int r, int x)

{

    if(l == r)

    {

        mx[p] = T[l] - l; mn[p] = T[l];

        return;

    }

    int mid = (l + r) >> ;

    if(x <= mid) Update(p << , l, mid, x);

    else Update(p <<  | , mid + , r, x);

    Push_Up(p, l, r);

}

int main()

{

    n = read(), m = read(), P = read(), N =  * n;

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

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

    Build(, , N);

    printf("%d\n", ans = min(mx[] + , rec[]) + n - );

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

    {

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

        if(P) x ^= ans, y ^= ans;

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

        Update(, , N, x); Update(, , N, x + n);

        printf("%d\n", ans = min(mx[] + , rec[]) + n - );

    }

    return ;

}

巴特西

【题解】HNOI2018转盘

最新文章

热门文章