题解：CF1982F Sorting Problem Again

fortyqin · 2025-10-24 16:35:16 · 题解

省流：单侧递归线段树+线段树二分，复杂度 O(n\log n + q \log^2n)。

我们在线段树上考虑维护：

区间最大值 \max，区间最小值 \min，假想排序区间 [ql, qr]。

单点修改很好做，区间极值也很好维护，关键考虑如何合并子区间的假想排序区间信息。

记当前的点是 P，它的左右儿子分别为 L,R。

显然，P.ql \le \min(L.ql, R.ql)，P.qr \ge \max(L.qr,R.qr)。

如果 L.\max > R.\min，我们需要扩大 P 的假想排序区间。

具体地，我们需要找到第一个大于 R.\min 的位置 x，最后一个小于 L.\min 的位置 y。

使得 P.ql \leftarrow \min(P.ql, x)，P.qr \leftarrow \max(P.qr, y)。

那么就可以将当前维护的区间的最小假想排序信息维护好。

至于寻找上面的位置 x 和 y，我们使用线段树二分即可。

#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;
}