2024牛客暑期多校训练营8 I Haitang and Ranking 题解

乱搞

看到 \(n=1e5\) ，时限3s，存在修改操作，很自然的想到根号分治。

考虑按照时间分治。对每 \(B\) 个交换统一处理， \(B\) 个交换最多有 \(2B\) 个元素改变状态，剩下都不变。那么只要对这 \(2B\) 元素内，暴力枚举，剩下的元素构建数据结构实现二维数点，平面内区间最值。

因为 \(a,b\) 是不变的，那么对于点 \((a,b)\) 一共有 \(n\) 个，预处理出每个点左下角的最大值，和右上角的最小值（经过变换后，也在左下角，所以数点只需要询问前缀最值，树状数组实现即可）。左下角的点都要小于自己，右上角的点都大于自己，那么这个点就是合法点。当每个点都是合法点的时候，即可输出 Yes 。如果不变的点内部已经不合法，那么这 \(B\) 个交换结束状态一定都是不合法的。时间复杂度 \(O(\frac{n}{B} \times n log(n))\) 。

考虑要改变状态的 \(2B\) 个点，对于不变的点，二维数点已经处理出是否合法，对于一样要改变的点。维护一个数组 \(err\) ，维护左下角的点有多少点比自己大。维护一个 \(cntok\) 为合法点数量，当 \(err=0\) 且对于不修改的点都成立时，\(cntok+1\) 。每次交换重新算交换点的 \(err\) ，和这个点对其他点的 \(err\) 影响即可，注意这两个点内部影响特判。时间复杂度 $ O(\frac{n}{B} B \times 2B) $ 。

总共的时间复杂度为 $ O(\frac{n^2}{B} log(n) + nB)$ ，取 \(B=\sqrt{n log(n)}\) 时最优，时间复杂度 \(O(n \sqrt{n log(n)})\) 。因为每个块交互元素可以到 \(2B\) 且多次循环，且树状数组常数小，所以代码设置块长偏大，这里设置 \(siz = 2000\) 。

#include <bits/stdc++.h>
#define ll long long
#define enl putchar('\n')
#define all(x) (x).begin(),(x).end()
#define debug(x) printf(" "#x":%d\n",x);
using namespace std;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
typedef pair<int, int> pii;
char buf[1 << 21], * p1 = buf, * p2 = buf, obuf[1 << 21], * o = obuf, of[35];
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1)res = res * a % mod; n >>= 1; a = a * a % mod; }return res; }
template <class T = int>inline T read() { T s = 0, f = 1; char c = gc(); for (; !isdigit(c); c = gc())if (c == '-')f = -1; for (; isdigit(c); c = gc())s = s * 10 + c - '0'; return s * f; }
inline void read(int* a, int n) { for (int i = 1; i <= n; ++i)a[i] = read(); }
inline int inal(char* s) { int n = 0; for (s[0] = gc(); !isalpha(s[0]); s[0] = gc()); for (; isalpha(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline void outd(auto* a, int n) { for (int i = 1; i <= n; ++i)printf("%d ", a[i]); enl; }
int n, m, q;

struct P { int operator()(const int& x, const int& y)const { return max(x, y); } };
struct PP { int operator()(const int& x, const int& y)const { return min(x, y); } };


template<class T, int bas>
struct BIT {
    T opt;
    int tr[MAXN], n;
    BIT() { n = MAXN - 1; }
    void setlim(int x) { n = x; }
    void clear() { memset(tr, bas, sizeof(tr)); }
    int lowbit(int x) { return x & -x; }
    void add(int x, int k) { for (; x <= n; x += lowbit(x))tr[x] = opt(tr[x], k); }
    int ask(int x) { int res = bas; for (; x; x -= lowbit(x))res = opt(res, tr[x]); return res; }
};


template<class T, int bas>
struct SMP : BIT<T, bas> {
    array<int, 3> pt[MAXN];
    array<int, 3>qry[MAXN];
    int ans[MAXN];
    int n, m;
    void clear() {
        n = m = 0;
        BIT<T, bas>::clear();
    }
    void addpt(int x, int y, int val) { pt[++n] = {x, y, val}; }
    void addqry(int x, int y, int id) { qry[++m] = {x, y, id}; }
    void work() {
        sort(pt + 1, pt + n + 1, [&](auto& a, auto& b) {return a[1] < b[1]; });
        sort(qry + 1, qry + m + 1, [&](auto& a, auto& b) {return a[1] < b[1]; });
        for (int i = 1, j = 1; i <= m; ++i) {
            while (j <= n && pt[j][1] <= qry[i][1])BIT<T, bas>::add(pt[j][0], pt[j][2]), ++j;
            ans[qry[i][2]] = BIT<T, bas>::ask(qry[i][0]);
        }
    }
};

SMP<P, 0> smp;
SMP<PP, inf> sm;

const int siz = 2000;
int a[MAXN], b[MAXN], c[MAXN], rk[MAXN];

vector<pii>opt;
bool vis[MAXN];

int err[MAXN], cntok;

void work() {
    memset(vis, 0, sizeof(vis)); smp.clear(); sm.clear();
    memset(err, 0, sizeof(err)); cntok = 0;

    for (auto& [x, y] : opt)
        vis[x] = vis[y] = 1;
    vector<int>rth;
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) {
            rth.push_back(i);
            smp.addqry(a[i], b[i], i);
            sm.addqry(n + 1 - a[i], n + 1 - b[i], i);
        } else {
            smp.addpt(a[i], b[i], c[i]);
            smp.addqry(a[i], b[i], i);
            sm.addpt(n + 1 - a[i], n + 1 - b[i], c[i]);
        }
    }
    smp.work(); sm.work();

    int siz = opt.size();
    int tot = rth.size();


    for (int i = 1; i <= n; ++i)
        if (!vis[i])
            if (smp.ans[i] > c[i]) {
                for (auto& [x, y] : opt)
                    swap(c[x], c[y]);
                for (int j = 1; j <= siz; ++j)
                    printf("No\n");
                opt.clear();
                return;
            }

    sort(all(rth), [&](int x, int y) {return a[x] < a[y]; });

    auto check = [&](int x) -> bool {
        return smp.ans[x] <= c[x] && sm.ans[x] >= c[x];
    };

    for (int i = 0; i < rth.size(); ++i)
        for (int j = 0; j < i; ++j)
            if (b[rth[j]] < b[rth[i]] && c[rth[j]] > c[rth[i]])
                ++err[rth[i]];
    for (int i = 0; i < rth.size(); ++i)
        rk[rth[i]] = i;

    for (auto x : rth)
        if (check(x) && !err[x])
            ++cntok;

    auto del = [&](int x) -> void {
        for (int i = rk[x] + 1; i < rth.size(); ++i)
            if (b[x] < b[rth[i]] && c[x] > c[rth[i]]) {
                --err[rth[i]];
                if (!err[rth[i]] && check(rth[i]))
                    ++cntok;
            }
    };

    auto cal = [&](int x) -> void {
        for (int i = 0; i < rk[x]; ++i)
            if (b[rth[i]] < b[x] && c[rth[i]] > c[x])
                ++err[x];
        for (int i = rk[x] + 1; i < rth.size(); ++i)
            if (b[x] < b[rth[i]] && c[x] > c[rth[i]]) {
                if (!err[rth[i]] && check(rth[i]))
                    --cntok;
                ++err[rth[i]];
            }
        if (check(x) && !err[x])
            ++cntok;
    };

    for (auto& [x, y] : opt) {
        if (x == y) {
            if (cntok == tot)printf("Yes\n");
            else printf("No\n");
            continue;
        }
        if (rk[x] < rk[y])swap(x, y);
        del(x); del(y);
        if (!err[x] && check(x))--cntok;
        if (!err[y] && check(y))--cntok;
        err[x] = err[y] = 0;
        swap(c[x], c[y]);
        int tmp = c[y];
        c[y] = 0; cal(x); c[y] = tmp; cal(y);
        if (cntok == tot)printf("Yes\n");
        else printf("No\n");
    }

    opt.clear();
}

void solve() {
    n = read(), m = read();
    smp.setlim(n), sm.setlim(n);
    read(a, n), read(b, n), read(c, n);
    for (int i = 1; i <= m; ++i) {
        opt.push_back({read(), read()});
        if (i % siz == 0)
            work();
    }
    if (!opt.empty())work();
}
signed main(signed argc, char const* argv[]) {
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //=============================================================
    int TxT = 1;
    // TxT = read();
    while (TxT--)
        solve();
    //=============================================================
#ifdef LOCAL
    end :
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}