专栏文章

题解：P14175 【MX-X23-T5】向死存魏

BBlackPanda
P14175题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhe40f
此快照首次捕获于
2025/12/02 02:27
3 个月前
此快照最后确认于
2025/12/02 02:27
3 个月前
查看原文
在线做法。
考虑维护每个值下一次出现的位置，记 nxt⁡(i,x)\operatorname{nxt}(i, x) 表示 ii 之后下一个 xx 出现的位置，记 ansians_i 表示 ii 之后最小的 jj 满足区间 [i,j][i,j] 包含 [1,V][1,V] 所有数，则 ansi=max⁡x=1Vnxt⁡(i,x)ans_i = \max\limits_{x=1}^{V}\operatorname{nxt}(i, x)。
那么对于操作三，我们存一下每个数出现的位置，然后预处理出 nxtnxt 和 ansans 的值 ，如果有解答案就是 anslans_l。同理，如果 [1,V][1,V] 中的某个元素最后一次出现位置在 ll 之前，则 ll 后一定有数字没出现，无解。这里用 set 维护每个值最后出现的位置，每次判一下最后出现次数的最小值（也就是 *s.begin()）即可。
对于操作二，我们假设 xx 在操作前序列中最后一次出现的位置为 lstxlst_x，这是第 cntcnt 次操作二（已经插入了 cnt−1cnt-1 个数），则当前 xx 应该插到第 n+cntn + cnt 的位置。对于 i∈[lxtx+1,n+cnt]i\in [lxt_x + 1, n + cnt] ，其中间一定没有 xx 出现（lstxlst_x 为原序列 xx 最后出现的位置），要想完整找到 [1,V][1,V] 中所有数，至少在 n+cntn + cnt 位置或其之后，应更新 ansi=n+cntans_i=n+cnt。
对于操作一，在 xx 所有出现位置的序列中二分，找到第一个大于等于 ll 的前一个出现位置 ℓ′\ell'，以及第一个大于 rr 的位置 r′r'，由于 [l,r][l,r] 中所有 xx 被删掉了，所以 i∈[ℓ′+1,r′]i\in [\ell'+1, r'] 的 nxt⁡(x,i)\operatorname{nxt}(x,i) 都应更新为 r′r'，ansians_i 做一下 chmax⁡\operatorname{chmax} 即可。如果 rr 后面没有 xx 了，就把 ansians_i 临时更新成 n+cnt+1n+cnt+1，后面再次插入 xx 会将此处的值继续更新。最后把 xx 位置包含在 [l,r][l,r] 里的删掉即可。
ansans 是区间更新 max⁡\max ，单点查询，可以用线段树维护，总时间复杂度是 O(nlog⁡n)O(n\log n) 级别。
CPP
int n, m, V;
vector<int> pos[N];
multiset<int> lst;
int a[N];
int cnt;
struct Tree { // chmax
    int l, r;
    int maxv, tag;
    void Maintain(int _tag) {
        tag = max(_tag, tag);
        maxv = max(_tag, maxv);
    }
} tree[N << 3]; // (n + m) << 2
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void PushUp(int p) {
    tree[p].maxv = max(tree[ls(p)].maxv, tree[rs(p)].maxv);
}
void PushDown(int p) {
    tree[ls(p)].Maintain(tree[p].tag);
    tree[rs(p)].Maintain(tree[p].tag);
    tree[p].tag = 0;
}
void Build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r; tree[p].tag = 0;
    if (tree[p].l == tree[p].r) {
        tree[p].maxv = 0;
    } else {
        int mid = (tree[p].l + tree[p].r) >> 1;
        Build(ls(p), l + 0, mid);
        Build(rs(p), mid + 1, r);
        PushUp(p);
    }
}
void Change(int p, int l, int r, int d) {
    if (l > r) return;
    if (r < tree[p].l || tree[p].r < l) return;
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].Maintain(d);
    } else {
        PushDown(p);
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (l <= mid)Change(ls(p), l, r, d);
        if (mid < r) Change(rs(p), l, r, d);
        PushUp(p);
    }
}
int Ask(int p, int x) {
    if (tree[p].l == tree[p].r) {
        return tree[p].maxv;
    } else {
        PushDown(p);
        int mid = (tree[p].l + tree[p].r) >> 1;
        int res = -inf;
        if (x <= mid)res = max(res, Ask(ls(p), x));
        if (mid < x) res = max(res, Ask(rs(p), x));
        return res;
    }
}
/*====================*/
void Solve() {
    cin >> n >> m >> V;
    Build(1, 1, n + m);
    for (int i = 1; i <= V; i++) {
        pos[i].push_back(0);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= V; i++) {
        for (auto j = 1; j < pos[i].size(); j++)   Change(1, pos[i][j - 1] + 1, pos[i][j], pos[i][j]);
        lst.insert(pos[i].back());
    }
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int ll, rr, x; cin >> ll >> rr >> x;
            auto l = lower_bound(pos[x].begin(), pos[x].end(), ll); // >= l
            auto r = upper_bound(pos[x].begin(), pos[x].end(), rr); // > r
            auto nl = l, nr = r;
            r--; // 防止下面 *r 取到 end，r' 位置本身没有被影响到，可以不更新
            nl--; // 取到 l 前一个位置
            int maxn = (nr == pos[x].end()) ? n + cnt + 1 : *nr;
            Change(1, (*nl) + 1, *r, maxn);
            lst.erase(lst.find(pos[x].back()));
            pos[x].erase(l, nr); // 删掉 [l,r] 范围内的元素
            lst.insert(pos[x].back());
        } else if (op == 2) {
            int x; cin >> x;
            cnt++;
            Change(1, pos[x].back() + 1, n + cnt, n + cnt);
            lst.erase(lst.find(pos[x].back()));
            lst.insert(n + cnt);
            pos[x].push_back(n + cnt);
        } else {
            int l; cin >> l;
            if (l > *lst.begin()) cout << -1 << endl;
            else cout << Ask(1, l) << endl;
        }
    }
    return;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...