专栏文章

题解：CF1982F Sorting Problem Again

qqinsishi
CF1982F题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minijt51
此快照首次捕获于
2025/12/02 02:59
3 个月前
此快照最后确认于
2025/12/02 02:59
3 个月前
查看原文
省流：单侧递归线段树+线段树二分，复杂度 O(nlog⁡n+qlog⁡2n)O(n\log n + q \log^2n)。
我们在线段树上考虑维护：
区间最大值 max⁡\max，区间最小值 min⁡\min，假想排序区间 [ql,qr][ql, qr]。
单点修改很好做，区间极值也很好维护，关键考虑如何合并子区间的假想排序区间信息。
记当前的点是 PP，它的左右儿子分别为 L,RL,R。
显然，P.ql≤min⁡(L.ql,R.ql)P.ql \le \min(L.ql, R.ql)，P.qr≥max⁡(L.qr,R.qr)P.qr \ge \max(L.qr,R.qr)。
如果 L.max⁡>R.min⁡L.\max > R.\min，我们需要扩大 PP 的假想排序区间。
具体地，我们需要找到第一个大于 R.min⁡R.\min 的位置 xx，最后一个小于 L.min⁡L.\min 的位置 yy。
使得 P.ql←min⁡(P.ql,x)P.ql \leftarrow \min(P.ql, x)，P.qr←max⁡(P.qr,y)P.qr \leftarrow \max(P.qr, y)。
那么就可以将当前维护的区间的最小假想排序信息维护好。
至于寻找上面的位置 xx 和 yy，我们使用线段树二分即可。
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+10, inf = 1e9;
int a[N], n, q;

struct node {
    int ql, qr; // 修改的 ql 和 qr
    int min, max; // 区间最小值和最大值
}t[N<<2];

// 区间第一个 >v 的下标
int search1(int p, int l, int r, int v) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (t[p<<1].max > v) return search1(p<<1, l, mid, v);
    else return search1(p<<1|1, mid+1, r, v);
}

// 区间最后一个 <v 的下标
int search2(int p, int l, int r, int v) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (t[p<<1|1].min < v) return search2(p<<1|1, mid+1, r, v);
    else return search2(p<<1, l, mid, v);
}

void pushup(int p, int l, int r) {
    t[p].min = min(t[p<<1].min, t[p<<1|1].min);
    t[p].max = max(t[p<<1].max, t[p<<1|1].max);
    t[p].ql = min(t[p<<1].ql, t[p<<1|1].ql);
    t[p].qr = max(t[p<<1].qr, t[p<<1|1].qr);
    if (t[p<<1].max > t[p<<1|1].min) {
        int mid = l + r >> 1;
        t[p].ql = min(t[p].ql, search1(p<<1, l, mid, t[p<<1|1].min));
        t[p].qr = max(t[p].qr, search2(p<<1|1, mid+1, r, t[p<<1].max));
    }
}

void build(int p, int l, int r) {
    if (l == r) return t[p] = {inf, -inf, a[r], a[r]}, void();
    int mid = l + r >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    pushup(p, l, r);
}

void update(int p, int l, int r, int x, int v) {
    if (l == r) return t[p] = {inf, -inf, v, v}, void();
    int mid = l + r >> 1;
    if (x <= mid) update(p<<1, l, mid, x, v);
    else update(p<<1|1, mid+1, r, x, v);
    pushup(p, l, r);
}

void print() {
    if (t[1].ql == inf && t[1].qr == -inf) cout << "-1 -1\n";
    else cout << t[1].ql << ' ' << t[1].qr << '\n';
}

void solve() {
    cin >> n;
    for (int i=1; i<=n; ++i) cin >> a[i];
    build(1, 1, n);
    print();
    cin >> q;
    while (q--) {
        int x, v;
        cin >> x >> v;
        update(1, 1, n, x, v);
        print();
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

评论

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

正在加载评论...