CF2147F Exchange Queries

· · 题解

以下是场上 16min 速通的做法。

若 i 可以买到 j 就连一条 i \to j 的有向边，相当于求可达点对数量。发现这个图是竞赛图加上若干条边，所以缩点之后一定是一条链。

令 a_{p_i} = s_i。设 \max\limits_{j = 1}^i a_j = i 的所有位置为 b_1, b_2, \ldots, b_k（设 b_0 = 0），那么一个强连通分量即为 [b_{i - 1} + 1, b_i]，它可以到达 [1, b_i] 中的所有点。

所以答案即为：

\sum\limits_{i = 1}^k b_i \times (b_i - b_{i - 1}) = \sum\limits_{i = 1}^k b_i^2 - \sum\limits_{i = 2}^k b_{i - 1} \times b_i

要求支持交换 a 的两个元素，然后查询上述式子。

考虑线段树维护，对于每个 i，维护 i 减去前缀 [1, i] 中 \le i 的 a_j 的个数，容易发现这个值一定 \ge 0。那么一个 a_j 会对 i \in [\max(j, a_j), n] 有 1 的贡献。

问题变成，区间（其实是后缀）\pm 1，设值为 0（即最小值）的所有位置为 b_1, b_2, \ldots, b_k，求 \sum\limits_{i = 1}^k b_i^2 - \sum\limits_{i = 2}^k b_{i - 1} \times b_i。

容易线段树维护。线段树每个结点维护这个区间最靠左、最靠右的区间最小值，和当前区间的答案。合并是容易的。

时间复杂度 O((n + m) \log n)。

// Problem: F. Exchange Queries
// Contest: Codeforces - Codeforces Global Round 29 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2147/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 100100;

int n, m, a[maxn], b[maxn], p[maxn], ip[maxn];

struct node {
    int mn, l, r;
    ll s;
};

inline node operator + (const node &a, const node &b) {
    node res;
    res.mn = min(a.mn, b.mn);
    if (a.mn < b.mn) {
        res.l = a.l;
        res.r = a.r;
        res.s = a.s;
    } else if (a.mn > b.mn) {
        res.l = b.l;
        res.r = b.r;
        res.s = b.s;
    } else {
        res.l = a.l;
        res.r = b.r;
        res.s = a.s + b.s - 1LL * a.r * b.l;
    }
    return res;
}

namespace SGT {
    node a[maxn << 2];
    int tag[maxn << 2];

    inline void pushup(int x) {
        a[x] = a[x << 1] + a[x << 1 | 1];
    }

    inline void pushtag(int x, int y) {
        a[x].mn += y;
        tag[x] += y;
    }

    inline void pushdown(int x) {
        if (!tag[x]) {
            return;
        }
        pushtag(x << 1, tag[x]);
        pushtag(x << 1 | 1, tag[x]);
        tag[x] = 0;
    }

    void build(int rt, int l, int r) {
        tag[rt] = 0;
        if (l == r) {
            a[rt].mn = a[rt].l = a[rt].r = l;
            a[rt].s = 1LL * l * l;
            return;
        }
        int mid = (l + r) >> 1;
        build(rt << 1, l, mid);
        build(rt << 1 | 1, mid + 1, r);
        pushup(rt);
    }

    void update(int rt, int l, int r, int ql, int qr, int x) {
        if (ql > qr) {
            return;
        }
        if (ql <= l && r <= qr) {
            pushtag(rt, x);
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        if (ql <= mid) {
            update(rt << 1, l, mid, ql, qr, x);
        }
        if (qr > mid) {
            update(rt << 1 | 1, mid + 1, r, ql, qr, x);
        }
        pushup(rt);
    }
}

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        p[a[i]] = b[i];
        ip[b[i]] = a[i];
    }
    SGT::build(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        SGT::update(1, 1, n, max(i, p[i]), n, -1);
    }
    while (m--) {
        int o, i, j;
        scanf("%d%d%d", &o, &i, &j);
        if (o == 1) {
            swap(a[i], a[j]);
            SGT::update(1, 1, n, max(a[i], p[a[i]]), n, 1);
            SGT::update(1, 1, n, max(a[j], p[a[j]]), n, 1);
            swap(p[a[i]], p[a[j]]);
            SGT::update(1, 1, n, max(a[i], p[a[i]]), n, -1);
            SGT::update(1, 1, n, max(a[j], p[a[j]]), n, -1);
            swap(ip[p[a[i]]], ip[p[a[j]]]);
        } else {
            swap(b[i], b[j]);
            swap(ip[b[i]], ip[b[j]]);
            int x = ip[b[i]], y = ip[b[j]];
            SGT::update(1, 1, n, max(x, p[x]), n, 1);
            SGT::update(1, 1, n, max(y, p[y]), n, 1);
            swap(p[ip[b[i]]], p[ip[b[j]]]);
            SGT::update(1, 1, n, max(x, p[x]), n, -1);
            SGT::update(1, 1, n, max(y, p[y]), n, -1);
        }
        printf("%lld\n", SGT::a[1].s);
    }
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}