P4425:[HNOI/AHOI2018]转盘 – 题解

主要思路

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

首先这个题求的就是 \(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;
}

发布者

kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注