loj#523. 「LibreOJ β Round #3」绯色 IOI（悬念）

由题述，\(X\) 满匹配，根据 Hall 定理，有对于任意一个有 \(k\) 个妹子的集合，她们能配对的男生的人数 \(\ge k\)。

把每个妹子看作她所连接的两个（可能是同一个）男生间的无向边，则每个连通块必然是树或基环树。

问题转化为给每条无向边定向，满足每个点的入度不超过 \(1\)，求最大边权和。

对于树，其实就是确定一个根结点转化为外向树，所以对 dfn 建线段树，并对修改的边在对应根结点的子树内或外进行分讨即可，时间复杂度 \(\mathcal O(\log n)\)。

对于基环树，它一定是基环外向树，所以环外边 \(\mathcal O(1)\) 修改即可，环内边只有顺时针和逆时针两种方向，同样 \(\mathcal O(1)\) 修改搞定。

总时间复杂度 \(\mathcal O[(n + q) \log n]\)，跑不满一点。

代码

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

constexpr int N = 5e5 + 10;

int m, n, T, a[N], b[N], rt[N], w[N << 1], s[N][3], ans;
int cnt, dep[N], dfn[N], sed[N], pree[N];
bool mark[N];

vector<int> cir;

int tot, head[N], oppo[N << 1], dir[N << 1];
struct Edge{int to, nxt;} e[N << 1];
inline void add(int u, int v) {e[++tot] = Edge{v, head[u]}; head[u] = tot;}

namespace SGT {
    #define lson pos << 1
    #define rson pos << 1 | 1

    int mx[N << 2], lazy[N << 2];
    
    inline void pushdown(int pos) {
        if (!lazy[pos]) return;
        mx[lson] += lazy[pos], lazy[lson] += lazy[pos];
        mx[rson] += lazy[pos], lazy[rson] += lazy[pos];
        lazy[pos] = 0;
    }

    void upd(int pos, int l, int r, int x, int y, int c) {
        if (x <= l && r <= y) {mx[pos] += c, lazy[pos] += c; return;}
        pushdown(pos); int mid = (l + r) >> 1;
        if (x <= mid) upd(lson, l, mid, x, y, c);
        if (y > mid) upd(rson, mid + 1, r, x, y, c);
        mx[pos] = max(mx[lson], mx[rson]);
    }

    int query(int pos, int l, int r, int x, int y) {
        if (x <= l && r <= y) return mx[pos];
        pushdown(pos); int mid = (l + r) >> 1, res = 0;
        if (x <= mid) res = query(lson, l, mid, x, y);
        if (y > mid) res = max(res, query(rson, mid + 1, r, x, y));
        return res;
    }
}

void dfs(int u) {
    for (int i = head[u], v; v = e[i].to, i; i = e[i].nxt) {
        if (!dep[v]) dep[v] = dep[u] + 1, pree[v] = i, dfs(v);
        else if (dep[v] >= dep[u]) {
            int j = pree[v];
            while (j && e[j].to != u) cir.eb(j), j = pree[e[oppo[j]].to];
            cir.eb(oppo[i]);
        }
    }
}

void dfs2(int u, int r) {
    rt[u] = r, dfn[u] = ++cnt;
    for (int i = head[u], v; v = e[i].to, i; i = e[i].nxt) if (!dfn[v]) dfs2(v, r);
    sed[u] = cnt;
}

void modify(int x, int v) {
    int d = v - w[x], r = rt[e[x].to]; w[x] = v;
    if (mark[r]) {
        ans -= s[r][0] + max(s[r][1], s[r][2]);
        if (dir[x] || dfn[e[x].to] > dfn[e[oppo[x]].to]) s[r][dir[x]] += d;
        ans += s[r][0] + max(s[r][1], s[r][2]);
    } else {
        ans -= SGT::query(1, 1, n, dfn[r], sed[r]);
        if (dfn[e[x].to] > dfn[e[oppo[x]].to]) SGT::upd(1, 1, n, dfn[r], dfn[e[x].to] - 1, d), SGT::upd(1, 1, n, sed[e[x].to] + 1, sed[r], d);
        else SGT::upd(1, 1, n, dfn[e[oppo[x]].to], sed[e[oppo[x]].to], d);
        ans += SGT::query(1, 1, n, dfn[r], sed[r]);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> m >> n >> T;
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= m; i++) {
        int u = (a[i] + b[i]) % n + 1, v = (a[i] - b[i] + n) % n + 1;
        if (u < v) swap(u, v);
        add(u, v);
        if (u == v) oppo[tot] = tot;
        else oppo[tot] = tot + 1, add(v, u), oppo[tot] = tot - 1;
    }
    for (int i = 1; i <= n; i++) if (!rt[i]) {
        dep[i] = 1, cir.clear(), dfs(i); mark[i] = !cir.empty();
        if (mark[i]) {
            for (int j : cir) dir[j] = 1, dir[oppo[j]] = 2;
            dfs2(e[cir[0]].to, i);
        } else dfs2(i, i);
    }
    for (int i = 1, v; i <= tot; i++) cin >> v, modify(i, v);
    cout << ans << '\n';
    int q; cin >> q;
    while (q--) {
        int x, v; cin >> x >> v; x -= T * ans, v -= T * ans;
        modify(x, v); cout << ans << '\n';
    }
    return 0;
}