题解：CF2247D2 XOR Sorting (Hard Version)

· · 题解

挺好，休训许久刚复健就场了一道蓝题

简单观察

数组会被划分成一些连通块，因为可以间接交换，所以块长仅与 k 的 highbit 有关，意味着 k 为 2^x,x\in \N。

仔细看看不难发现，上述块长为 2^{k+1}，题目转化为了维护最短块长，使得不存在需要跨块交换的一组数。

考虑实现

“需要跨块交换的一组数”形式化讲就是逆序对，而由于题目自带的倍增性质，容易想到扔进线段树。

线段树维护逆序对很典了，维护 max min 在合并的时候比较判断即可，本题需在节点维护 ans，也即子树内最少多少的 k 能满足没有跨块逆序对。

考虑转移，k 在左右子树取 max，如果这一层出现了逆序对，那赋值为当前层的目标 k，如果补齐初始数组到 2^x，也即区间长度一半，这样比较好处理。

查询答案的时候，因为树里维护的就是答案，所以直接查树顶就完了。

遂粘线段树板子场掉这道题。

时间复杂度

建树 O(n)，单点修 O(\log n)，全局查 O(1)，总复杂度 O(n+q\log n)，10^6 的话，感觉不太像官解，但能过，赛时代码跑了 1s 左右。 :::info[赛时代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace DS {
class seg {
private:
    struct tree {
        int mi, mx;
        int ans;
        tree() {
            mi = LLONG_MAX;
            mx = LLONG_MIN;
            ans = 0;
        }
    };
    int n;
    int siz;
    vector<tree> tr;
    void pushup(int p, int l, int r) {
        tree &ls = tr[p << 1];
        tree &rs = tr[p << 1 | 1];
        tr[p].mi = min(ls.mi, rs.mi);
        tr[p].mx = max(ls.mx, rs.mx);
        tr[p].ans = max(ls.ans, rs.ans);
        int hlf = (r - l + 1) >> 1;
        if (ls.mx > rs.mi)
            tr[p].ans = max(tr[p].ans, hlf);
    }
    void build(int p, int l, int r, const vector<int> &a) {
        if (l == r) {
            if (l < n) {
                tr[p].mi = a[l];
                tr[p].mx = a[l];
            } else {
                tr[p].mi = LLONG_MAX;
                tr[p].mx = LLONG_MIN;
            }
            tr[p].ans = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid, a);
        build(p << 1 | 1, mid + 1, r, a);
        pushup(p, l, r);
    }
    void update(int p, int l, int r, int pos, int val) {
        if (l == r) {
            tr[p].mi = val;
            tr[p].mx = val;
            tr[p].ans = 0;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(p << 1, l, mid, pos, val);
        else
            update(p << 1 | 1, mid + 1, r, pos, val);
        pushup(p, l, r);
    }

public:
    seg() {
        n = 0;
        siz = 0;
    }
    seg(vector<int> &a) { init(a); }
    void init(const vector<int> &a) {
        n = a.size();
        siz = 1;
        while (siz < n)
            siz <<= 1;
        tr.assign(siz << 1, tree());
        build(1, 0, siz - 1, a);
    }
    void update(int pos, int val) { update(1, 0, siz - 1, pos, val); }
    int ans() const { return tr[1].ans; }
};
}
using namespace DS;
namespace yys_wys {
void work() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n);
        for (auto &tmp : a) {
            cin >> tmp;
        }
        seg seg(a);
        cout << seg.ans();
        while (q--) {
            int pos, x;
            cin >> pos >> x;
            seg.update(pos, x);
            cout << endl << seg.ans();
        }
        cout << endl;
    }
}
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    return yys_wys::work(), 0;
}

:::

后记

Easy Ver 写了不同做法，但是感觉完全不如线段树好理解，遂略过