题解：P16679 [CSPro 27] 吉祥物投票

cosf · 2026-10-20 14:10:01 · 题解

什么缝合怪题。

:::success[Code]{open}

#include <iostream>
#include <set>
using namespace std;

#define MAXN 200005

int n, m, q;

struct Seg
{
    int l, r, v;
    friend bool operator<(const Seg &l, const Seg &r)
    {
        return l.r < r.r;
    }
};
set<Seg> odt;
int sid = 0;

int cnt[MAXN];
struct SegTree
{
    int t[MAXN << 2];
    #define ls (p << 1)
    #define rs (p << 1 | 1)

    void pushup(int p)
    {
        if (cnt[t[ls]] >= cnt[t[rs]])
        {
            t[p] = t[ls];
        }
        else
        {
            t[p] = t[rs];
        }
    }

    void build(int p, int l, int r)
    {
        if (l == r)
        {
            t[p] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(p);
    }

    void upd(int p, int l, int r, int q)
    {
        if (l == r || !q)
        {
            return;
        }
        int mid = (l + r) >> 1;
        if (mid >= q)
        {
            upd(ls, l, mid, q);
        }
        else
        {
            upd(rs, mid + 1, r, q);
        }
        pushup(p);
    }
} seg;

struct DSU
{
    int fa[MAXN << 2];
    int sz[MAXN << 2];

    int find(int x)
    {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    void mergets(int u, int v)
    {
        u = find(u), v = find(v);
        if (u == v)
        {
            return;
        }
        fa[v] = u;
        sz[u] += sz[v];
    }

    int unlink(int u)
    {
        int f = find(u);
        sz[f] -= sz[u];
        fa[u] = u;
        return f;
    }
} dsu;

int dir[MAXN], rid[MAXN << 2];

void upd(int f)
{
    cnt[rid[f]] = dsu.sz[f];
    seg.upd(1, 1, m, rid[f]);
}

set<Seg>::iterator split(int p)
{
    if (!p)
    {
        return odt.begin();
    }
    auto it = odt.lower_bound(Seg{0, p, 0});
    if (it->r == p)
    {
        return next(it);
    }
    auto [l, r, v] = *it;
    odt.erase(it);
    int f = dsu.unlink(v);
    dsu.sz[v] = (p - l + 1);
    dsu.mergets(f, v);
    ++sid;
    dsu.fa[sid] = sid;
    dsu.sz[sid] = (r - p);
    dsu.mergets(f, sid);
    upd(f);
    odt.insert(Seg{l, p, v});
    return odt.insert(Seg{p + 1, r, sid}).first;
}

void segfill()
{
    int l, r, w;
    cin >> l >> r >> w;
    auto itr = split(r), itl = split(l - 1);
    for (auto it = itl; it != itr; ++it)
    {
        upd(dsu.unlink(it->v));
    }
    odt.erase(itl, itr);
    ++sid;
    dsu.fa[sid] = sid;
    dsu.sz[sid] = r - l + 1;
    dsu.mergets(dir[w], sid);
    upd(dir[w]);
    odt.insert(Seg{l, r, sid});
}

void redir()
{
    int u, v;
    cin >> u >> v;
    cnt[v] += cnt[u];
    cnt[u] = 0;
    dsu.mergets(dir[v], dir[u]);
    dir[u] = ++sid;
    rid[sid] = u;
    dsu.fa[sid] = sid;
    seg.upd(1, 1, m, u), seg.upd(1, 1, m, v);
}

void swp()
{
    int u, v;
    cin >> u >> v;
    swap(cnt[u], cnt[v]);
    swap(dir[u], dir[v]);
    swap(rid[dir[u]], rid[dir[v]]);
    seg.upd(1, 1, m, u), seg.upd(1, 1, m, v);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    seg.build(1, 1, m);
    cnt[0] = n;
    odt.insert({1, n, 0});
    sid = m + 1;
    dir[0] = m + 1;
    dsu.sz[0] = n;
    for (int i = 1; i <= m; i++)
    {
        dsu.fa[i] = i;
        dir[i] = i;
        rid[i] = i;
    }
    dsu.fa[m + 1] = m + 1;
    dsu.mergets(m + 1, 0);
    while (q--)
    {
        int o;
        cin >> o;
        if (o == 1)
        {
            segfill();
        }
        else if (o == 2)
        {
            redir();
        }
        else if (o == 3)
        {
            swp();
        }
        else if (o == 4)
        {
            int w;
            cin >> w;
            cout << cnt[w] << '\n';
        }
        else
        {
            int w = seg.t[1];
            cout << !!cnt[w] * w << '\n';
        }
    }
    return 0;
}

:::