官方题解 | 巅峰赛 27

hopebetter

2025-11-10 12:13:13

发布于：浙江

185阅读

0回复

0点赞

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目名称	题目难度
T1	Alice 的简单数组	入门
T2	Alice 的数学构造	普及-
T3	Alice 的交通网络	普及+/提高
T4	Alice 的分段游戏	普及+/提高
T5	Alice 的奇妙字段	普及+/提高
T6	Alice 的奇妙通信	普及+/提高

T1

题目大意

现在给你一个数组 a , 每次你可以将数组左移一格，问最终能否让这个数组，非降序。

题解

把数组视作首尾相接的环。定义“下降点”为满足

$a_i > a_{(i+1)\bmod n}$

的下标 $i$ 。

充要条件：
存在某个左旋次数 $r$ 使数组非降，当且仅当环上的下降点个数 $\le 1$ 。

若下降点个数 cnt = 0：原数组已非降，最小 $r=0$ 。
若 cnt > 1：无论从哪切开，总会把至少一个下降点放到中间位置，无法整体非降，答案 $-1$ 。
若 cnt = 1：设唯一下降点在 (i)（即 $a_i>a_{i+1}$ ）。则左旋 (r=i+1) 次（把 $a_{i+1}$ 放到开头）后序列必为非降；且这是最小的可行旋转次数。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        if (n == 1) {
            cout << 0 << "\n";
            continue;
        }
        int cnt = 0, pos = -1;
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            if (a[i] > a[j]) {
                cnt++;
                pos = i;
            }
        }
        if (cnt == 0) {
            cout << 0 << "\n";
            continue;
        }
        if (cnt > 1) {
            cout << -1 << "\n";
            continue;
        }
        int r = (pos + 1) % n;
        bool ok = true;
        for (int t = 1; t < n; t++) {
            long long x = a[(r + t - 1) % n], y = a[(r + t) % n];
            if (x > y) {
                ok = false;
                break;
            }
        }
        cout << (ok ? r : -1) << "\n";
    }
    return 0;
}

T2

题目大意

给定 $T$ 组询问，每组给一个正整数 $n$ 。设 $a$ 是 $\{1,2,\dots,n\}$ 的某个排列，定义前缀乘积序列

$b_1 \equiv a_1 \pmod n,\qquad b_i \equiv b_{i-1}\cdot a_i \pmod n\ \ (2\le i\le n).$

若序列 $b$ 恰好是 $\{0,1,\dots,n-1\}$ 的一个排列（每个余数出现且只出现一次），则称该排列 $a$ 可行。要求对每个 $n$ 判断是否存在可行排列。

判定结论： 当且仅当 $n\in{1,2,4}$ 或 $n$ 为素数时，答案为 YES，否则为 NO。

题解

必要性

令排列为 $\boldsymbol{a} = (a_1,\dots,a_n)$ ，前缀积为

$b_1\equiv a_1 \pmod{n},\qquad b_i\equiv b_{i-1} \times a_i \pmod{n}\ \ (2\le i\le n).$

$n$ 必须在末位：若某个 $a_k=n$ 出现在 $k<n$ ，则 $b_k\equiv 0$ ，而此后 $b_{k+1},\dots,b_n$ 也都 $\equiv 0$ ，无法成为 ${0,1,\dots,n-1}$ 的排列。因此必须 $a_n=n$ ，且恰有 $b_n\equiv 0$ 。
$(n-1)!\not\equiv 0\pmod{n}$ 必须成立：由于前 $n-1$ 个元素正好是 ${1,\dots,n-1}$ 的某个排列，

$b_{n-1}\equiv \prod_{i=1}^{n-1} a_i \equiv (n-1)!\pmod{n}.$

为避免 $b_{n-1}=0$ 与 $b_n=0$ 重复，必须 $(n-1)!\not\equiv 0\pmod{n}$ 。

经典数论结论：对一切合数 $n$ ，都有

$(n-1)!\equiv 0\pmod{n},$

仅有 $n=4$ 例外（ $3!\equiv 6\equiv 2\pmod{4}$ ）。而 $n$ 为素数时由威尔逊定理 $(n-1)!\equiv -1\pmod{n}\ne 0$ 。再合并平凡情形 $n=1,2$ ，得必然条件： $n\in{1,2,4}$ 或 $n$ 为素数。

充分性（构造）

$n=1$ ：取 $a=(1)$ ， $b=(0)$ 。
$n=2$ ：取 $a=(1,2)$ （或 $a=(2,1)$ ）， $b=(1,0)$ 为全体剩余。
$n=4$ ：取 $a=(1,3,2,4)$ ， $b=(1,3,2,0)$ 。
$n=p$ 为素数：构造
$a_1=1,\quad a_i\equiv i\cdot (i-1)^{-1}\pmod{p}\ \ (2\le i\le p-1),\quad a_p=p.$
其中 $(i-1)^{-1}$ 指模 $p$ 的乘法逆元。则
$b_i\equiv \prod_{j=1}^i a_j \equiv \prod_{j=2}^i \frac{j}{j-1} \equiv i \pmod{p}\quad(1\le i\le p-1),$
且 $b_p\equiv 0$ ，于是 $b$ 正好是 ${0,1,\dots,p-1}$ 的排列。

参考代码

#include "bits/stdc++.h"

using namespace std;


// 10 1 2 3 4 5 6 7 8 9 10
signed main() {
  
    int maxn = 1e6 + 7;
    vector<int> vis(maxn + 1, 1);
    for (int i = 2; i <= maxn; i++) {
        if (vis[i]) {
            for (int j = i + i; j <= maxn; j+=i) {
                vis[j] = 0;
            }
        }
    }
    vis[4] = 1;
    int t;
    cin >>t;
    while (t --) {
        int x;
        cin >>x ;
        if (vis[x]) cout <<"YES" <<endl;
        else cout <<"NO" <<endl;
    }
    return 0;
}

T3

题目大意

给定一棵有 $n$ 个点的无根树，第 $i$ 个点有正整数点权 $a_i$ 。要求恰好切断树上 $k$ 条边，把树分成 $k+1$ 个连通块。每个连通块的代价等于该块内点权和的平方，总代价

$\mathrm{Cost}=\sum_{i=1}^{k+1} s_i^2,$

其中 $s_i$ 是第 $i$ 块的点权和。求最小可能的总代价。

题解

思路

任选根 $1$ 。在每个结点 $u$ 的子树内维护“已结算代价 + 携带块点和”的二元状态，自底向上合并；切边时把子树携带块的平方落地，不断开时只合并点和，最后在根把剩余携带块平方收尾。

状态

对每个结点 $u$ ，定义

$\mathrm{DP}_u[t]=\{ (c,\ s)\ \}$

表示在 $u$ 的子树内恰好切了 $t$ 条边，已结算代价为 $c$ ，且仍与父亲连通的携带块点权和为 $s$ （此块平方尚未计入 $c$ ）。

叶子初始：

$\mathrm{DP}_u[0]={(0,\ a_u)},\qquad \mathrm{DP}_u[t>0]=\varnothing.$

合并转移

设从 $\mathrm{DP}_u[i]$ 取 $(c_1,s_1)$ ，从儿子 $v$ 的 $\mathrm{DP}_v[j]$ 取 $(c_2,s_2)$ ，有两类转移：

不断开边 $u\text{--}v$ （合并携带块，不加切边）：

$(i,j)\ \to\ (i+j),\qquad (c',s')=(c_1+c_2,\ s_1+s_2).$
切开边 $u\text{--}v$ （儿子侧携带块在此落地结算）：

$(i,j)\ \to\ (i+j+1),\qquad (c',s')=(c_1+c_2+s_2^2,\ s_1).$

对所有 $i,j$ （不超过 $k$ ）枚举并取更优。

收尾

整树处理完后，在根 $r$ ：

$\text{Answer}=\min_{(c,s)\in \mathrm{DP}_r[k]}\ \big(c+s^2\big).$

支配剪枝（控状态）

对固定的切边数 $t$ ，对 $\mathrm{DP}_u[t]$ 的候选按 $s$ 递增排序，仅保留使

$\Phi(c,s)=c+s^2$

严格下降的“前沿”。因为后续操作只会使携带和 $s$ 非减且落地代价是 $s^2$ （凸），被支配的状态在将来不可能更优。

正确性要点

单次记账：携带块只在切边处落地平方一次；不断开时不计平方，避免重复。
完备与不重：每条父子边都在“切/不断开”二选一中被唯一处理。
最优子结构：合并仅依赖 $,(c,s),$ 的可加性与携带性质，满足 DP 要求。
剪枝不伤最优：若同 $t$ 下有 $s_1\le s_2$ 且 $c_1+s_1^2\le c_2+s_2^2$ ，则任意后续合并/落地操作后前者不劣于后者。

复杂度

设剪枝后每个 $t$ 的候选至多为 $m$ （经验上很小）。一次父子合并约为 $O(k^2m^2)$ ，全树

$O\big(n\cdot k^2 \cdot m^2\big),\qquad \text{空间 }O(n\cdot k\cdot m),$

对 $n\le 5\times 10^3,\ k\le 30$ 可行。

边界校验

$k=0$ ：答案为整树总和 $S$ 的平方 $S^2$ （根处结算）。
$k=n-1$ ：每点成块，答案 $\sum a_i^2$ 。
点权全正，直觉与剪枝一致（块越大平方越贵，早落地有利于优化）。

参考代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;
const i64 inf = 4000000000000000000LL;

class Graph {
public:
    int n, k;
    vector<i64> arr;
    vector<vector<int> > adj;

    struct node {
        i128 cost, sum;

        node(i128 c = inf, i128 s = 0) : cost(c), sum(s) {
        }
    };

    i128 getV(const node &x) {
        return x.cost + x.sum * x.sum;
    }

    void prune(vector<node> &v) {
        if (v.empty()) return;
        sort(v.begin(), v.end(), [](const node &a, const node &b) {
            if (a.sum != b.sum) return a.sum < b.sum;
            return a.cost < b.cost;
        });
        vector<node> tmp;
        tmp.reserve(v.size());
        bool first = true;
        i128 best = 0;
        for (const auto &it: v) {
            i128 cc = getV(it);
            if (first || cc < best) {
                first = false;
                best = cc;
                tmp.push_back(it);
            }
        }
        v.swap(tmp);
    }

    struct DPnode {
        vector<vector<node> > f;
        vector<i64> v;
        int sz = 1;
    };

    Graph(int n, int k, vector<i64> _a, vector<vector<int> > _e)
        : n(n), k(min(k, n - 1)), arr(_a), adj(_e) {
    }

    void runDP(DPnode &ret, DPnode &child) {
        int sz1 = (int) ret.f.size();
        int sz2 = (int) child.f.size();
        int sz3 = (int) child.v.size();

        vector<int> _i, _j, __j;
        for (int i = 0; i <= min(k, sz1 - 1); ++i) if (!ret.f[i].empty()) _i.push_back(i);
        for (int j = 0; j <= min(k, sz2 - 1); ++j) if (!child.f[j].empty()) _j.push_back(j);
        for (int j = 0; j <= min(k, sz3 - 1); ++j) if (child.v[j] < inf) __j.push_back(j);

        vector<vector<node> > vv(k + 1);
        int maxs = -1;

        for (int i: _i) {
            for (int j: _j) {
                if (i + j > k) continue;
                for (const auto &ii: ret.f[i]) {
                    for (const auto &jj: child.f[j]) {
                        node states = {ii.cost + jj.cost, ii.sum + jj.sum};
                        vv[i + j].push_back(states);
                        maxs = max(maxs, i + j);
                    }
                }
            }
        }

        // 切 (u,child)：使用 child 的封口代价
        for (int i: _i) {
            for (int j: __j) {
                if (i + j + 1 > k) continue;
                i128 vvv = (i128) child.v[j];
                for (const auto &ii: ret.f[i]) {
                    node states = {ii.cost + vvv, ii.sum};
                    vv[i + j + 1].push_back(states);
                    maxs = max(maxs, i + j + 1);
                }
            }
        }

        if (maxs < 0) return;

        vector<vector<node> > tmp(maxs + 1);
        for (int t = 0; t <= maxs; ++t) {
            tmp[t] = move(vv[t]);
            prune(tmp[t]);
        }
        ret.f = tmp;
    }

    DPnode dfs(int u, int p) {
        DPnode ret;
        ret.f.assign(1, vector<node>(1, node{0, (i128) arr[u]}));

        vector<DPnode> V;
        for (auto vtx: adj[u]) {
            if (vtx == p) continue;
            V.push_back(dfs(vtx, u));
        }
        sort(V.begin(), V.end(), [](const DPnode &a, const DPnode &b) { return a.sz < b.sz; });
        for (auto &ch: V) runDP(ret, ch);

        ret.sz = 0;
        for (auto &bucket: ret.f) ret.sz += (int) bucket.size();

        ret.v.assign(ret.f.size(), inf);
        for (int i = 0; i < (int) ret.f.size(); ++i) {
            for (const auto &nd: ret.f[i]) {
                i128 cur = getV(nd);
                if (cur < (i128) ret.v[i]) ret.v[i] = (i64) cur;
            }
        }
        return ret;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<i64> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    vector<vector<int> > adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    Graph g(n, k, arr, adj);
    auto res = g.dfs(1, 0);
    i64 ans = (k <= (int) res.v.size() - 1 ? res.v[k] : inf);
    cout << ans << '\n';
    return 0;
}

T4

一、二分阈值 $X$

答案 $f$ 显然单调：若阈值从 $X$ 变大到 $X'$ （ $X'\ge X$ ），可行性不会变差。
因此二分 $X$ 。边界可取

$L=\max_i a_i,\qquad R=\sum_{i=1}^n a_i,$

在 $[L,R]$ 上二分，判定函数 ok(X) 判断“是否能用 $\le k$ 段满足条件”。

若数组中压根没有目标颜色（ $\exists i,\ \text{col}_i\in S$ 不成立），直接输出 $-1$ 。

二、判定 `ok(X)`：转化与 DP

约束 1：段和 $\le X$
令前缀和 $pre[i]=\sum_{t=1}^i a_t$ ，并设

$\text{lim}[i]=\min{,j\in[0,i-1]\mid pre[i]-pre[j]\le X,}.$

在 $a_i\ge 0$ 时， $\text{lim}[i]$ 可用双指针线性求出：对每个 $i$ ，让 $j$ 右移，使区间和 $\le X$ 。

约束 2：每段必须含 $S$
用 $nxt[i]$ 表示从位置 $i$ 开始向右的第一个“目标颜色”所在下标（若不存在取 $n+1$ ）。
那么分一段 $[j+1,i]$ 合法 $\iff$ nxt[j+1] <= i。

DP 设计
设 $g[i]$ 表示前 $i$ 个位置最少需要多少段（满足两项约束）， $g[0]=0$ ，其余初始为无穷大。
则

$g[i] ;=; 1+\min{,g[j]\mid \text{lim}[i]\le j\le i-1,\ \text{且}\ nxt[j+1]\le i,}.$

单调队列优化
当 $i$ 从小到大推进时：

允许作为转移来源的 $j$ 必须满足 nxt[j+1] <= i。也就是，当 $i$ 到达某值时，新的 $j$ 会陆续“解锁”。
同时 $j \ge \text{lim}[i]$ ，即窗口左端还要随着 $\text{lim}[i]$ 右移而弹出。

维护一个按 $g[j]$ 非降的双端队列 $Q$ 存可行的 $j$ 。推进步骤：

把新“解锁”的 $j$ 依次入队，入队前把队尾中 $g$ 不优的下标弹出，保持队列内 $g$ 非降；
把不满足 $j\ge \text{lim}[i]$ 的队首弹出；
若队首存在， $g[i]=g[Q.front()]+1$ ，否则 $g[i]=\infty$ 。

这样 ok(X) 即判断 g[n] <= k。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

static bool check(i64 X,
                  int n, int k,
                  const vector<i64> &pre,
                  const vector<int> &nxt) {
    // lim[i]: 最小 j 使 pre[i]-pre[j] <= X（0<=j<i），a>=0 情况用双指针
    vector<int> lim(n + 1, 0);
    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (j < i && pre[i] - pre[j] > X) j++;
        lim[i] = j;
    }

    const int INF = 0x3f3f3f3f;
    vector<int> g(n + 1, INF);
    g[0] = 0;

    // 当 i 达到 >= nxt[j+1] 时，j 被解锁为可转移左端
    int added = -1;
    deque<int> dq; // 按 g[j] 非降维护候选

    for (int i = 1; i <= n; i++) {
        while (added + 1 < i && nxt[added + 2] <= i) {
            int nj = added + 1;
            while (!dq.empty() && g[dq.back()] >= g[nj]) dq.pop_back();
            dq.push_back(nj);
            added = nj;
        }
        while (!dq.empty() && dq.front() < lim[i]) dq.pop_front();
        if (!dq.empty() && g[dq.front()] < INF) g[i] = g[dq.front()] + 1;
        else g[i] = INF;
    }
    return g[n] <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, t;
    cin >> n >> m >> k >> t;

    vector<i64> a(n + 1, 0), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> col(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> col[i];

    vector<int> inS(m + 1, 0);
    for (int i = 0; i < t; i++) {
        int x; cin >> x;
        if (1 <= x && x <= m) inS[x] = 1;
    }

    bool hasS = false;
    for (int i = 1; i <= n; i++) if (inS[col[i]]) { hasS = true; break; }
    if (!hasS) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];

    vector<int> nxt(n + 2, n + 1);
    for (int i = n; i >= 1; i--) {
        if (inS[col[i]]) nxt[i] = i;
        else nxt[i] = nxt[i + 1];
    }

    i64 L = 0, R = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > L) L = a[i];
        R += a[i];
    }

    i64 ans = -1;
    i64 left = L, right = R;
    while (left <= right) {
        i64 mid = (left + right) >> 1;
        if (check(mid, n, k, pre, nxt)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

T5

题目大意

有一串数 $(a_1,\dots,a_n)$ 。你可以最多一次把某一段连续区间里（长度不超过 $L$ ）的数全部取反（乘 $-1$ ）。翻完之后，再从新数组里选一个非空连续子段，让它的和尽量大。问这个最大值是多少（也可以选择不翻）。

题解

思路解释

想象最后你选出来的“最大子段”是一整段，中间有一小段被你翻转过。那这件事等价于：

左边：接一段原数组的“最好尾巴”（以某个位置结尾的最大和，负数就不取）；
中间：接一段被翻转的区间（长度 $\le L$ ）。
注意：翻转某一段，其贡献就是把这段的和从 $S$ 变成 $-S$ ，净变化是 减去 $2S$ 。所以“翻哪一段最赚”？——在你选的整段里面，找一个和尽可能小、长度 $\le L$ 的中间段去翻；
右边：再接一段原数组的“最好开头”（以某个位置开始的最大和，负数就不取）。

于是，我们只要把“左边最好尾巴 $+$ 中间翻转 $+$ 右边最好开头”的组合做到最优即可。

怎么高效做

先算一个保底答案：不翻转时的最大子段和（经典的最大子段和，一次扫描）。
准备三样“辅助信息”
- 前缀和 $P[i]$ （方便快速算任意一段的和）；
- $\texttt{pre}[i]$ ：以 $i$ 结尾的最大子段和（负就当 $0$ ，不取）；
- $\texttt{suf}[i]$ ：从 $i$ 开始的最大子段和（负就当 $0$ ，不取）。
  pre 正向扫一遍，suf 反向扫一遍就好了。
把“翻转中间段”变成滑窗问题
设中间段的右端是 $r$ 。那它的左端 $l$ 只能在区间 $[,r-L+1,\ r,]$ 里（长度 $\le L$ ）。
这时“左边最好尾巴 $+$ 这段被翻后带来的收益 $+$ 右边最好开头”可以写成：

$\text{选 } j=l-1\in[,r-L,,r-1,]\ \text{去最大化：}\quad (\texttt{pre}[j]+P[j])\ +\ (\texttt{suf}[r+1]-P[r]) .$

对于固定的 $r$ ，右边括号中的 $(\texttt{suf}[r+1]-P[r])$ 是常数；
左边需要在区间 $j \in [,r-L,,r-1,]$ 里取 $(\texttt{pre}[j] + P[j])$ 的最大值。
——这就是一个滑动窗口最大值：用一个单调队列维护窗口内的最大 $(\texttt{pre}[j]+P[j])$ 即可。每次 $r$ 右移一步，就：
- 把窗口左端过期的 $j$ 弹掉；
- 把新进入的 $j=r-1$ 按值递减地入队；
- 用队头的最大值更新答案。
别忘了比较“不翻”的保底答案
最终答案 $=\max{\text{不翻的最大子段和},\ \text{上面滑窗得到的最大值}}$ 。
如果 $L=0$ （不能翻），那就直接输出最大子段和的结果。

参考代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
    int n, l;
    cin >> n >> l;
    vector<i64> v(n + 10), pre(n + 10), suf(n + 10), pc(n + 10), sums(n + 10);
    i64 maxs = -1e18;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        pre[i] = max(v[i], v[i] + pre[i - 1]);
        maxs = max(maxs, pre[i]);
        pc[i] = pc[i - 1] - v[i];
        sums[i] = pre[i] - pc[i];
    }
    sums[0] = 0;
    for (int i = n; i; i--) {
        suf[i] = max(v[i], v[i] + suf[i + 1]);
    }
    if (l == 0) {
        cout << maxs << '\n';
        return 0;
    }

    deque<int> dq;
    for (int i = 1; i <= n; i++) {
        int t = i - 1;
        while (!dq.empty() && sums[t] >= sums[dq.back()]) dq.pop_back();
        dq.push_back(t);
        if (dq.front() < i - l) dq.pop_front();
        if (!dq.empty()) {
            maxs = max(sums[dq.front()] + suf[i + 1] + pc[i], maxs);
        }
    }
    cout << maxs << '\n';
}

T6

题面简介

给定一个最初无边的 $n$ 点图，按时刻 $t=1\ldots q$ 发生三类事件：

1 x y：在无向点对 $(x,y)$ 之间新增一条通道（允许多重边，计数 $+1$ ）；
2 x y：在 $(x,y)$ 之间摧毁一条通道（计数 $-1$ ，保证此时计数 $\ge 1$ ）；
3 x y：询问此刻 $x$ 与 $y$ 是否连通。

把所有回答为“连通”的询问的时刻记为 $t_1,t_2,\dots$ ，输出

$X=t_1\oplus t_2\oplus \cdots .$

若没有一次连通询问，输出 $0$ 。图允许多重边，连通按“仍存在的通道”是否能成路来判断。

题解

1. 离线把“边的存在”转成时间区间

对每个无序点对 $e={x,y}$ 维护当前计数 cnt[e]（初始 $0$ ）与“活跃区间起点” st[e]。从 $t=1$ 到 $q$ 顺序扫描事件：

1 x y：令 $e={x,y}$ 。若 cnt[e]==0，则 st[e]=t；随后 cnt[e]++。
2 x y：令 $e={x,y}$ 。先 cnt[e]--；若此时 cnt[e]==0，则产生一个活跃区间 $[,st[e],\ t-1,]$ ，表示这条边在该时间段存在。
计数语义的关键：我们只在计数从 $0\to 1$ 与 $1\to 0$ 时开/闭区间（多重边只要计数 $>0$ ，这条无向边就视为存在）。

扫描结束后，若某些边仍满足 cnt[e]>0，则补上区间 $[,st[e],\ q,]$ 。

于是，每条逻辑“边是否存在”的历史都被表示为若干时间区间。

2. 时间线段树上挂边

建一个覆盖区间 $[1,q]$ 的线段树。把每条边的活跃区间 $[L,R]$ 加到线段树所有与之相交的结点上（常规“区间加到节点”的做法，复杂度 $O(\log q)$ 每条区间）。
这样，线段树每个结点维护的是“它所覆盖的时间段内恒为存在”的边集合。

3. 回滚并查集（DSU with rollback）

准备可回滚的并查集：parent[] / size[] 以及一条操作栈用于记录每次 union 的变更（谁挂到谁、被改变的 size 值等）。提供函数：

save()：记录当前栈大小；
rollback(S)：把栈回滚到大小为 S 的状态（逐一撤销 union 的 parent/size 改动）；
union(x,y)：若本来就同属一集合则不入栈；若合并，按启发式把小树挂大树并把改动入栈，便于回退；
find(x)：路径不压缩的版本（避免难以回滚），只配合按秩/按大小合并即可。

4. 深搜线段树处理查询

从根结点 DFS：

入结点前：记下当前栈大小 S；把该结点挂着的所有边执行 union；
若是叶子（对应唯一时刻 $t$ ）：若第 $t$ 个事件是询问 3 x y，则判断 find(x)==find(y)；若连通，则做
$\text{ans}\ \mathrel{:=}\ \text{ans}\ \oplus\ t.$
递归处理左右子结点；
回到本结点退出前：rollback(S) 撤销本结点施加的所有合并，环境还原给兄弟分支使用。

最终输出 ans。

参考代码

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> fa, sz;

    struct Node {
        int x, y;
    };

    vector<Node> st;
    int n;

    void init(int n_) {
        n = n_;
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
        sz.assign(n + 1, 1);
        st.clear();
    }

    int find(int x) const {
        while (fa[x] != x) x = fa[x];
        return x;
    }

    // 返回当前栈快照（替代原来的 t）
    int snapshot() const { return (int) st.size(); }

    // 合并，返回是否真的合并成功
    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        st.push_back({u, v});
        fa[u] = v;
        sz[v] += sz[u];
        return true;
    }

    // 回滚到快照 snap（不包含 snap 本身）
    void rollback(int snap) {
        while ((int) st.size() > snap) {
            auto m = st.back();
            st.pop_back();
            int x = m.x, y = m.y;
            sz[y] -= sz[x];
            fa[x] = x;
        }
    }
};

DSU d;
int ans = 0;

struct STG {
    int n;
    vector<vector<pair<int, int> > > edge;

    struct ASK {
        int u, v;

        ASK() {
            u = 0, v = 0;
        }

        ASK(int _u, int _v) {
            u = _u, v = _v;
        }
    };

    vector<ASK> asks;


    void init(int _n) {
        n = _n;
        edge.resize(n * 4 + 1);
        asks.resize(n + 1);
    }

    void add(int q, int l, int r, int L, int R, int x, int y) {
        if (l > r) return;
        if (l > R || r < L) return;
        if (L <= l && r <= R) {
            edge[q].push_back({x, y});
            return;
        }
        int mid = (l + r) / 2;
        add(q << 1, l, mid, L, R, x, y);
        add(q << 1 | 1, mid + 1, r, L, R, x, y);
    }

    void addASK(int t, int u, int v) {
        asks[t] = {u, v};
    }

    void dfs(int q, int l, int r) {
        int st = d.snapshot();
        for (auto e: edge[q]) {
            int x = e.first;
            int y = e.second;
            d.merge(x, y);
        }
        if (l == r) {
            int u = asks[l].u;
            int v = asks[l].v;
            u = d.find(u);
            v = d.find(v);
            if (u == v && u) {
                ans ^= l;
            }
        } else {
            int mid = (l + r) / 2;
            dfs(q << 1, l, mid);
            dfs(q << 1 | 1, mid + 1, r);
        }
        d.rollback(st);
    }
};

STG stg;

int main() {
    int n, q;
    cin >> n >> q;
    d.init(n + 1);
    stg.init(q + 1);
    map<pair<int, int>, int> cnt;
    map<pair<int, int>, int> pp;
    for (int i = 1; i <= q; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > y) swap(x, y);
        if (op == 1) {
            cnt[{x, y}]++;
            if (cnt[{x, y}] == 1) {
                pp[{x, y}] = i;
            }
        } else if (op == 2) {
            cnt[{x, y}]--;
            if (cnt[{x, y}] == 0) {
                int L = pp[{x, y}];
                stg.add(1, 1, q, L, i - 1, x, y);
            }
        } else if (op == 3) {
            stg.addASK(i, x, y);
        }
    }

    for (auto k: cnt) {
        if (k.second) {
            int L = pp[k.first];
            stg.add(1, 1, q, L, q, k.first.first, k.first.second);
        }
    }
    stg.dfs(1, 1, q);
    cout << ans << '\n';
}

有帮助，赞一个

去预览

0/2000

全部评论 5

Lost
hack C 题 std：https://www.acgo.cn/discuss/study/62579

1小时前来自山东
1
Stars_Seeker
qp

3天前来自重庆
1
cjdstttttt
T4<<T3

3天前来自广东
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复cjdstttttt
  智齿
  
  昨天来自上海
  0
- cjdstttttt
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  我去发明数位dp大佬%%%
  
  37分钟前来自广东
  0
- cjdstttttt
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  我去发明数位dp大佬%%%
  
  37分钟前来自广东
  0
cjdstttttt
T6不是紫吗

3天前来自广东
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复cjdstttttt
  上上上位蓝/下下下位紫
  
  昨天来自上海
  0
egogaming
666，动态图连通性说成绿题？

3天前来自广东
0