OI笔记 | 2023.1-2 做题记录（二）
- Sports Festival
- Fox And Names
- ρars/ey
- [NOI2018] 归程
- [NOIP2013 提高组] 货车运输
- [NOIP2017 提高组] 逛公园
- [SCOI2015]情报传递
- [国家集训队] 小 Z 的袜子
- Destiny
Sports Festival
Takahashi举办了一场运动会，这场运动会有 $M$ 个项目，有 $N$ 个人来参加。
给你一个 $N\times M$ 的二维数组 $a$，其中 $a[i][j]$ 表示第 $i$ 个人，她心目中排名第 $j$ 的项目是哪个。
这 $M$ 个项目不一定全都要进行，可以选其中一些项目进行，剩下的都鸽掉，当然肯定不能鸽掉所有 $M$ 个项目。
每个人会在所有开展的项目当中，选择她心目中排名最高的那个项目参加。
因此，如果开展全部项目的话，可能某个项目的人数会爆多无比，所以Takahashi决定，只开展其中的一部分项目，使得参加人数最多的那个项目，参加人数尽量少。
请输出这个值。
题解
考虑全选时，参加人数最多的项目为 $del$，它的参加人数为 $x$。
显然一旦我们开展这个任务，答案一定为 $x$。不开展其他项目对这件事没有影响，不会减少答案。
所以我们只能尝试不开展这个项目 $del$，这样之后答案不大于 $x$。
统计答案，直到删光，时间复杂度 $O(nm)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 305, INF = (1 << 30);
int a[MAX_N][MAX_N], now[MAX_N], cnt[MAX_N], vis[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read(), ans = INF;
for(int i = 1; i <= n; i++) {
now[i] = 1;
for(int j = 1; j <= m; j++)
a[i][j] = read();
}
while(1) {
int del = 0;
for(int i = 1; i <= m; i++)
cnt[i] = 0;
for(int i = 1; i <= n; i++) {
while(now[i] <= m && vis[a[i][now[i]]]) now[i]++;
if(now[i] > m) continue;
int x = a[i][now[i]];
cnt[x]++;
if(cnt[x] > cnt[del]) del = x;
}
if(!del) break;
vis[del] = 1;
ans = min(ans, cnt[del]);
}
write(ans);
return 0;
}
Fox And Names
有一些按照某个被改变的字典序排序后的字符串，请求出其字典序。
（存在多组解，请输出任意一组）
否则输出 Impossible（请注意大小写）
题解
拓扑排序。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
char s[105][105];
int in[27];
bool G[27][27];
vector<int> ans;
inline ll read() {...}
inline void write(ll x) {...}
bool topo() {
queue<int> s;
for(int i = 0; i < 26; i++)
if(!in[i]) s.push(i);
while(!s.empty()) {
int u = s.front();
s.pop();
ans.pb(u);
for(int v = 0; v < 26; v++) {
if(!G[u][v]) continue;
if(--in[v] == 0) s.push(v);
}
}
return (ans.size() == 26);
}
int main() {
int n = read();
for(int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
for(int i = 1; i < n; i++) {
int len1 = strlen(s[i] + 1), len2 = strlen(s[i + 1] + 1), k = 1;
while(k < min(len1, len2) && s[i][k] == s[i + 1][k])
k++;
int u = s[i][k] - 'a', v = s[i + 1][k] - 'a';
if(u == v && len1 <= len2) continue;
if(!G[u][v]) {
G[u][v] = 1;
in[v]++;
}
}
if(topo()) {
for(int u : ans)
putchar(u + 'a');
putchar('\n');
}
else puts("Impossible");
return 0;
}
ρars/ey
给定一颗有 $n$ 个节点的有根树，其中根节点是 $1$。你可以进行若干次以下操作:
- 选择一个节点，删去其子树内除其以外的点。
此操作的代价为 $f_i$，其中 $i$ 是你选择的节点子树大小。
你希望删掉除了 $1$ 以外的所有点，请问代价的最小值是多少？
题解
树形背包，$O(n^2)$ 的简单写法。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const int MAX_N = 5e3 + 10;
const ll INF = (1ll << 60);
int f[MAX_N], siz[MAX_N], n;
ll dp[MAX_N][MAX_N];
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void dfs(int u, int fa) {
siz[u] = 1;
for(int i = 1; i <= n; i++)
dp[u][i] = INF;
for(int v : G[u]) {
if(v == fa) continue;
dfs(v, u);
for(int i = siz[u] - 1; i >= 0; i--)
for(int j = siz[v] - 1; j >= 0; j--)
dp[u][i + j] = min(dp[u][i + j], dp[u][i] + dp[v][j]);
siz[u] += siz[v];
}
for(int i = 0; i < siz[u] - 1; i++)
dp[u][siz[u] - 1] = min(dp[u][siz[u] - 1], dp[u][i] + f[siz[u] - i]);
}
int main() {
n = read();
for(int i = 1; i <= n - 1; i++)
f[i + 1] = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read();
G[u].pb(v), G[v].pb(u);
}
dfs(1, 0);
write(dp[1][n - 1]);
return 0;
}
[NOI2018] 归程
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图（节点的编号从 $1$ 至 $n$）。我们依次用 $l,a$ 描述一条边的长度、海拔。
作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。
Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。
每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着：
- 车会在新的出发点被准备好。
- Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。
本题的部分测试点强制在线。
-
$T\leq 3$
-
$n\leq 2\times 10^5$，$m\leq 4\times 10^5$，$Q\leq 4\times 10^5$，$K\in\left{0,1\right}$，$1\leq S\leq 10^9$。
-
对于所有边：$l\leq 10^4$，$a\leq 10^9$。
-
任意两点之间都直接或间接通过边相连。
题解
先考虑离线的部分分。可以先把 $1$ 号点到所有点的最短路预处理，然后把所有询问的水位线从大到小排序。对于每个询问，把海拔大于当前水位线的边加上，然后用并查集维护当前连通块距离 $1$ 号节点最近的距离即可。
对于上面的排序再加边的过程，我们可以用 Kruskal 重构树使其在线。这个就比较套路。
如何构建 Kruskal 重构树呢？考虑排序后的每一次加边过程。假设我们现在要加上 $(u,v)$ 这条边：
-
如果 $u$ 和 $v$ 连通，忽略这次操作。
-
否则，找到它们在重构树上的的祖先 $f_u$ 和 $f_v$，并在重构树上新建一个节点 $k$，连两条边 $(k,f_u),(k,f_v)$。节点 $k$ 带有的信息是原图中的 $(u,v)$ 边。
这样出来的重构树有非常好的性质。
-
它是一个二叉堆。
-
$\operatorname{lca}(u,v)$ 对应原图中 $u$ 到 $v$ 的路径上的瓶颈。
本题主要用到第一个性质，我们会构造出一个小根堆，即 $u$ 子树内的所有节点 $w$ 所代表的边的海拔都有 $p_w\ge p_u$。
这样这题的思路就有了。首先预处理 Kruskal 重构树并用 dijkstra 求出 $1$ 号点到所有点的最短路。然后每个询问只要在 Kruskal 重构树上倍增找到第一个海拔大于询问水位，且父亲的海拔小于或等于当前水位的节点。然后在子树的叶子节点中找到在原图中距离 $1$ 号节点最近的即可。
用链式前向星存图的代码见此处。
用 vector 存图的代码（奇怪的习惯，虽然慢了两秒但是不会被卡常）：
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 4e5 + 10, MAX_LOG = 20, INF = (1 << 30);
inline ll read() {
ll ret = 0, w = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') w = -1; c = getchar();}
while(isdigit(c)) {ret = (ret << 1) + (ret << 3) + (c ^ 48); c = getchar();}
return ret * w;
}
inline void write(ll x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
}
int T, n, m, cnt, tot;
int fa[MAX_N][MAX_LOG], dis[MAX_N], dp[MAX_N], h[MAX_N], dep[MAX_N];
bool vis[MAX_N];
struct edge {
int u, v, l, a;
edge(int _u = 0, int _v = 0, int _l = 0, int _a = 0) :
u(_u), v(_v), l(_l), a(_a) {}
bool operator < (const edge &t) const {return a > t.a;}
} E[MAX_N];
int f[MAX_N];
int find(int x) {
if(x == f[x]) return x;
return f[x] = find(f[x]);
}
vector<edge> edges;
vector<int> G[MAX_N], tree[MAX_N];
void AddEdge(int u, int v, int l, int a) {
edges.pb(edge(u, v, l, a));
G[u].pb((int)edges.size() - 1);
}
void dijkstra() {
for(int i = 1; i <= n; i++)
dis[i] = INF, vis[i] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push(make_pair(0, 1));
dis[1] = 0;
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i : G[u]) {
int v = edges[i].v, w = edges[i].l;
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push(make_pair(dis[v], v));
}
}
}
}
void dfs(int u, int pre) {
fa[u][0] = pre;
dp[u] = tree[u].empty() ? dis[u] : INF;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v : tree[u]) {
dep[v] = dep[u] + 1;
dfs(v, u);
dp[u] = min(dp[u], dp[v]);
}
}
void kruskal() {
sort(E + 1, E + m + 1);
for(int i = 1; i <= (n << 1); i++)
f[i] = i, tree[i].clear();
cnt = n, tot = 0;
for(int i = 1; i <= m; i++) {
int x = E[i].u, y = E[i].v, a = E[i].a;
int fx = find(x), fy = find(y);
if(fx == fy) continue;
cnt++;
tree[cnt].pb(fx);
tree[cnt].pb(fy);
h[cnt] = a;
f[fx] = f[fy] = cnt;
if(++tot == n - 1) break;
}
}
int main() {
T = read();
while(T--) {
n = read(), m = read();
edges.clear();
for(int i = 1; i <= n; i++)
G[i].clear();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), l = read(), a = read();
E[i] = edge(u, v, l, a);
AddEdge(u, v, l, a);
AddEdge(v, u, l, a);
}
dijkstra();
kruskal();
dep[cnt] = 1;
dfs(cnt, 0);
int q = read(), k = read(), s = read(), lastans = 0;
while(q--) {
int v = read(), p = read();
v = (v + k * lastans - 1) % n + 1;
p = (p + k * lastans) % (s + 1);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(h[fa[v][i]] > p && dep[v] > (1 << i)) v = fa[v][i];
write(lastans = dp[v]);
putchar('\n');
}
}
return 0;
}
[NOIP2013 提高组] 货车运输
A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 $q$ 辆货车在运输货物，一次运输有起点和终点。司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
$1 \le n < 10^4$，$1 \le m < 5\times 10^4$，$1 \le q< 3\times 10^4 $，$0 \le z \le 10^5$。
题解
询问 $x$ 到 $y$ 的路径中最小的边权最大是多少。
其实就是最大生成树的路径最小值。可以用 Kruskal 重构树解决，重构树的 LCA 的权值就是最小的边权。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const int MAX_M = 5e4 + 10, MAX_LOG = 16;
inline ll read() {...}
inline void write(ll x) {...}
int n, m;
struct edge {
int u, v, w;
bool operator < (const edge &t) const {return w > t.w;}
} E[MAX_M];
vector<int> G[MAX_M];
int fa[MAX_M], dep[MAX_M], val[MAX_M];
bool vis[MAX_M];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int f[MAX_M][MAX_LOG];
void dfs(int u, int pre) {
f[u][0] = pre;
dep[u] = dep[pre] + 1;
vis[u] = 1;
for(int i = 1; i < MAX_LOG; i++)
f[u][i] = f[f[u][i - 1]][i - 1];
for(int v : G[u])
dfs(v, u);
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(f[u][i] && dep[f[u][i]] >= dep[v]) u = f[u][i];
if(u == v) return u;
for(int i = MAX_LOG - 1; i >= 0; i--)
if(f[u][i] && f[v][i] && f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++)
E[i].u = read(), E[i].v = read(), E[i].w = read();
sort(E + 1, E + m + 1);
int cnt = n;
for(int i = 1; i < (n << 1); i++)
fa[i] = i;
for(int i = 1; i <= m; i++) {
int u = E[i].u, v = E[i].v, w = E[i].w;
int fu = find(u), fv = find(v);
if(fu != fv) {
cnt++;
val[cnt] = w;
G[cnt].pb(fu);
G[cnt].pb(fv);
fa[fu] = fa[fv] = cnt;
}
}
for(int i = 1; i <= cnt; i++)
if(!vis[i]) dfs(find(i), 0);
int q = read();
while(q--) {
int x = read(), y = read();
if(find(x) != find(y)) write(-1);
else write(val[lca(x, y)]);
putchar('\n');
}
return 0;
}
[NOIP2017 提高组] 逛公园
策策同学特别喜欢逛公园。公园可以看成一张 $N$ 个点 $M$ 条边构成的有向图，且没有 自环和重边。其中 $1$ 号点是公园的入口，$N$ 号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 $1$ 号点进去，从 $N$ 号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 $1$ 号点 到 $N$ 号点的最短路长为 $d$，那么策策只会喜欢长度不超过 $d + K$ 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对 $P$ 取模。
如果有无穷多条合法的路线，请输出 $-1$。
$1 \le P \le 10^9$，$1 \le a_i,b_i \le N$，$0 \le c_i \le 1000$，$0\le k\le50$。
题解
我们看到 $k$ 的范围很小，所以可以暴力枚举。设 $dp_{u,k}$ 为 $1$ 到 $u$，最短路恰好为 $dis_u + k$ 时的路径条数。那么答案就是 $\sum\limits_{w=0}^k dp_{n,w}$。
这个路径条数我们可以在反图上记忆化搜索。反图可以使合法状态数减少一些。
然后我们考虑一条边 $(u,v,w)$，怎么从 $dp_{v,x}$ 转移到 $dp_{u,k}$？用边权找到约束关系：$dis_{v} + x + w = dis_u + k$。所以转移方程为：
\[dp_{u,k} = \sum\limits_{(u,v,w)\in E} dp_{v,dis_u+k-dis_v-w}\]然后观察样例，原图中有零环的情况下最短路当然有无数多条。这个只要在记搜的时候记录一下会不会成环即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e5 + 10, INF = (1 << 30);
inline ll read() {...}
inline void write(ll x) {...}
int T, n, m, k, p, cnt1, cnt2;
int fir1[MAX_N], fir2[MAX_N], dis[MAX_N], dp[MAX_N][60];
bool vis[MAX_N], instack[MAX_N][60];
struct node {int v, w, nxt;} e1[MAX_N], e2[MAX_N];
void AddEdge(int u, int v, int w, int &cnt, int *fir, node *e) {
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].nxt = fir[u];
fir[u] = cnt;
}
void clear() {
cnt1 = cnt2 = 0;
for(int i = 1; i <= m; i++)
fir1[i] = fir2[i] = 0;
for(int i = 1; i <= n; i++) {
dis[i] = INF, vis[i] = 0;
for(int k = 0; k <= 50; k++)
dp[i][k] = instack[i][k] = 0;
}
}
void dijkstra() {
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push(make_pair(0, 1));
dis[1] = 0;
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = fir1[u]; i; i = e1[i].nxt) {
int v = e1[i].v, w = e1[i].w;
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push(make_pair(dis[v], v));
}
}
}
}
int dfs(int u, int k) {
if(k < 0) return 0;
if(instack[u][k]) return -1;
if(dp[u][k]) return dp[u][k];
instack[u][k] = 1;
int ret = 0;
for(int i = fir2[u]; i; i = e2[i].nxt) {
int v = e2[i].v, w = e2[i].w;
int tmp = dfs(v, dis[u] - dis[v] + k - w);
if(tmp == -1) return -1;
(ret += tmp) %= p;
}
instack[u][k] = 0;
return dp[u][k] = ret;
}
int work() {
int ans = 0;
if(dfs(1, 0) == -1) return -1;
dp[1][0] = 1;
for(int i = 0; i <= k; i++) {
int tmp = dfs(n, i);
if(tmp == -1) return -1;
(ans += tmp) %= p;
}
return ans;
}
int main() {
T = read();
while(T--) {
n = read(), m = read(), k = read(), p = read();
clear();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w, cnt1, fir1, e1);
AddEdge(v, u, w, cnt2, fir2, e2);
}
dijkstra();
write(work());
putchar('\n');
}
return 0;
}
[SCOI2015]情报传递
奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名 (可能没有) 下线，除 $1$ 名大头目外其余 $n-1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上、下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务：
- 搜集情报：指派 $T$ 号情报员搜集情报；
- 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员。
情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为 $0$；一旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加 $1$ 点危险值 (开始搜集情报的当天危险值仍为 $0$，第 $2$ 天危险值为 $1$，第 $3$ 天危险值为 $2$，以此类推)。传递情报并不会使情报员的危险值增加。
为了保证传递情报的过程相对安全，每条情报都有一个风险控制值 $C$。奈特公司认为，参与传递这条情报的所有情报员中，危险值大于 $C$ 的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。
题解
对于这个树上问题，先用 dfs 序 或 重链剖分 转化为序列问题。
所以需要支持：
-
在序列的位置 $u$ 打时间戳 $t_u$。
-
查询 $t$ 时刻序列的区间 $[l,r]$ 内有多少个位置 $u$ 满足 $t-t_u> c$。
Solution 1
可以用主席树来维护。把位置的权值设为时间戳的值，查询即查询区间内权值小于 $t-c$ 的个数。
Solution 2
考虑离线。对于查询 $t$ 时刻的情况，它只被 $t_u < t - c$ 的位置影响，所以我们可以在 $t=t_u - c - 1$ 的时刻算出 $t$ 时刻的答案。
此外，我们可以考虑差分。打时间戳的操作可以改为对 $u$ 的子树区间内 +1；询问的答案可以用差分得出。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10, MAX_LOG = 19;
int n, q, dfncnt, rt;
int ans[MAX_N], opt[MAX_N], X[MAX_N], Y[MAX_N], C, T;
int fa[MAX_N][MAX_LOG], siz[MAX_N], dep[MAX_N], dfn[MAX_N];
vector<int> G[MAX_N], opter[MAX_N];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
struct TreeArray {
int t[MAX_N];
TreeArray() {memset(t, 0, sizeof(t));}
inline int lowbit(int i) {return i & -i;}
inline void add(int i, int x) {
for(; i <= n; i += lowbit(i))
t[i] += x;
}
inline int query(int i) {
int ret = 0;
for(; i; i -= lowbit(i))
ret += t[i];
return ret;
}
} tree;
void dfs(int u) {
siz[u] = 1;
dep[u] = dep[fa[u][0]] + 1;
dfn[u] = ++dfncnt;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v : G[u]) {
dfs(v);
siz[u] += siz[v];
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[u][i] && dep[fa[u][i]] >= dep[v]) u = fa[u][i];
if(u == v) return u;
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[u][i] && fa[v][i] && fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
int dis(int u, int v) {
int p = lca(u, v);
return dep[u] + dep[v] - dep[p] * 2 + 1;
}
int main() {
n = read();
for(int i = 1; i <= n; i++)
fa[i][0] = read(), G[fa[i][0]].pb(i), rt = (fa[i][0] ? rt : i);
dfs(rt);
q = read();
for(int i = 1; i <= q; i++) {
opt[i] = read();
if(opt[i] == 1) {
X[i] = read(), Y[i] = read(), C = read();
if(i - C - 1 >= 0) opter[i - C - 1].pb(i);
}
else X[i] = read();
}
for(int i = 1; i <= q; i++) {
int x = X[i], y = Y[i];
if(opt[i] == 2) tree.add(dfn[x], 1), tree.add(dfn[x] + siz[x], -1);
for(int u : opter[i]) {
int p = lca(X[u], Y[u]);
ans[u] = tree.query(dfn[X[u]]) + tree.query(dfn[Y[u]]) - tree.query(dfn[p]) - tree.query(dfn[fa[p][0]]);
}
if(opt[i] == 1) {
write(dis(x, y)), putchar(' ');
write(ans[i]), putchar('\n');
}
}
return 0;
}
[国家集训队] 小 Z 的袜子
有一个长度为 $n$ 的序列 ${c_i}$。现在给出 $m$ 个询问，每次给出两个数 $l,r$，从编号在 $l$ 到 $r$ 之间的数中随机选出两个不同的数，求两个数相等的概率。
题解
莫队模板题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAX_N = 5e4 + 10;
int n, m, siz, tot;
int c[MAX_N], cnt[MAX_N];
pll ans[MAX_N];
inline int belong(int i) {return (i - 1) / siz + 1;}
struct query {
int l, r, id;
inline bool operator < (const query &t) const {
if(belong(l) == belong(t.l)) return l < t.l;
return belong(l) & 1 ? r < t.r : r > t.r;
}
} q[MAX_N];
inline void add(int col) {
tot += cnt[col];
cnt[col]++;
}
inline void del(int col) {
cnt[col]--;
tot -= cnt[col];
}
inline ll gcd(ll x, ll y) {return y ? gcd(y, x % y) : x;}
pll reduce(pll x) {
ll g = gcd(x.first, x.second);
return make_pair(x.first / g, x.second / g);
}
inline ll read() {...}
inline void write(ll x) {...}
int main() {
n = read(), m = read();
siz = sqrt(n);
for(int i = 1; i <= n; i++)
c[i] = read();
for(int i = 1; i <= m; i++)
q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(q + 1, q + m + 1);
for(int i = 1, l = 1, r = 0; i <= m; i++) {
if(q[i].l == q[i].r) {
ans[q[i].id] = make_pair(0, 1);
continue;
}
while(l > q[i].l) add(c[--l]);
while(r < q[i].r) add(c[++r]);
while(l < q[i].l) del(c[l++]);
while(r > q[i].r) del(c[r--]);
ans[q[i].id] = reduce(make_pair(tot, 1ll * (r - l + 1) * (r - l) / 2));
if(!ans[q[i].id].first) ans[i].second = 1;
}
for(int i = 1; i <= m; i++) {
write(ans[i].first), putchar('/');
write(ans[i].second), putchar('\n');
}
return 0;
}
Destiny
给定 $n$ 个元素，$m$ 次询问。
每次给出三个参数 $l,r,k$，询问区间 $[l,r]$ 内是否存在出现次数严格大于 $\frac{r-l+1}{k}$ 的数。如果存在就输出最小的那个 $ans$，否则输出 $-1$.
$2\le k\le 5$
题解
考虑随机化。在区间 $[l,r]$ 中随机取值，有 $\frac{1}{k}$ 的概率取到答案， $1-\frac{1}{k}$ 的概率不是答案。由于 $k\le 5$，可知 $1-\frac{1}{k}\le \frac{4}{5}$，所以投答案 $T$ 次取不到答案的概率为 $(\frac{4}{5})^T$。取 $T=100$，则这个概率约为 $2\times 10^{-10}$。
由于可以离线，我们用莫队来求区间内每个数的出现次数。
时间复杂度 $O(100n\sqrt n)。$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 3e5 + 10;
int n, m, siz;
int a[MAX_N], cnt[MAX_N], ans[MAX_N];
mt19937 rng(random_device{}());
inline int belong(int i) {return (i - 1) / siz + 1;}
struct query {
int l, r, k, id;
bool operator < (const query &t) const {
if(belong(l) != belong(t.l)) return l < t.l;
return belong(l) & 1 ? r < t.r : r > t.r;
}
} q[MAX_N];
int main() {
n = read(), m = read();
siz = sqrt(n);
for(int i = 1; i <= n; i++)
a[i] = read();
for(int i = 1; i <= m; i++)
q[i].l = read(), q[i].r = read(), q[i].k = read(), q[i].id = i;
sort(q + 1, q + m + 1);
for(int i = 1, l = 1, r = 0; i <= m; i++) {
while(l > q[i].l) cnt[a[--l]]++;
while(r < q[i].r) cnt[a[++r]]++;
while(l < q[i].l) cnt[a[l++]]--;
while(r > q[i].r) cnt[a[r--]]--;
int res = -1;
for(int j = 1; j <= 100; j++) {
int x = l + rng() % (r - l + 1);
if(cnt[a[x]] * q[i].k > r - l + 1)
res = (res == -1 || res > a[x]) ? a[x] : res;
}
ans[q[i].id] = res;
}
for(int i = 1; i <= m; i++)
write(ans[i]), putchar('\n');
return 0;
}
♥