Codeforces 题解

初三和高一写的，平均难度 2800 左右。

题号	tags
CF1515G	dfs and similar, graphs, math, number theory
CF521E	dfs and similar, graphs
CF549F	data structures, divide and conquer
CF1144G	dp, greedy
CF1305G	bitmasks, brute force, dp, dsu, graphs
CF1430F	dp, greedy
CF1498E	brute force, graphs, greedy, interactive, sortings
CF1508C	bitmasks, brute force, data structures, dfs and similar, dsu, graphs, greedy, trees
CF1516E	combinatorics, dp, math
CF1515F	constructive algorithms, dfs and similar, dsu, graphs, greedy, trees
CF1519E	constructive algorithms, dfs and similar, geometry, graphs, sortings, trees
CF1498D	dfs and similar, dp, graphs, implementation
CF1498F	bitmasks, data structures, dfs and similar, dp, games, math, trees
CF493E	math
CF868E	dp, graphs, trees
CF555E	dfs and similar, graphs, trees
CF845F	bitmasks, dp
CF908G	dp, math
CF1548D2	brute force, geometry, math, number theory
CF1548E	data structures, divide and conquer, graphs, greedy, math
CF1562E	dp, greedy, string suffix structures, strings
CF1562F	interactive, math, number theory, probabilities
CF566C	dfs and similar, divide and conquer, trees
CF1149C	data structures, implementation, trees

CF1515G Phoenix and Odometers

给定一张 $n$ 个点 $m$ 条边的带权有向图。

有 $q$ 次询问，每次给定 $v,s,t$，问是否存在一条起点终点都为 $v$ 的路径满足 $t | (s+l)$，其中 $l$ 是路径的总长。

$n,m,q \le 2 \times 10^5,0\le s<t\le 10^9$，边权均不超过 $10^9$。

首先这条路径只能在 $v$ 所在强连通分量的内部。

以下所有的路径长度都是在模 $t$ 意义下的。

引理：在同一个强连通分量，如果 $u\rightarrow v$ 存在一条长度为 $l$ 的路径，那么 $v\rightarrow u$ 存在一条长度为 $-l$ 的路径。

构造：根据强连通性 $v\rightarrow u$ 存在一条路径，设它的长度为 $w$，先走 $v\rightarrow u$，长度为 $w$，再走 $t-1$ 次 $u\rightarrow v\rightarrow u$，长度为 $(t-1)(l+w)$，总长度 $-l$。

在强连通分量的内部，对于一个长度为 $w$ 的环，从 环上 一个点 $u$ 出发绕若干圈再回到 $u$，所有可能的路径长度为 $\gcd(w,t)$ 的倍数。根据引理，对于任意一个点 $v$，先走 $v\rightarrow u$，再绕若干圈，最后走 $u\rightarrow v$，就可以凑出所有长度为 $\gcd(w,t)$ 倍数的环。

以 $r$ 为根建出 DFS 树，设 $\varphi(u)$ 表示从 $r$ 沿着树边走到 $u$ 的路径长度，对于每条非树边 $(u,v,w)$，意味着存在一个长度为 $\varphi(u)+w-\varphi(v)$ 的环。设 $x=\gcd_{(u,v,w)}\varphi(u)+w-\varphi(v)$，那么所有的可能环长分别为 $0,x,2x,3x,\cdots$。这些环长显然能取到，也可以归纳证明对于任何 $r\rightarrow u$ 的路径，都有长度 $\equiv \varphi(u)\pmod x$。结论：存在合法路径当且仅当 $x|s$。

复杂度 $O(n+m)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define upd(a, b) (a = min(a, b))

using namespace std;

typedef long long ll;
const int N = 2e5 + 5;

int n, m, q;
vector<pair<int, int>> G[N];
int idx, dfn[N], scc[N], stk[N], tp, sid;
ll g[N], d[N], gg[N];

int dfs(int u) {
    int low = dfn[u] = ++idx; stk[++tp] = u;
    for(auto [v, w] : G[u]) if(!dfn[v]) d[v] = d[u] + w, upd(low, dfs(v));
    else if(!scc[v]) upd(low, dfn[v]), g[u] = gcd(g[u], d[u] - d[v] + w);
    if(low == dfn[u]) for(int v = (sid++, 0); v ^ u;)
        v = stk[tp--], scc[v] = sid, gg[sid] = gcd(gg[sid], g[v]);
    return low;
}
int main() {
    cin >> n >> m;
    int u, v, w;
    rep(i, 1, m) scanf("%d%d%d", &u, &v, &w), G[u].emplace_back(v, w);
    rep(i, 1, n) if(!dfn[i]) dfs(i);
    for(cin >> q; q--; puts(v % gcd(gg[scc[u]], (ll)w) ? "NO" : "YES"))
        scanf("%d%d%d", &u, &v, &w);
}

CF521E Cycling City

给定一张 $n$ 个点 $m$ 条边的简单无向图。

问在图中能否找到两个点，满足这两个点之间有至少三条点不相交的简单路径，有解要打印三条路径。

$n,m \le 2 \times 10^5$ 不保证图连通。

考虑 $u \rightarrow v$ 有三条点不相交的路径会是什么样子，发现有两个环相交了。

反过来，如果任意两个环都不相交，即仙人掌，那就无解。

至此，得到了有解的充要条件：不是仙人掌。

但为了便于打印路径，采用另一种方法。

设 $low_u$ 为 tarjan 算法中的定义，$Low_u$ 表示次小值。

如果 $Low_u = dfn_u$，则子树内的一个点到子树外的一个点至多有两条点不相交的简单路径。

于是存在满足 $Low_u < dfn_u$ 的点 $u$ 是有解的必要条件。

观察这张图，如果 $lca(v,V)=u$，那么 $u \rightarrow Low$，$u \rightarrow v \rightarrow low \rightarrow Low$ 和 $u \rightarrow V \rightarrow Low$ 是三条点不相交的简单路径。

只要以 $u$ 为根的子树中只有 $u$ 一个点满足 $Low_u < dfn_u$，则 $lca(v, V) = u$。

在 dfs 过程中第一次找到满足 $Low_u < dfn_u$ 的点 $u$ 即符合上一行的条件，因为它是子树中最后判定的点。

复杂度 $O(n)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 2e5 + 5;
typedef vector <int> vi;
int n, m; vi G[N];
int idx, dfn[N], fa[N], ma;
struct node {
    int u, fa, U, Fa;
    node(int uu) { u = fa = U = Fa = uu; }
    void upd(int uu, int ffa) {
        if(dfn[ffa] < dfn[fa]) U = u, Fa = fa, u = uu, fa = ffa;
        else if(dfn[ffa] < dfn[Fa]) U = uu, Fa = ffa;
    }
} as(0);
node dfs(int u) {
    dfn[u] = ++idx; node lowu(u);
    for(int v : G[u]) if(!dfn[v]) {
        fa[v] = u;
        node lowv = dfs(v);
        lowu.upd(lowv.u, lowv.fa), lowu.upd(lowv.U, lowv.Fa);
    } else if(dfn[v] < dfn[u] && v ^ fa[u]) lowu.upd(u, v);
    if(!ma && dfn[lowu.Fa] < dfn[u]) as = lowu, ma = u;
    return lowu;
}
vi find(int s, int t) {
    vi p;
    while(s ^ t) p.pb(s), s = fa[s];
    p.pb(t);
    return p;
}
vi p;
void print() {
    printf("%llu ", p.size());
    for(int u : p) printf("%d ", u);
    puts("");
}
int main() {
    cin >> n >> m;
    int u, v;
    rep(i, 1, m) scanf("%d%d", &u, &v), G[u].pb(v), G[v].pb(u);
    rep(i, 1, n) if(!ma && !dfn[i]) dfs(i);
    if(ma) {
        puts("YES");
        p = find(ma, as.Fa), print();
        p = find(as.U, ma), reverse(p.begin(), p.end());
        p.pb(as.Fa), print();
        p = find(as.Fa, as.fa); vi t = find(as.u, ma);
        p.insert(p.end(), t.begin(), t.end());
        reverse(p.begin(), p.end()), print();
    } else puts("NO");
    return 0;
}

CF549F Yura and Developers

给定一个长度为 $n$ 的序列和数 $k$，求有多少长度大于 $1$ 的区间满足和减最大值是 $k$ 的倍数。

$n \le 3 \times 10^5,k \le 10^6,a_i \le 10^9$

先求出前缀和数组 $pre$。

则条件可以写成 $pre_r \equiv pre_{l-1} + \max \pmod k$。

把 $i$ 插入 $\text{vector}[pre_i \bmod k]$，通过二分可以快速查询区间中有多少前缀和模 $k$ 余 $x$。

求出整个序列的最大值的位置为 $x$。

然后枚举 $x$ 左边的前缀和，查询 $x$ 右边有多少个前缀和与之配对。

因为 $x$ 的位置不确定，所以这样是 $O(n^2\log n)$。

但如果每次枚举左右中较短的一段，则复杂度可降为 $O(n \log^2 n)$。

其实不用真的分治，只需要单调栈求出每个位置作为最大值的极大区间即可。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, K, a[N], L[N], R[N], su[N];
vector <int> v[1000000];
int main() {
    cin >> n >> K;
    rep(i, 1, n) scanf("%d", &a[i]);
    v[0].pb(0);
    rep(i, 1, n) su[i] = (su[i - 1] + a[i]) % K, v[su[i]].pb(i);
    rep(i, 1, n) for(int& j = L[i] = i - 1; j && a[j] <= a[i]; j = L[j]);
    per(i, n, 1) for(int& j = R[i] = i + 1; j <= n && a[j] < a[i]; j = R[j]);
    long long as = 0;
    rep(i, 1, n) if(i - L[i] < R[i] - i) For(j, L[i], i) {
        int t = (su[j] + a[i]) % K;
        #define lb lower_bound
        #define all v[t].begin(), v[t].end()
        as += lb(all, R[i]) - lb(all, i);
    } else For(j, i, R[i]) {
        int t = ((su[j] - a[i]) % K + K) % K;
        as += lb(all, i) - lb(all, L[i]);
    }
    cout << as - n;    
    return 0;
}

CF1144G Two Merged Sequences

给定一个长度为 $n$ 的序列 $A$。

问能否把它拆成一个严格递增序列和一个严格递减序列，如果有解则输出方案。

$n \le 2 \times 10^5$

设 $f_{i,0}$ 表示把序列的前 $i$ 个数拆成一个递增序列和一个递减序列（可以为空），并且 $A_i$ 属于递增序列时，递减序列结尾可能的最大值。$f_{i,1}$ 表示 $A_i$ 属于递减序列时，递增序列结尾可能的最小值。

转移有四种：

• $A_{i-1},A_i$ 都属于递增序列，条件是 $A_{i-1} < A_i$，转移为 $f_{i-1,0} \rightarrow f_{i,0}$ 。
• $A_{i-1},A_i$ 都属于递减序列，情况类似。
• $A_{i-1}$ 属于递减序列，$A_i$ 属于递增序列，条件是 $f_{i-1,1} < A_i$，转移为 $A_{i-1} \rightarrow f_{i,0}$。
• $A_{i-1}$ 属于递增序列，$A_i$ 属于递减序列，情况类似。

为了输出方案，记 $g_{i,0}$ 表示在最优方案中 $A_{i-1}$ 属于哪个序列，$g_{i,1}$ 同理。

实现中可以用 pair <int, int> 把 f 和 g 数组压一起。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define fi first
#define se second
#define mp make_pair

using namespace std;
const int N = 2e5 + 5;
int n, A[N], in[N];
pair <int, int> f[N][2], ans;
int main() {
    cin >> n;
    rep(i, 1, n) scanf("%d", &A[i]);
    f[1][0].fi = N, f[1][1].fi = -1;
    rep(i, 2, n) {
        f[i][0].fi = -1, f[i][1].fi = N;
        if(A[i - 1] < A[i]) f[i][0] = {f[i - 1][0].fi, 0};
        if(A[i - 1] > A[i]) f[i][1] = {f[i - 1][1].fi, 1};
        if(f[i - 1][1].fi < A[i]) f[i][0] = max(f[i][0], mp(A[i - 1], 1));
        if(f[i - 1][0].fi > A[i]) f[i][1] = min(f[i][1], mp(A[i - 1], 0));
    }
    if(~f[n][0].fi || f[n][1].fi < N) {
        puts("YES");
        in[n] = ~f[n][0].fi ? 0 : 1;
        per(i, n, 2) in[i - 1] = f[i][in[i]].se;
        rep(i, 1, n) printf("%d ", in[i]);
    } else puts("NO");
    return 0;
}

CF1305G Kuroni and Antihype

一张有 $n$ 个点的图，每个点的点权为 $a_i$。

点 $u$ 和点 $v$ 连边当且仅当 $a_u \& a_v = 0$。

对于点 $u$，有两种操作：

• 直接涂黑，无贡献。
• 找一个与 $u$ 相邻且已经涂黑的点 $v$，再涂黑 $u$，贡献为 $a_v$。

求涂黑所有点的最大贡献。

$n \le 2 \times 10^5,a_i \le 2 \times 10^5$

首先加入一个点权为 $0$ 的虚点，且初始为黑，则两种操作就可以统一成第二种。

对于每次操作，就从 $u$ 向 $v$ 连一条有向边，得到一个以 $0$ 为根的有根树。

设点 $u$ 的度数为 $degree_u$，则总贡献可以表示为

$$\sum_{u \in V}a_u(degree_u-1)=\sum_{u \in V}a_udegree_u-\sum_{u \in V}a_u = \sum_{(u,v) \in E}a_u + a_v - \sum_{u \in V}a_u$$

如果定义 $(u,v)$ 边权为 $a_u + a_v$，则前一部分为生成树权值，后一部分是定值。

所以问题转化为求最大生成树。

先考虑所有点的点权两两不同。

根据枚举子集的经典结论，边的总数小于 $3^{18}$，但实际只有一半左右，即 $1.7 \times 10^8$ 左右。

考虑 Kruskal 算法，虽然并查集复杂度要乘一个 $\alpha(n)$，但感觉卡不满。

首先不可能存下所有边，更不可能排序，所以考虑从大到小枚举边权。

注意到 $u,v$ 连边当且仅当 $a_u \& a_v = 0$，而边权为 $a_u + a_v$。

直接枚举边权的子集就可以得到两个端点。

剩下的正常做 Kruskal 就行了。

复杂度 $O(3^{18}\alpha(n))$。

点权相同时

当枚举到 $a_u,a_v$ 时，$a_u$ 可能会对应很多的 $u$，设这些 $u$ 构成集合 $U$，$a_v$ 也会对应很多的 $a_v$，设这些 $v$ 构成集合 $V$。

任何一个 $U$ 中的结点和任何一个 $V$ 中的结点都有权值相等的连边，边太多了。

考虑一个等价的连边：

在 $U$ 中选择一个代表元 $u_0$，同理选个 $v_0$，$u_0$ 和 $v_0$ 连边，$u_0$ 和 $U$ 中其他点连边，$v_0$ 和 $V$ 中其他点连边。

对于后两种连边，每个集合只用在第一次访问到时进行，复杂度 $O(3^{18}\alpha(n))$。

UPD：复杂度不带 $O(3^{18}\alpha(n))$，当并查集的 find 的次数不少于 $n\log n$ 时，均摊复杂度为 $O(1)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define upd(a, b) (a = min(a, b))

using namespace std;
const int N = 1 << 18;
typedef long long ll;
int n, a[N], fa[N], sz[N], vis[N];
vector <int> nds[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int main() {
    cin >> n;
    ll as = 0;
    rep(i, 1, n) {
        scanf("%d", &a[i]), as -= a[i];
        nds[a[i]].push_back(i);
    }
    nds[0].push_back(0);
    rep(i, 0, n) fa[i] = i, sz[i] = 1;
    per(S, N - 1, 1) for(int T = S; T > S / 2; --T &= S) {
        if(nds[T].empty() || nds[S ^ T].empty()) continue;
        auto mrg = [&](int u, int v) {
            u = find(u), v = find(v);
            if(u == v) return;
            if(sz[u] < sz[v]) swap(u, v);
            fa[v] = u, sz[u] += sz[v];
            as += S;
            if(sz[u] == n + 1) cout << as, exit(0);
        };
        mrg(nds[T][0], nds[S ^ T][0]);
        if(!vis[T]) for(int u : nds[T]) mrg(u, nds[S ^ T][0]);
        if(!vis[S ^ T]) for(int v : nds[S ^ T]) mrg(nds[T][0], v);
        vis[T] = vis[S ^ T] = 1;
    }
    puts("0");
    return 0;
}

CF1430F Realistic Gameplay

你有一把枪，枪的弹匣量为 $k$。

有 $n$ 波怪物，对于第 $i$ 波，你必须在 $[l_i,r_i]$ 时间内消灭 $a_i$ 只怪物 $(r_i \le l_{i+1})$，你可以在任意时刻打出一发子弹击杀一只怪物且不耗费时间。你每次换弹都需要将弹匣（包括里面的子弹）扔掉，并花费 1 单位的时间。

在保证通关的情况下，需要的最少的子弹数为多少。

$n \le 2000,k \le 10^9, l_i \le r_i \le 10^9,a_i \le 10^9$

考虑什么时候会换弹，要么是当前子弹打完了，而这波怪还没打完，称之为一类换弹；要么是当前这波怪已经打完了，但为了通关而换新弹匣 ，称之为二类换弹。

如果所有二类换弹在哪一波都是确定的，只要按时间线扫描一遍就可以算出所有一类换弹的时间。

因此设 $f_i$ 表示打完前 $i$ 波怪，且在第 $i$ 波进行一次二类换弹需要的最少的子弹数。
转移就从第 $i + 1$ 波开始扫描，同时维护当前弹匣中的子弹数，直到不合法为止。
如果在 $r_j$ 之前消灭了第 $j$ 波的所有怪物，就可以在第 $j$ 波进行一次二类换弹后转移到 $f_j$。
如果能消灭完所有怪就更新 ans。

复杂度 $O(n^2)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define upd(a, b) (a = min(a, b))

using namespace std;
const int N = 2005;
typedef long long ll;
int n, K;
int l[N], r[N], a[N];
ll f[N];
int main() {
    mem(f, 63), f[0] = 0;
    cin >> n >> K;
    rep(i, 1, n) scanf("%d%d%d", &l[i], &r[i], &a[i]);
    rep(i, 0, n - 1) {
        int nw = K;
        rep(j, i + 1, n) {
            int t = (a[j] - nw + K - 1) / K;
            if(t > r[j] - l[j]) break;
            nw += t * K - a[j];
            f[i] += a[j];
            if(j == n) upd(f[j], f[i]);
            else if(t < l[j + 1] - l[j]) upd(f[j], f[i] + nw);
        }
    }
    if(f[n] < 0x3f3f3f3f3f3f3f3f) cout << f[n];
    else puts("-1");
    return 0;
}

CF1498E Two Houses

有一张 $n$ 个点的竞赛图。

不会给这张竞赛图，但会给每个点的入度 $k_i$。

还可以通过交互询问从 $u$ 能否到达 $v$，但一旦回答了”是“，就不能再询问了。

定义一个点对 $(u,v)$ 的价值是 $|k_u-k_v|$。

求所有双向可达的点对中价值最大的一对，或者输出无解。如果有多对，输出任意一对。

$n \le 500$

做法一

考虑一对点 $(u,v)$，由于是竞赛图，$u,v$ 间有连边，不妨设 $u \rightarrow v$。

如果 $v$ 不能到达 $u$，$\exists S,u \in S \land \forall x \in S, y \not \in S,x \rightarrow y$，即集合 $S$ 内的点全部向 $S$ 外的点连边。

$\therefore k_v \ge |S|,k_u < |S| \Rightarrow k_u < k_v$

得到一个结论：如果一对点不双向可达，那么入度大的一定无法到达入度小的。

把所有点对按价值从大到小依次询问，每次询问入度大的能否到达入度小的，如果可以，就直接输出这一对。

如果到最后都没有回答“是”，那么输出无解。

复杂度 $O(n^2)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
const int N = 1000;
char ch[N];
struct Qry {
    int x, y, v;
    bool operator <(const Qry& b)const { return v > b.v; }
} q[N * N];
vector <int> v[N];
int n, idx, k[N];
int main() {
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", &k[i]);
    rep(i, 1, n) rep(j, i + 1, n)
        q[++idx] = k[i] < k[j] ? (Qry){ j, i, k[j] - k[i] } : (Qry){ i, j, k[i] - k[j] };
    sort(q + 1, q + idx + 1);
    rep(i, 1, idx) {
        printf("? %d %d\n", q[i].x, q[i].y);
        fflush(stdout);
        scanf("%s", ch);
        if(ch[0] == 'Y') printf("! %d %d\n", q[i].x, q[i].y), fflush(stdout), exit(0);
    }
    puts("! 0 0"), fflush(stdout);
    return 0;
}

做法二

考虑拓扑序最小的几个强连通分量的并集 $S$，$S$ 内的点全部向 $S$ 外的点连边，所以 $S$ 内所有点的入度和等于 $\binom {|S|}2$，反之亦然。

把所有点按入度从小到大排序，如果前 $m$ 个节点的入度和等于 $\binom m2$，那么前 $m$ 个点一定是拓扑序最小的几个强连通分量的并集，并且不会漏掉，这样就可以分离出所有的强连通分量，直接统计答案即可。

复杂度 $O(n)$，因为排序可以桶排，无需询问。

UPD: 这个结论叫 兰道定理，练习题 「2021 集训队互测」基础图论练习题。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define fi first
#define se second
#define mp make_pair

using namespace std;
const int N = 505;
typedef pair <int, int> P;
int n; P a[N];
int main() {
    cin >> n;
    rep(i, 1, n) scanf("%d", &a[i].fi), a[i].se = i;
    sort(a + 1, a + n + 1);
    int su = 0; P mi(n, 0), ma(-1, 0);
    pair <int, P> as;
    rep(i, 1, n) {
        su += a[i].fi;
        mi = min(mi, a[i]), ma = max(ma, a[i]);
        if(su == i * (i - 1) / 2) {
            if(mi.se ^ ma.se) as = max(as, mp(ma.fi - mi.fi, mp(mi.se, ma.se)));
            mi.fi = n, ma.fi = -1;
        }
    }
    if(as.se.fi) printf("! %d %d\n", as.se.fi, as.se.se);
    else puts("! 0 0");
    fflush(stdout);
    return 0;
}

CF1508C Complete the MST

有一张 $n$ 个点的无向完全图，其中 $m$ 条边的边权已给定。

你需要给剩下的边确定边权，使得所有边的权值异或和为 $0$。

求出所有方案中最小生成树权值的最小值。

$n \le 2 \times 10^5,m \le \min\{2 \times 10^5,\binom n2-1\}$

下面原图指给定的 $m$ 条边构成的图，补图指剩下的边构成的图，MST 指最小生成树。

引理：最优解中补图至多有一条权值非 $0$ 的边。

证明：考虑两条补图边 $e_1,e_2$，它们的权值 $w_1,w_2$ 都大于 $0$。

• 如果它们都不在 MST 上，把 $e_1$ 权值变为 $0$，$e_2$ 权值异或上 $e_1$ 权值，新的 MST 不会变劣。
• 如果它们都在 MST 上，把 $e_1$ 权值变为 $0$，$e_2$ 权值异或上 $e_1$ 权值，因为 $w_1 \oplus w_2 \le w_1 + w_2$，所以新的 MST 不会变劣。
• 如果它们中的一条在 MST 上，一条不在，不妨设 $e_1$ 在 MST 上，把 $e_1$ 权值变为 $0$，$e_2$ 权值异或上 $e_1$ 权值，新的 MST 不会变劣。

综上，如果存在两条权值大于 $0$ 的边，把其中一条的权值变为 $0$，新的 MST 不会变劣。

所以补图中有一条特殊边的权值恰好为给定的 $m$ 条边的权值异或和，其余边的权值均为 $0$。

容易想到枚举一下特殊边在不在 MST 上。

先用 DFS 求出补图的生成森林，用 set 优化枚举未访问的点可以做到 $O(m\log n)$ 的复杂度。

如果补图中存在环，那么补图中一定有边不在 MST 上，故特殊边一定不在 MST 上。把求出的生成森林加入原图后，答案即为该图的最小生成树，复杂度 $O(m\log m)$。

如果不存在环，那么 $n$ 就是 $O(\sqrt m)$ 级别的，如果特殊边在 MST 上，直接用同样的做法；如果不在 MST 上，就需要枚举特殊边是哪一条，每次删去它再沿用以上做法，复杂度 $O(m \log m + nm\alpha(n))$。一个优化：用原图的最小生成树替代原图，复杂度降为 $O(m\log m + n^2\alpha(n))=O(m\log m)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n, m, fa[N], xorsu, eid, tid;
int find(int x) { return x ^ fa[x] ? fa[x] = find(fa[x]) : x; }
int mrg(int u, int v) {
    if((u = find(u)) ^ (v = find(v))) return fa[u] = v;
    return 0;
}
vector <int> G[N];
struct edge {
    int u, v, w;
    bool operator <(const edge& b)const {
        return w < b.w;
    }
} e[N], t[N];
set <int> s;
void dfs(int u) {
    s.erase(u);
    For(i, 0, G[u].size() - 1) {
        int v = G[u][i], nxt = G[u][i + 1];
        while(!s.empty() && *s.rbegin() > v) {
            int vv = *s.upper_bound(v);
            if(vv >= nxt) break;
            t[++tid] = {u, vv}, dfs(vv);
        }
    }
}
int main() {
    cin >> n >> m;
    rep(i, 1, m) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), xorsu ^= e[i].w;
        G[e[i].u].pb(e[i].v), G[e[i].v].pb(e[i].u);
    }
    rep(i, 1, n) G[i].pb(0), G[i].pb(n + 1), sort(G[i].begin(), G[i].end()), s.insert(i);
    while(!s.empty()) dfs(*s.begin());
    sort(e + 1, e + m + 1);
    rep(i, 1, n) fa[i] = i;
    rep(i, 1, m) if(mrg(e[i].u, e[i].v)) e[++eid] = e[i];
    if(tid < n * (n - 1ll) / 2 - m) {
        rep(i, 1, n) fa[i] = i;
        rep(i, 1, tid) mrg(t[i].u, t[i].v);
        ll as = 0;
        rep(i, 1, eid) if(mrg(e[i].u, e[i].v)) as += e[i].w;
        cout << as;
    } else {
        ll as = 1e18;
        rep(i, 0, tid) {
            rep(j, 1, n) fa[j] = j;
            rep(j, 1, tid) if(j ^ i) mrg(t[j].u, t[j].v);
            ll su = i ? 0 : xorsu;
            rep(j, 1, eid) if(mrg(e[j].u, e[j].v)) su += e[j].w;
            as = min(as, su);
        }
        cout << as;
    }
    return 0;
}

CF1516E Baby Ehab Plays with Permutations

给定 $n,k$，对于每个 $i \in [1,k]$，你需要求出有多少个长度为 $n$ 的排列能通过恰好 $i$ 次交换操作变成 $\{1,2,\cdots,n\}$。

答案对 $10^9+7$ 取模。

$n \le 10^9,k \le 200$

先考虑这样一个问题：给定一个排列 $P$，最少交换几次才能变成 $\{1,2,\cdots,n\}$。

把排列 $P$ 理解成一个置换，并分解成循环，不难发现 $i$ 个元素的循环需要交换 $i-1$ 次。

这样，如果 $P$ 的循环节为 $x$，则总的交换次数为 $n-x$。

涉及到点数和循环数不难想到第一类斯特林数。

$i$ 的答案即 ${n \brack n-i}+{n \brack n-i+2}+{n \brack n-i+4} + \cdots$。

问题是 $n$ 太大了，不能递推求出第一类斯特林数。

由于 $i$ 次交换最多影响 $2i$ 个元素，一个合法的排列 $P$ 至多有 $2i$ 个位置 $j$ 满足 $j \ne P_j$。

可以枚举有多少个 $j$ 满足 $j \ne P_j$，如果有 $x$ 个，对答案的贡献为 $\binom nxf_{x,x-i}$。

其中 $f_{i,j}$ 表示有多少个长度为 $i$ 的错排循环节为 $j$，它可以通过第一类斯特林数容斥得到：

$$f_{i,j}={i \brack j}-\sum_{k=1}^j\binom ikf_{i-k,j-k}$$

复杂度 $O(k^3)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define pb push_back

using namespace std;

typedef long long ll;
const int N = 205;
const ll P = 1e9 + 7;

int n, K, C[N * 2][N * 2];
ll f[N * 2][N], as[N];

ll Pow(ll a, int n, ll r = 1) {
    for(; n; n /= 2, a = a * a % P)
    if(n & 1) r = r * a % P;
    return r;
}
ll calc(int x) {
    ll a = 1, b = 1;
    while(x) b = b * x-- % P, a = a * (n - x) % P;
    return a * Pow(b, P - 2) % P;
}
int main() {
    cin >> n >> K;
    f[0][0] = 1;
    rep(i, 1, K * 2) rep(j, 1, K)
        f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j]) % P;
    rep(i, 0, K * 2) {
        C[i][0] = 1;
        rep(j, 1, i) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
    rep(i, 1, K * 2) rep(j, 1, i) rep(k, 1, j)
        (f[i][j] -= C[i][k] * f[i - k][j - k]) %= P;
    rep(i, 0, K) {
        rep(j, i, i * 2) (as[i] += f[j][j - i] * calc(j)) %= P;
        if(i >= 2) (as[i] += as[i - 2]) %= P;
        if(i) printf("%lld ", (as[i] + P) % P);
    }
    return 0;
}

CF1515F Phoenix and Earthquake

给定一张 $n$ 个点 $m$ 条边的无向连通图和正整数 $x$，点有非负权值 $a_i$。

如果一条边 $(u,v)$ 满足 $a_u+a_v \ge x$，可以将 $u,v$ 缩起来，新点的点权为 $a_u+a_v-x$。

判断这张图是否可以缩成一个点并给出方案。

$n,m \le 3 \times 10^5,x,a_i \le 10^9$

首先将每个点的点权减去 $x$，则合并条件变为 $a_u + a_v \ge -x$，每次合并后新点的点权为 $a_u + a_v$。

结论：这张图可以缩成一个点的充要条件是点权和大于等于 $-x$。

必要性显然，充分性可以考虑这个构造：每次选择点权最大的点 $u$ 的任意一条边。

构造的正确性可以考虑反证法，设这条边为 $(u,v)$，假设这条边不行，即 $a_u+a_v<-x$。

进一步 $\because a_v \ge -x,\therefore a_u < 0$

由于 $a_u$ 是最大值，因此所有点的点权都是负数，那么 $a_u+a_v \ge \sum a_i \ge -x$，推出矛盾！

至此，已经得到一个做法。

但还有更简单的做法，根据上面结论，任意求一棵生成树都有可行方案。

先从叶子向根依次考虑每个结点，如果这个结点权值非负，则选择它和它父亲的连边，再从根向叶子依次考虑每个结点，如果它和它父亲的连边还没选，则选择这条边。

证明考虑数学归纳法即可。

在实现中不必 DFS 两遍，DFS 过程中把没选的边压栈即可。

复杂度 $O(n)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define eb emplace_back

using namespace std;

const int N = 3e5 + 5;

int n, m, x, vis[N], as[N], L, R;
long long a[N], su;
vector <pair <int, int>> G[N];

void dfs(int u) {
    vis[u] = 1;
    for(auto [v, i] : G[u]) if(!vis[v])
        dfs(v), a[v] >= 0 ? a[u] += a[v], as[L++] = i : as[R--] = i;
}
int main() {
    cin >> n >> m >> x;
    rep(i, 1, n) scanf("%lld", &a[i]), su += a[i] -= x;
    int u, v;
    rep(i, 1, m) scanf("%d%d", &u, &v), G[u].eb(v, i), G[v].eb(u, i);
    if(su + x < 0) puts("NO"), exit(0);
    puts("YES"), L = 2, R = n, dfs(1);
    rep(i, 2, n) printf("%d\n", as[i]);
    return 0;
}

CF1519E Off by One

给定平面上的 $n$ 个点 $(\frac {a_i}{b_i},\frac {c_i}{d_i})$，定义一个点 $(x,y)$ 的派生点为点 $(x+1,y)$ 和点 $(x,y+1)$。

两个点 $A,B$ 能够匹配当且仅当 $A$ 的一个派生点和 $B$ 的一个派生点在同一条过原点的直线上。

求出最大匹配的大小和任意一种方案。

$n \le 2 \times 10^5,1 \le a_i,b_i,c_i,d_i \le 10^9$

两个第一象限的点在同一条过原点的直线上等价于两个点的横纵坐标之比相等。

定义一个点 $(x,y)$ 的派生值为 $\frac {x+1}y$ 和 $\frac x{y+1}$。

两个点 $A,B$ 能够匹配即拥有同一个派生值。

把所有的派生值抽象成点，给定的点抽象成边，匹配条件进一步转化为两条边拥有公共顶点。

引理：一个连通无向图能够给每条边定向使得每个点入度为偶数当且仅当边数为偶数。

证明：边数为奇数显然不行，下面给出边数为偶数时的构造：

先建树 DFS 树，所有反向边都向上，如果两个端点都在点 $u$ 子树内的边的数量为偶数，则 $u$ 与其父亲的连边（如果存在）向上，否则向下。

通过引理不难推出一个边数为 $m$ 的连通图的答案为 $\lfloor \frac m2 \rfloor$，求方案可以先给每条边定向，再把每个点的所有入边两两配对。

只需要对每个连通块做一遍即可。

最后一个问题：派生值是分子分母都是 $10^{18}$ 级别的分数，离散化时需要排序，但如何比较。

一种方法是转 __int128 交叉相乘比较大小。其实不一定要按分数值排序，双关键字排序同样能实现离散化，先约分，再以分子、分母为两关键字比较则是另一种更快的方法。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back

using namespace std;
const int N = 4e5 + 5;
typedef long long ll;
ll K1[N], K2[N];
int n, ord[N], id[N];
vector <pair <int, int>> G[N];
vector <pair <int, int>> as;
int idx, dfn[N], sz[N];
void add(int u, int v, int i) {
    G[u].eb(v, i), G[v].eb(u, i);
}
void dfs(int u, int f) {
    dfn[u] = ++idx;
    int lst = 0;
    auto ins = [&](int x) {
        if(lst) as.eb(lst, x), lst = 0;
        else lst = x;
    };
    for(auto [v, w] : G[u]) if(!dfn[v]) {
        dfs(v, w), sz[u] += sz[v];
        if(~sz[v] & 1) ins(w);
    } else if(dfn[v] > dfn[u]) ins(w);
    else sz[v]++;
    if(lst && f) as.eb(lst, f);
}
int main() {
    cin >> n;
    int a, b, c, d;
    rep(i, 1, n) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        K1[i * 2 - 1] = ll(a + b) * d, K1[i * 2] = (ll)a * d;
        K2[i * 2 - 1] = (ll)b * c, K2[i * 2] = b * ll(c + d);
    }
    n *= 2;
    rep(i, 1, n) {
        ord[i] = i;
        ll g = __gcd(K1[i], K2[i]);
        K1[i] /= g, K2[i] /= g;
    }
    auto cmp = [](int x, int y) {
        return K1[x] ^ K1[y] ? K1[x] < K1[y] : K2[x] < K2[y];
    };
    sort(ord + 1, ord + n + 1, cmp);
    rep(i, 1, n) id[i] = lower_bound(ord + 1, ord + n + 1, i, cmp) - ord;
    rep(i, 1, n / 2) add(id[i * 2 - 1], id[i * 2], i);
    rep(i, 1, n) dfs(i, 0);
    cout << as.size() << endl;
    for(auto [u, v] : as) printf("%d %d\n", u, v);
    return 0;
}

CF1498D Bananas in a Microwave

有一个变量 $k$ 初始为 $0$。

对于时刻 $i=1,2,3,\cdots,n$，给定 $t_i,x_i,y_i$，且执行以下操作：

• 若 $t_i=1$，选择 $a \in [0,y_i]$，执行 $a$ 次 $k=\lceil k + x_i \rceil$。
• 若 $t_i=2$，选择 $a \in [0,y_i]$，执行 $a$ 次 $k=\lceil k \cdot x_i \rceil$。

其中 $x_i$ 是实数。

对于每个 $j \in [1,m]$，求可能的最小时刻使得 $k=j$。

$n \le 200,y_i \le m \le 10^5$

对于 $t_i=1$，有 $0 < x_i \le m$，对于 $t_i=2$，有 $1 < x_i \le m$。

对于每个时刻 $i$，维护数组 $ok_j$ 表示经过前 $i$ 个时刻能否使 $k=j$。

设 $next_j=\begin{cases}\lceil j + x_i \rceil&(t_i=1)\\\lceil j \cdot x_i \rceil&(t_i=2)\end{cases}$。

因为 $\forall j \ne k,next_j \ne next_k$，所以 $j \rightarrow next_j$ 连边后形成若干条链。

假设一条链上的结点分别为 $v_1,v_2,v_3,\cdots,v_s$

对于 $v_j$，如果 $\exist k \in [j-y_i,j)$，满足 $ok_k=1$，那么在第 $i$ 时刻 $k$ 可以等于 $v_j$。

对每条链扫描一遍即可求出在第 $i$ 时刻 $k$ 可以等于哪些值。

复杂度 $O(nm)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define upd(a, b) (a = min(a, b))

using namespace std;
typedef long long ll;
const int N = 1e5, M = N + 5;
int n, m, f[M], nxt[M], vis[M], ok[M];
int main() {
    mem(f, -1);
    int t, y; ll x;
    cin >> n >> m;
    f[0] = 0;
    rep(k, 1, n) {
        scanf("%d%lld%d", &t, &x, &y);
        if(t == 1) {
            x = (x + N - 1) / N;
            rep(i, 0, m) nxt[i] = min(i + x, m + 1ll);
        } else {
            nxt[0] = m + 1;
            rep(i, 1, m) nxt[i] = min((i * x + N - 1) / N, m + 1ll);
        }
        mem(vis, 0);
        rep(i, 0, m) if(!vis[i]) {
            vector <int> v;
            for(int j = i; j <= m; j = nxt[j]) vis[j] = 1, v.push_back(j);
            int cnt = 0;
            For(j, 0, v.size()) {
                if(cnt) ok[v[j]] = 1;
                cnt += f[v[j]] != -1;
                if(j >= y) cnt -= f[v[j - y]] != -1;
            }
        }
        rep(i, 0, m) if(!~f[i] && ok[i]) f[i] = k;
    }
    rep(i, 1, m) printf("%d ", f[i]);
    return 0;
}

CF1498F Christmas Game

给定一棵 $n$ 个点的树和 $k$，每个结点上有 $a_i$ 个物品，Alice 和 Bob 在上面玩游戏。

在确定根之后，两个玩家轮流选择任意一个存在 $k$ 级祖先的结点 $u$，然后把 $u$ 的任意个物品移到 $u$ 的 $k$ 级祖先上。

最后没有物品可取的人输。

问当每个结点作为根时，谁必胜。

$n \le 10^5, k \le 20,a_i \le 10^9$

当 $k=1$ 时，它几乎是一个阶梯 NIM 游戏。

设根结点深度为 $0$，根据阶梯 NIM 游戏的结论，原问题等价于所有深度为奇数的结点做 NIM 游戏，即先手必胜当且仅当所有深度为奇数的结点的 $a_i$ 异或和不为 $0$。

对于一般的情况，先手必胜当且仅当

$$\bigoplus_{\big\lfloor \frac {depth_u}k \big\rfloor \text{ is odd}}a_u \ne 0$$

设 $f_{u,i}$ 表示以 $u$ 为根的子树里，所有满足 $depth_v - depth_u \equiv i \pmod {2k}$ 的结点 $v$ 的点权异或和。

然后换根 DP 一下即可。

复杂度 $O(nk)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, K, a[N];
ll f[N][40], ans[N];
vector <int> G[N];
void add(int u, int v) {
    For(i, 0, K) f[u][(i + 1) % K] ^= f[v][i];
}
void dfs(int u, int fa) {
    f[u][0] = a[u];
    for(int v : G[u]) if(v ^ fa) dfs(v, u), add(u, v);
}
void Dfs(int u, int fa) {
    For(i, K / 2, K) ans[u] ^= f[u][i];
    for(int v : G[u]) if(v ^ fa) add(u, v), add(v, u), Dfs(v, u), add(v, u), add(u, v);
}
int main() {
    cin >> n >> K, K *= 2;
    int u, v;
    rep(i, 2, n) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    rep(i, 1, n) scanf("%d", &a[i]);
    dfs(1, 0), Dfs(1, 0);
    rep(i, 1, n) printf("%d ", ans[i] != 0);
    return 0;
}

CF493E Vasya and Polynomial

原题题意：给你三个正整数 $a$，$b$，$c$，问多少个非负整系数多项式 $F$, 满足 $F(a)=b \land F(b)=c$

$1 \le a, b, c \le 10^{18}$

若 $a=1,b=1$ 答案显然。

否则因为非负整系数的限制，多项式系数是 $\log$ 级别的。

我们考虑一个更一般的问题：问多少个非负整系数多项式 $F$, 满足

$$F(a)=x \land F(b)=y \land x \le b$$

设 $F$ 的常数项为 $V$。

根据 $F(a)=x$ 和 $F(b)=y$ 知道 $V \le x, V \equiv y\ (mod\ b)$。

分两种情况。

1. 当 $x=b \land b\ |\ y$ 时，则 $V=0 \lor V=x$，

   若 $V=x$，因为 $F(a)=x$, 所以 $F$ 只能是常函数 $F(x)=V$，当 $x \ne y$ 时无解。

   另一种情况，因为 $F(a)-V=x-V$，所以 $a$ 要能整除 $x-V$，如果不整除就无解。

   否则令 $G(x)=\dfrac{F(x)-V}x$，有 $G(a)=\dfrac{x-V}a,G(b)=\dfrac{y-V}b$。

   显然 $\dfrac{x-V}a \le x \le b$，因此就转化为了一个子问题。

2. 当 $x < b \lor b \not |\ y$ 时，显然 $V=y \mod b$，可以转化为子问题。

边界条件是 $xy=0$, 这意味着无解（$F(x)=0$ 不算合法）。

然后就可以求出多项式的数量了。

code

typedef long long ll;
ll a, b, c; 
find(ll x, ll y) {
    if(!x || !y) return 0; ll v = y % b;
    return ((x - v) % a ? 0 : find((x - v) / a, (y - v) / b)) + (x == y);
}
main() {
    scanf("%lld%lld%lld", &a, &b, &c);
    if(a == 1 && b == 1) puts(c > 1 ? "0" : "inf");
    else printf("%d", find(b, c));
}

如何求次数最高的前提下字典序最小的多项式？

分析递归过程，每个次数的合法多项式最多一个，递归时优先选择次数高的就行了。

code

typedef long long ll;
cnt, ans; ll a, b, c, A[100];
find(ll x, ll y, int d) {
    if(!x || !y) return;
    ll v = A[d] = y % b;
    if((x - v) % a == 0) find((x - v) / a, (y - v) / b, d + 1);
    if(x == y) { if(!ans) A[cnt = d] = x; ans++; }
}
main(T) {
    for(scanf("%d", &T); T--; puts("")) {
        scanf("%d%d%d", &a, &b, &c);
        if(a == 1 && b == 1) puts(c > 1 ? "0" : "-1");
        else {
            ans = 0, find(b, c, 0);
            printf("%d", ans);
            if(ans) for(printf("\n%d ", cnt); ~cnt; printf("%lld ", A[cnt--]));
        }
    }
}

CF868E Policeman and a Tree

一棵 $n$ 个结点的边带权树，有一个警察初始在 $s$ 点，速度为 $1$，树上分布有 $m$ 个罪犯，速度为任意大，如果罪犯和警察在同一个结点就会被干掉，警察希望干掉所有罪犯的时间尽量短，而罪犯希望最大化这个时间，假设每个人都以最优策略行动，求这个时间。

$1 \le n, m, w_i \le 50$，$w_i$ 为边权。

所有罪犯初始不在 $s$ 点，一个结点可能会有多个罪犯。

状态设计

考虑这个过程是怎样的。

当警察在结点 $1$ 时，由于罪犯速度任意大，但不能经过警察，所以罪犯分布在被结点 $1$ 隔开的三个部分中，并且可以在所属部分的任意位置上，不妨假设罪犯全部分布在所有与结点 $1$ 相邻的结点 $2,3,4$ 上。

图上的红数字表示该结点上有多少名罪犯。

当警察从结点 $1$ 走到结点 $4$ 时，结点 $4$ 上的两名罪犯就需要走到结点 $5,6$ ，同时结点 $2,3$ 上的两名罪犯可以一起走到结点 $1$。

容易想到用警察所在的结点 $u$ 和所有与结点 $u$ 相邻的结点上分别有多少名罪犯来表示一个状态。
但一个结点的度数是 $O(n)$ 级别的，因此状态数爆炸。

另一个描述状态的想法是警察当前在哪条边上，这条边的两端分别有多少名罪犯。
然后状态数就减少成了 $O(n^3)$，非常少。

因此我们用 $f_{i,j,k}$ 表示当前总共还剩 $i$ 名罪犯，警察刚走上 $j = u \rightarrow v$ 这条有向边（警察和 $u$ 的距离忽略不计），结点 $v$ 上有 $k$ 名罪犯。

转移

假设当前总共还剩 $i$ 名罪犯，警察在有向边 $j = u \rightarrow v$ 上，边权为 $w$，结点 $v$ 上有 $k$ 名罪犯。

如果结点 $v$ 是叶子结点，显然

$$f_{i,j,k}=f_{i-k,\bar j,i-k} + w$$

其中 $\bar j$ 是 $j$ 的反向边。

另一种情况：

结点 $4$ 上的 $k$ 名罪犯必须要分为两波，其中 $a$ 名跑到了结点 $5$，$b$ 名跑到了结点 $6$。
警察会下一步会在 $4 \rightarrow 5$ 和 $4 \rightarrow 6$ 中选择较优的一条有向边。

罪犯为了最大化时间：

$$f_{i,1 \rightarrow 4,k} = \max_{a+b=k}\min \lbrace f_{i,4 \rightarrow 5,a},f_{i,4 \rightarrow 6,b}\rbrace + w$$

一般地，设结点 $v$ 除 $u$ 以外的相邻点分别为 $a_1,a_2,a_3,\cdots,a_d$，则转移方程为：

$$f_{i,j,k}=\max_{c_1+c_2+\cdots+c_d=k}\min_{s=1}^df_{i,v \rightarrow a_s,c_s} + w$$

下面给出一种复杂度比较优秀的贪心算法实现第二种转移：

引理：若求 $f_{i,j,k}$ 时的决策为 $c_1,c_2,\cdots,c_d$。
那么求 $f_{i,j,k+1}$ 时的决策 $\bar c_1,\bar c_2,\cdots,\bar c_d$ 一定是在 $c_1,c_2,\cdots,c_d$ 中的某个数 $+1$ 得到的。
并且 $+1$ 的这个 $c_x$ 满足

$$f_{i,v \rightarrow a_x,c_x+1}=\max_{s=1}^df_{i,v \rightarrow a_s,c_s+1}$$

证明：首先在总人数和位置相同的情况下，警察追的人越多，剩下的时间就越短。
故 $f_{i,j,0} \ge f_{i,j,1} \ge f_{i,j,2} \ge \cdots \ge f_{i,j,i}$。

考虑

$$\begin{aligned} \forall x \le f_{i,j,k}&\exists c_1,c_2,\cdots,c_d,\\&f_{i,v \rightarrow a_1,c_1} \ge x\\&f_{i,v \rightarrow a_2,c_2} \ge x\\&\cdots\\&f_{i,v \rightarrow a_d,c_d} \ge x \end{aligned}$$

由二分答案算法的 check 函数可知：若 $m_i$ 是 $f_{i,v \rightarrow a_i}$ 数列中最后一个大于等于 $x$ 的位置，
则 $m_1+m_2+\cdots+m_d \ge k$。

而以这种决策的构造方式，一定有 $c_1 \le m_1,c_2 \le m_2, \cdots, c_d \le m_d$，因此通过该决策得到的值一定不劣于 $x$。

因此可以用一个大根堆维护那个 $x$，可以在 $O(n\log n)$ 的时间同时求出 $f_{i,j,0},f_{i,j,1},\cdots,f_{i,j,i}$。

复杂度 $O(n^3\log n)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
const int N = 55, Inf = 1e9;
int n, s, m, ev[N * 2], ew[N * 2], cnt[N], deg[N];
vector <int> G[N];
int f[N][N * 2][N];
void solve(int, int);
int dp(int i, int j, int k) {
    if(!f[i][j][k]) solve(i, j);
    return f[i][j][k];
}
struct node {
    int i, e, c;
    int val()const { return c < i ? dp(i, e, c + 1) : 0; }
    bool operator <(const node& b)const { return val() < b.val(); }
};
void solve(int i, int j) {
    f[i][j][0] = Inf;
    if(deg[ev[j]] == 1)
        rep(k, 1, i) f[i][j][k] = k < i ? dp(i - k, j ^ 1, i - k) + ew[j] : ew[j];
    else {
        priority_queue <node> q;
        for(int e : G[ev[j]]) if(e ^ j ^ 1) q.push({ i, e, 0 });
        rep(k, 1, i) {
            node x = q.top(); q.pop();
            f[i][j][k] = min(f[i][j][k - 1], x.val() + ew[j]);
            x.c++, q.push(x);
        }
    }
}
int dfs(int u, int fa) {
    int res = cnt[u];
    for(int e : G[u]) if(ev[e] ^ fa) res += dfs(ev[e], u);
    return res;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    int u, v, w;
    rep(i, 2, n) {
        int a = i * 2, b = a + 1;
        cin >> u >> v >> w, deg[ev[a] = v]++, deg[ev[b] = u]++, ew[a] = ew[b] = w;
        G[u].push_back(a), G[v].push_back(b);
    }
    cin >> s >> m;
    rep(i, 1, m) cin >> u, cnt[u]++;
    int ans = Inf;
    for(int e : G[s]) ans = min(ans, dp(m, e, dfs(ev[e], s)));
    cout << ans;
    return 0;
}

CF555E Case of Computer Network

给定一张 $n$ 个点 $m$ 条边的无向图和 $q$ 组有序点对 $(s_i,t_i)$。

询问是否可以给每条边定向，使得所有的 $s_i$ 都能到达 $t_i$。

$n,m,q \le 2 \times 10^5$ 不保证图连通，可能有重边。

先假设有解，尝试求出一组解，再判定这组解合不合法。

构造解

一个经典结论：

一个边双连通分量存在一种给每条边定向的方案，使之成为强连通分量。

一个强连通分量把有向边变成无向边后成为边双连通分量。

对于前者直接让树边向下，反向边向上即可。

对于后者考虑一条有向边的两个端点可以相互到达，推出这条边在一个简单环上。

把图中的边双全部定向成强连通分量，接下来只需要给所有桥定向，以使 $s_i$ 所在的边双能到达 $t_i$ 所在的边双。

其实无需求边双，只需求出哪些边是桥即可，由于此题有重边，tarjan 算法应当记录上一条边而不是父亲。

建出 dfs 树，对于每组 $(s_i,t_i)$，要求 $s_i$ 到 $t_i$ 路径上的桥由 $s_i$ 指向 $t_i$。

让 $s_i \rightarrow lca$ 上的边 $+1$，$lca \rightarrow t_i$ 上的边 $-1$，树上差分转换为 $s_i$ 处 $+1$，$t_i$ 处 $-1$，$lca$ 处不变。

一条边的最终权值如果为正，则必须向上，为负则必须向下，为 $0$ 则都可以。

判定

检验 $s_i \rightarrow lca$ 上的边是否全部为正，$lca \rightarrow t_i$ 上的边是否全部为负。

记 $up_u$ 表示从 $u$ 开始只经过非桥边和权值为正的桥边能到达的深度最小的结点。

$down_u$ 表示从 $u$ 开始只经过非桥边和权值为负的桥边能到达的深度最小的结点。

如果 $up_{s_i}$ 和 $down_{t_i}$ 中深度较大者是 $s_i$ 和 $t_i$ 的公共祖先 $(s_i,t_i)$ 就合法，使用 dfs 序可判定。

复杂度 $O(n)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
const int N = 2e5 + 5;
int n, m, q, idx, dfn[N], suf[N], cut[N];
vector <pair <int, int>> G[N];
int vis[N], sz[N], s[N], t[N], up[N], down[N];
int dfs(int u, int lst) {
    int lowu = dfn[u] = ++idx;
    for(auto [v, w] : G[u]) if(!dfn[v]) {
        int lowv = dfs(v, w);
        lowu = min(lowu, lowv), cut[v] = lowv > dfn[u];
    } else if(w ^ lst && dfn[v] < dfn[u]) lowu = min(lowu, dfn[v]);
    suf[u] = idx;
    return lowu;
}
void Dfs(int u) {
    vis[u] = 1;
    for(auto [v, w] : G[u]) if(!vis[v]) Dfs(v), sz[u] += sz[v];
}
void DFs(int u, int fa) {
    vis[u] = 1, up[u] = up[fa], down[u] = down[fa];
    if(!fa || (cut[u] && sz[u] <= 0)) up[u] = u;
    if(!fa || (cut[u] && sz[u] >= 0)) down[u] = u;
    for(auto [v, w] : G[u]) if(!vis[v]) DFs(v, u);
}
int main() {
    cin >> n >> m >> q; 
    int u, v;
    rep(i, 1, m) {
        scanf("%d%d", &u, &v);
        G[u].push_back({v, ++idx}), G[v].push_back({u, idx});
    }
    idx = 0;
    rep(i, 1, n) if(!dfn[i]) dfs(i, 0);
    rep(i, 1, q) scanf("%d%d", &s[i], &t[i]), sz[s[i]]++, sz[t[i]]--;
    rep(i, 1, n) if(!vis[i]) Dfs(i);
    mem(vis, 0);
    rep(i, 1, n) if(!vis[i]) DFs(i, 0);
    rep(i, 1, q) {
        int lca = dfn[up[s[i]]] > dfn[down[t[i]]] ? up[s[i]] : down[t[i]];
        if(dfn[s[i]] > dfn[t[i]]) swap(s[i], t[i]);
        if(dfn[s[i]] < dfn[lca] || dfn[t[i]] > suf[lca]) puts("No"), exit(0);
    }
    puts("Yes");
    return 0;
}

CF845F Guards In The Storehouse

给定一个 $n \times m$ 的网格，有些位置是障碍，其他是空地。

在一个空地放灯可以照亮这个灯向右，向下第一个障碍前的所有方格。

求有多少种在空地上放灯的方案，使得最多 $1$ 个空地没有被照亮，对 $10^9+7$ 取模。

$nm \le 250$

$\land$ 是逻辑与，$\lor$ 是逻辑或。

首先 $nm \le 250 \Rightarrow \min\{n,m\} \le 15$。

如果 $n < m$，就可以将行列转置，问题不变，但 $m \le 15$ 了。

容易想到对每一行状压，状压一行中每个格子向上第一个障碍前是否有灯（即这个格子是否有向下的光）。

这样时间复杂度过高，感觉行不通，于是考虑压轮廓线，按照从上到下，从左到右的顺序放灯。

设 $f_{i\,a,b,S}$ 表示目前将要决定格子 $i=(x,y)$ 放不放灯，$a$ 表示从 $i$ 向左第一个障碍前是（$1$）否（$0$）有灯（即 $i$ 左边是否有向右的光），$b$ 表示有几个目前已决定有没有放灯的空地没有被照亮，而 $S$ 是压的是第 $x$ 行前 $y-1$ 个格子和第 $x-1$ 行后 $m-y+1$ 个格子上是（$1$）否（$0$）有向下的光。

图中的情况 $a = 0, b = 1, S = \{0,0,1,0,1\}$。

转移就三种情况（先不考虑从一行最后一个格子转移到下一行第一个格子的情况）：

• 格子 $i$ 是障碍，那么它会挡住向右和向下的光，形式化地：

  $$a \rightarrow 0,S \rightarrow S \setminus \{y\}$$

  f[i][a][b][S] 转移到 f[nxt][0][b][~(~S | 1 << y)]。

• 格子 $i$ 是空地，在格子 $i$ 放灯，那么它会产生向右和向下的光。

  $$a \rightarrow 1,S \rightarrow S \cup \{y\}$$

  f[i][a][b][S] 转移到 f[nxt][1][b][S | 1 << y]

• 格子 $i$ 是空地，不在格子 $i$ 放灯，那么还要考虑 $i$ 会不会被照亮。

  如果 $a=1 \lor y \in S$，那么 $i$ 会被照亮，$a,b$ 和 $S$ 都不变，否则 $i$ 不会被照亮， $b$ 必须为 0，转移后变为 $1$，$a$ 和 $S$ 不变。

当 $i$ 是一行最后一个格子时，唯一区别是转移后 $a$ 变为 $0$，因此在代码里无需单独讨论。

答案就是格子 $(n+1,1)$ 的所有 f 值之和，因为状态的定义是目前将要决定这个格子放不放灯。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
typedef long long ll;
const ll P = 1e9 + 7;
int n, m, f[255][2][2][1 << 15]; char s[255][255];

int main() {
    cin >> n >> m;
    For(i, 0, n) scanf("%s", s[i]);
    if(n < m) {
        For(i, 0, n) For(j, i + 1, m) swap(s[i][j], s[j][i]);
        swap(n, m);
    }
    f[0][0][0][0] = 1;
    For(i, 0, n) For(j, 0, m) rep(a, 0, 1) rep(b, 0, 1) For(S, 0, 1 << m) {
        int x = f[i * m + j][a][b][S], nxt = i * m + j + 1;
        if(!x) continue;
        if(s[i][j] == 'x') (f[nxt][0][b][~(~S | 1 << j)] += x) %= P;
        else {
            (f[nxt][j < m - 1][b][S | 1 << j] += x) %= P;
            if(a | (S >> j & 1)) (f[nxt][a & (j < m - 1)][b][S] += x) %= P;
            else if(!b) (f[nxt][0][1][S] += x) %= P;
        }
    }
    int as = 0;
    rep(b, 0, 1) For(S, 0, 1 << m) (as += f[n * m][0][b][S]) %= P;
    cout << as;
    return 0;
}

CF908G New Year and Original Order

定义 $S(x)$ 表示把 $x$ 各数位上的数排序后得到的新数，$S(353594)=334559$。

给定 $n$，求 $\sum\limits_{i=1}^nS(i) \bmod 10^9+7$。

$n \le 10^{700}$

设 $n$ 总共 $m$ 位，$h_{x,i}$ 表示 $x$ 有多少个数位上的数大于等于 $i$。

然后发现 $S(x) = \sum\limits_{i=1}^9 \underbrace{111\cdots 1}=\frac 19\sum\limits_{i=1}^910^{h_{x,i}}-1=\frac 19\sum\limits_{i=1}^9\sum\limits_{j=0}^{m}(10^j-1)\sum\limits_{k=1}^n[h_{k,i}=j]$
                                  $h_{x,i}$ 个 $1$

因此对每个 $i,j$ 求出 $\sum\limits_{k=1}^n[h_{k,i}=j]$ 即可求得答案。

数位 DP 即可，复杂度 $O(100m^2)$。

也可以组合计数：

先让 n++，问题变成求 $\sum_{x < n}S(x)$。

定义第 $i$ 位是从最高位开始的第 $i$ 位，$a_i$ 表示 $n$ 的第 $i$ 位。

先枚举数 $x$ 和 $n$ 的 LCP $i \in [0,m)$，再枚举 $x$ 在第 $i+1$ 位上的值 $j \in [0,a_{i+1})$，则所有 $x$ 的贡献为：

这里 $k$ 表示低 $m-i-1$ 位中有多少位大于等于 $d$。

$$\frac 19\sum_{d=1}^9\sum_{k=0}^{m-i-1}\binom {m-i-1}k(10-d)^kd^{m-i-1-k}(10^{\sum_{s=1}^i[a_s \ge d]+[j \ge d]+k}-1)$$

故答案为：

$$\begin{aligned} &\frac 19\sum_{i=0}^{m-1}\sum_{j=0}^{a_{i+1}-1}\sum_{d=1}^9\sum_{k=0}^{m-i-1}\binom {m-i-1}k(10-d)^kd^{m-i-1-k}(10^{\sum_{s=1}^i[a_s \ge d]+[j \ge d]+k}-1)\\ &=\frac 19\sum_{i=0}^{m-1}\sum_{j=0}^{a_{i+1}-1}\sum_{d=1}^9\left(\left(10^{\sum_{s=1}^i[a_s \ge d]+[j \ge d]}\sum_{k=0}^{m-i-1}\binom {m-i-1}k(100-10d)^kd^{m-i-1-k}\right)-10^{m-i-1}\right)\\ &=\frac 19\sum_{i=0}^{m-1}\sum_{j=0}^{a_{i+1}-1}\sum_{d=1}^9\left(10^{\sum_{s=1}^i[a_s \ge d]+[j \ge d]}(100-9d)^{m-i-1}-10^{m-i-1}\right)\\ &=\frac 19\sum_{i=0}^{m-1}\sum_{d=1}^9\left(10^{\sum_{s=1}^i[a_s \ge d]}(10\max\{a_{i+1}-d,0\}+\min\{a_{i+1},d\})(100-9d)^{m-i-1}-a_{i+1}10^{m-i-1}\right)\\ &=\frac 19\sum_{i=1}^m\sum_{j=1}^9\left(10^{\sum_{s=1}^{i-1}[a_s \ge j]}(100-9j)^{m-i}(10\max\{a_i-j,0\}+\min\{a_i,j\})-a_i10^{m-i}\right) \end{aligned}$$

$\sum_{s=1}^i[a_s \ge d],(100-9d)^{m-i-1},10^{m-i-1}$ 可以枚举 $i$ 时顺便维护。

复杂度 $O(10m)$。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
typedef long long ll;
const ll P = 1e9 + 7;
int n, a[705]; char s[705];
ll Pow[705][11];
int main() {
    cin >> s, n = strlen(s);
    rep(i, 1, n) a[i] = s[n - i] - 48;
    int i = 1;
    while(a[i] == 9) a[i++] = 0;
    a[i]++;
    if(i > n) n++;
    reverse(a + 1, a + n + 1);
    rep(i, 1, 10) Pow[0][i] = 1;
    rep(i, 1, n) rep(j, 1, 10) Pow[i][j] = Pow[i - 1][j] * (100 - 9 * j) % P;
    int idx[11] = {};
    ll as = 0;
    rep(i, 1, n) rep(j, 1, 9) {
        (as += Pow[idx[j]][10] * Pow[n - i][j] % P * (10 * max(a[i] - j, 0) + min(a[i], j)) - a[i] * Pow[n - i][10]) %= P;
        idx[j] += a[i] >= j;
    }
    cout << (as * 111111112 % P + P) % P;
    return 0;
}

CF1548D2 Gregor and the Odd Cows (Hard)

根据 Pick 定理：

$$S=i+\frac b2-1$$

合法三角形的条件即为 $S\in \mathbb Z \land2S\equiv b \pmod 4$​。

对于三角形 $ABC$​， $2S=|\overrightarrow A\times \overrightarrow B+\overrightarrow B\times \overrightarrow C+\overrightarrow C\times \overrightarrow A|$​​​，由于 $S$ 是整数，所以绝对值不会影响 $S$ 的奇偶性，只需要各个顶点的坐标模 $4$ 的结果就可以知道 $2S \bmod 4$​。

一条线段 $AB$​​​ 的 边界数 为线段上整点数减一，$b$​​ 就是三条线段的边界数之和。线段 $AB$​​ 的边界数 $\text{bounds}(A,B)=\gcd(|X_A-X_B|,|Y_A-Y_B|)$​​​​，不太好简单表示。

由于要求 $S$ 为整数，所以 $b$ 为偶数，这是一个很重要的条件，这意味着合法三角形三条边的边界数中至少有一条是偶数，另外两个奇偶性相同，判断 $\text{bounds}(A,B) \bmod 4$ 是 $0$ 还是 $2$ 要容易得多，

$$\text{bounds}(A,B) \equiv 0\pmod 4 \iff X_A\equiv X_B\pmod 4 \land Y_A\equiv Y_B\pmod 4$$

在 $\text{bounds}(A,B) \not\equiv 0\pmod 4$ 的前提下

$$\text{bounds}(A,B) \equiv 2\pmod 4 \iff X_A\equiv X_B\pmod 2 \land Y_A\equiv Y_B\pmod 2$$

判断这两个条件只需要各个顶点的坐标模 $4$ 的结果。

此时做法就清晰起来了，合法三角形按三条边的边界数奇偶性可以分成 EEE 和 EOO 两类，设 $cnt_{A,x,y,z}$ 表示有多少个点 $B$​​ 满足

$$X_B\equiv x\pmod 4 \land Y_B\equiv y\pmod 4 \land \text{bounds}(A,B) \equiv z\pmod 4$$

这个是可以 $O(n^2\log V)$ 预处理的。

考虑分别对两类合法三角形 $ABC$​​​ 计数，先枚举点 $A$​，再枚举

$$\begin{aligned} &X_B\bmod 4,&Y_B\bmod 4,&\text{bounds}(A,B)\bmod 4\\ &X_C\bmod 4,&Y_C\bmod 4,&\text{bounds}(A,C)\bmod 4 \end{aligned}$$

满足

$$\begin{aligned} S &\in \mathbb Z\\ \text{bounds}(A,B)&\equiv\text{bounds}(A,C)\pmod 2\\ X_B&\equiv X_C \pmod 2\\ Y_B&\equiv Y_C\pmod 2\\ S&\equiv \text{bounds}(A,B)+\text{bounds}(A,C)+\text{bounds}(B,C)\pmod 4 \end{aligned}$$

使用 $cnt$ 数组可以 $O(1)$​​ 计算贡献。

这样每个 EEE 三角形会被算 $3$ 遍，每个 EOO 三角形会被算 $1$ 遍。

复杂度 $O(n^2\log V)$。

CF1548E Gregor and the Two Painters

把坏格子填成 $1$，其他填成 $0$，问题就是求矩阵中有多少个“1”的四-连通块。

引理：对于任意两行 $i,j$​​​，“1” 所在列的集合一定是相互包含的。

不妨假设 $a_i \ge a_j$​​，$a_i+b_k \le x \Rightarrow a_j+b_k \le x$​。

同时，此引理也就是这个矩阵的全部性质了，因为任何一个符合引理的矩阵都是可以构造出 $a,b$ 数组的。此题唯一的条件也就是这个引理了，目标很明确。

我们数连通块的思路是这样的：

• 对于一个连通块 $S$​​​​​​，它上到 $L_r$​​​​​​，下到 $R_r$​​​​​​，左到 $L_c$​​​​​，右到 $R_c$​​​​​​。
• 设 $a_{L_r},a_{L_r+1},\cdots,a_{R_r}$​​​ 中第一个取到最小值的位置为 $i$，显然 $(i,L_c),(i,L_c+1),\cdots,(i,R_c)$​ 都为 “1”。
• 我们希望 $S$ 被 $i$ 数到。

再考虑对于 $i$​，有多少个连通块会被它数到，对于第 $i$ 行的一个 “1” 的连续段 $[l,r]$，它所在的连通块会被 $i$​​ 数当且仅当：

• 它向上不能走到一行 $j$​​​ 满足 $a_j \le a_i$​​​​，形式化地，$\min_{k\in [l,r]}a_k+\max_{k\in (j,i]}b_k>x$​​。
• 它向下不能走到一行 $j$​​ 满足 $a_j<a_i$​​​，形式化地，$\min_{k\in [l,r]}a_k+\max_{k\in [i,j)}b_k>x$​​​。

综上，记 $i$ 前面第一个满足 $a_j\le a_i$ 的 $j$ 为 $pre$， $i$ 后面第一个满足 $a_j< a_i$ 的 $j$ 为 $suf$，连续段 $[l,r]$ 造成贡献当且仅当 $\min_{i\in [l,r]}a_i>x-\max_{i\in (pre,suf)}$，不等式右边对于每个 $i$ 是确定的，而且是可以通过单调栈 $O(n)$​ 预处理的东西，对于左边则可以使用数据结构来维护。

下面我们进一步讨论这个数据结构需要干什么：

• 这个数据结构维护所有连续段 $b$ 的最小值。
• 将所有行以 $a_i$​ 为第一关键字，$i$​​ 为第二关键字从大到小排序。每次序列中一个 $0$ 改成 $1$​，会导致新增连续段，也会导致两个连续段合并，修改就是加入元素和删除元素。
• 询问操作就是查询有多少个元素大于 $key$。

对于新增连续段和合并连续段可以用并查集维护，元素则用反向树状数组维护。

复杂度 $O(n\log n)$。

CF1562E Rescue Niwen!

先分析最长上升子序列有什么性质，假设最长上升子序列为

$$s[l_1,r_1],s[l_2,r_2],\cdots,s[l_k,r_k]$$

比较显然的是对于每个 $l$，选择的 $r$ 是一个区间。更强的结论是存在一组最优解满足对于每个 $l$，选择的 $r$ 是一个后缀。

反证法：假设对于一个 $l$，选择的 $r\in[r_1,r_2]$，其中 $r_2<n$，$s[l,r_2]$ 之后的子串为 $s[l',r']$。如果 $s[l,r_2+1]<s[l',r']$，直接在 $s[l,r_2]$ 后插入 $s[l,r_2+1]$，得到一组更优的解。否则 $s[l,r_2]<s[l',r']\le s[l,r_2+1]$，说明

$$\begin{aligned} s[l',l'+r_1-l]&=s[l,r_1]\\ s[l',l'+r_1+1-l]&=s[l,r_1+1]\\ s[l',l'+r_1+2-l]&=s[l,r_1+2]\\ \cdots\\ s[l',l'+r_2-l]&=s[l,r_2] \end{aligned}$$

于是可以用前者们一一替换后者们，得到一组不存在 $l$ 作为左端点的子串的解。

然后就可以 DP 了，设 $f_i$ 表示以 $s[i,n]$ 结尾的最长上升子序列，转移为

$$f_i=\max_{j<i\land s[j,n]<s[i,n]}f_j+n-\text{lcp}(s[i,n],s[j,n])+1$$

可以预处理 $\text{lcp}(s[i,n],s[j,n])\leftarrow \text{lcp}(s[i+1,n],s[j+1,n])$，复杂度 $O(n^2)$。

优化

可以优化到 $O(n\sqrt n)$。

首先是 LCP 怎么处理，通常是使用后缀数组的 height 数组，这里也可以这么处理。

求出后缀数组 $SA$ 和 height 数组，转移为

$$f_{SA_i}=\max_{j<i \land SA_j<SA_i}f_{SA_j}+\max_{k=j+1}^in-height_k+1$$

注意关于 height 的那项是一个后缀 $\max$，考虑单调栈维护，栈内维护两元组 $(v,S)$，每次将 $(n-height_{i+1}+1,\{i\})$ 压栈。假设栈顶元素为 $(v_1,S_1)$，下一个元素为 $(v_2,S_2)$，如果 $v_1\ge v_2$，就把这两个元素合并成 $(v_1,S_1\cup S_2)$。

在插入 $i$ 个元素后，就可以这样计算 $f_{i+1}$：遍历栈内每个三元组 $(v,S)$，用 $\max_{j \in S\land SA_j\le SA_i}+v\rightarrow f_{SA_{i+1}}$。但栈内元素可能很多，不能全部遍历，考虑把 $|S|\le \sqrt n$ 的栈元素的贡献用一个数据结构 $A$ 一起维护，每个 $|S|>\sqrt n$ 的元素用数据结构 $B$ 单独维护，这样就只需要遍历最多 $\sqrt n$ 个 $|S|>\sqrt n$ 的栈元素，即在 $A$ 中查询一次前缀 $\max$，$B$ 中查询 $\sqrt n$ 次前缀 $\max$。

元素合并的时候需要分类维护：

• 当 $|S_1|+|S_2|\le \sqrt n$ 时，相当于把 $S_2$ 的贡献整体加上一个正数，可以在 $A$ 中进行 $|S_2|$ 次增大修改操作，这类操作总共不超过 $n\sqrt n$ 次。
• 当 $|S_1|>\sqrt n\land |S_2|\le \sqrt n$ 时，在 $B$ 中进行 $|S_2|$ 次插入新元素，这类操作总共不超过 $n$ 次。
• 当 $|S_1|,|S_2|>\sqrt n$ 或 $|S_1|,|S_2|\le \sqrt n\land |S_1|+|S_2|>\sqrt n$ 时，用 $|S_1|+|S_2|$ 个元素重构一个 $B$，这类操作总共不超过 $\sqrt n$ 次。

综上，当 $A$ 做到 $O(1)$ 修改，$O(\sqrt n)$ 查询，$B$ 做到 $O(\sqrt n)$ 修改，$O(1)$ 查询时，复杂度为 $O(n\sqrt n)$。

因为修改是增大值，查询是前缀 $\max$，$A$ 和 $B$ 都可以通过分块实现。

CF1562F Tubular Bells

有个长度为 $n$ 的序列 $A$，元素两两不同且值域连续，但你不知道这个序列，每次可以询问两个不同数的 $\text{lcm}$，最多使用 $n+5000$ 次询问求出 $A$。

$n\le 10^5,A_i\le 2\times 10^5$

如果 $\gcd(a,b)=1$，那么 $\text{lcm}(a,b)=ab$，如果求出了 $A$ 序列中最大的质数 $p$，就只需要 $n-1$ 次询问就可以求出 $A$。

先考虑 $p$ 存在的情况，怎么求出 $p$ 和它的位置？询问 $\text{lcm}(A_1,A_2),\text{lcm}(A_2,A_3),\text{lcm}(A_3,A_4),\cdots,\text{lcm}(A_{n-1},n)$，所有质因子中最大的就是 $p$，同时也可以推断出 $p$ 的位置。然后再进行 $n-1$ 次询问就求出了 $A$，询问次数为 $2n-2$，可以处理 $100<n\le7500$。

再分别考虑 $n\le 100$ 和 $n>7500$ 的情况。

$n\le 100$ 可以先两两询问 $\text{lcm}$，再逐个确定。当 $n>3$ 时至少有两个奇数，根据两个奇数的 $\text{lcm}$ 为奇数就可以确定所有数的奇偶性，再取 $\text{lcm}$ 中最大的一个，它一定是 $\max A_i(\max A_i-1)$，结合奇偶性就可以确定最大的 $A_i$，然后删除最大值，重复上述过程，直到 $n=3$ 时，分类讨论即可。

当 $n>7500$ 时需要用不超过 $5000$ 次询问求出 $A$ 序列中最大的质数 $p$，然而比较困难，考虑不找最大的质数，找一个大于 $450$ 的质数 $p'$ 就行了。

考虑随机询问 $\text{lcm}(A_i,A_j)$，如果它是两个大于 $450$ 的质数 $p,q$ 的乘积，那么 $A_i,A_j$ 一定就是 $p,q$，考虑进一步确定 $A_i$，随机一个 $k$，如果 $p\not|\text{lcm}(A_i,A_k)$ 说明 $A_i=p$，如果 $q\not|\text{lcm}(A_j,A_k)$ 说明 $A_i=q$，期望的总随机次数是 $O(\ln^2n)$。

考虑

$$\text{lcm}(p',x)= \begin{cases} x&(x|p')\\ xp'&(x\not|p') \end{cases}$$

如果 $\text{lcm}(p',x)>2\times 10^5$ 就说明 $x\not|p'$，可以确定 $x$ 的值，这样至少可以确定 $n-900$ 个数，并且最大的质数 $p$ 一定被确定了，最后再用 $p$ 和剩下的数询问即可。

CF566C Logistical Questions

给定一棵 $n$ 个点的带权树，每个点住了 $w_i$ 个人，一个人从 $u$ 到 $v$ 的花费为距离的 $1.5$ 次方。

定义 $f(u)$ 表示所有人到点 $u$ 的总花费，求 $f(u)$ 最小的点。

$n \le 2\times 10^5$

首先研究 $f(u)$ 有什么性质，假设花费等于距离的话 $f(u)$ 就是单峰的，因此猜想 $f(u)$ 是单蜂的。

证明：由于 $w_v\text{dis}^{1.5}_v(u)$ 是下凸函数，所以它们加起来也是下凸函数。

回忆实数上的单蜂函数是怎么求最值的：当前确定最优点在 $[l,r]$ 中，在 $\frac {l+r}2$ 处求导来确定最远点在 $\frac {l+r}2$ 左边还是右边，然后将范围减半。

考虑怎么在树上实现这个过程：求出整棵树的重心，通过确定最优解在重心的哪个子树来将范围减半。

怎么确定最优解在哪棵子树？把 $f(u)$ 的定义域扩大，$u$ 可以是一条边上的位置。求出重心向各个方向的导数，由于 $f(u)$ 单峰，所以最多有一个导数小于 $0$，这是最优解的方向。假设最优解的方向沿着边 $(u,v)$，由于 $f(u)$ 的最优点可能在 $(u,v)$ 上，所以 $v$ 不一定比 $u$ 优，应该把经过的所有点取个最小值作为答案。

根 $u$ 向儿子 $v$ 方向的导数为：

$$\frac 32\left(\sum_{i=1}^nw_i\sqrt{\text{dis}(i,u)}-2\sum_{i\in \text{subree}(v)}w_i\sqrt{\text{dis}(i,u)}\right)$$

可以 $O(n)$ 求出 $u$ 向每个儿子的导数，复杂度 $O(n\log n)$。

CF1149C Tree Generator

给定一个长度为 $2(n-1)$ 的合法括号序列，还有 $q$ 次交换操作（保证交换后合法）。

求每次交换后括号序列建出来的树的直径。

$n,q \le 10^5$

容易想到直接维护树的形态，但发现很困难。

考虑括号序列的本质是什么，把 ( 变成 $1$，) 变成 $-1$，再做一遍前缀和，就是树的欧拉序的深度序列，记这个序列为 $dep$。

然后问题变得清晰起来了，因为树上两点间的距离只和 $dep$ 有关。假设欧拉序上第 $a$ 个结点为 $u$，第 $b$ 个结点 $v$，满足 $a \le b$，那么

$$\text{dis}(u,v)=dep_a+dep_b-2\min_{i=a}^bdep_i$$

于是直径为

$$\max_{i\le j\le k}dep_i+dep_k-2dep_j$$

用线段树维护即可，复杂度 $O(n\log n)$。