本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-09-24 13:25:43

A

题目大意

给定 $n$ 个数 $a_i$，一次操作可以选一个数使其 $+1$ 或 $-1$，问使得能够选出三个相等的数的最小操作数。

sol.

首先最终选出的三个数的值一定是三个数初始值的中位数，比较显然，然后就只需要给 $a_i$ 排序，枚举中位数 $a_i$，对 $a_{i+1}-a_{i-1}$ 取 $\min$ 即可。

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

B

题目大意

有一个金字塔，第 $i$ 层有 $i$ 个房间，房间 $(i,j)$ 可以通向房间 $(i+1,j),(i+1,j+1)$，在房间 $(i,j)$ 放置火把可以给所有它能到达的房间增加 $1$ 的亮度值，你现在可以在若干个房间放置火把，给定 $n$，求出使得房间 $(1,1),(2,1) \dots (n,1)$ 的亮度值之和最大、对于 $[1,n]$ 每一层内的房间都有相同亮度值的方案。

sol.

首先第 $i$ 层所有房间的最大亮度值是 $i$，因为只有 $i$ 个房间能够到达 $(i,1)$，然后只需要在每一层的第一个和最后一个房间放置火把即可达到这个上界并满足限制。

C

题目大意

初始你有一个集合 $S$，包含 $1 \dots n$ 的 $n$ 个正整数，每次操作你可以选择一个正整数 $k$，删掉 $S$ 中最小的 $k$ 的倍数，并花费 $k$ 的代价，求出使得 $S$ 变成 $T$ 的最小代价。

sol.

考虑贪心，从 $1$ 到 $n$ 枚举 $k$，把能删的数全删掉。从小到大依次枚举 $k$ 的倍数 $i$，若 $i$ 需要保留，说明不能再用 $k$ 删数，直接枚举下一个 $k$，否则若 $i$ 没有被删过，则将总代价加上 $k$。

时间复杂度为调和级数 $O(n \log n)$。

代码：

#include <bits\/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAXN = 1e6+5;
 
int n;
char s[MAXN];
bool use[MAXN];
ll ans;
 
void solve() {
    for (int i = 1; i <= n; i++) use[i] = 0;
 
    scanf("%d", &n);
    scanf(" %s", s + 1);
 
    ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (s[j] == '1') break;
            if (!use[j]) use[j] = 1, ans += i;
        }
    }
 
    printf("%lld\n", ans);
}
 
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

D

题目大意

$n$ 个史莱姆排成一排，第 $i$ 个血量为 $a_i$，你正在操控第 $k$ 个史莱姆。每次你可以选择和左边或右边相邻的史莱姆合并，合并后血量变为两者之和，若血量 $<0$ 则立即死亡，问最终是否能够与第 $1$ 或第 $n$ 个史莱姆合并并存活。

sol.1

现场思路。

设 $a_i$ 的前缀和数组为 $s_i$，已经合并了 $[l,r]$ 区间内的史莱姆，设当前血量为 $cur$, 则 $cur=s_r-s_{l-1}$。
考虑求出目前一直往左合并能够到达的左端点 $L$，发现需要满足 $cur+s_{l-1}-\max_{i=L}^{l-1}s_{i-1} \le 0$，可以二分求出。若 $L=1$ 那么直接返回 YES，否则考虑贪心，若区间 $[L,l-1]$ 内存在位置 $l'$ 使得 $s_{l-1}-s_{l'-1} \ge 0$，也就是可以让血量增加的位置，则执行 $l \gets l'$，不存在则不动。对右端点同样执行上述过程，若 $[l,r]$ 没有变化，则直接返回 NO。

由于每轮要么区间 $[l,r]$ 至少延长 $1$，要么返回 YES 或 NO ，二分使用 ST 表为 $O(\log n)$, 所以总时间复杂度为 $O(n \log n)$。

sol.2

如果我们现在想向左合并，那么当前血量越大越好，设 $mxR$ 为 $\max_{i=k+1}^r s_i-s_k$，$mxL$ 同理，其中 $r$ 为当左端点在取到 $mxL$ 处时，右端点所能到达的最靠右的位置，$l$ 的定义同理。初始时 $l=r=k, mxL=mxR=0$，每轮先尝试向左延长左端点，若成功则更新 $mxL$，否则向右尝试延长右端点，若成功则更新 $mxR$，否则说明已经没有史莱姆可以合并，返回 NO 即可。

两个指针最多将 $[1,n]$ 扫一遍，时间复杂度 $O(n)$。

代码：

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

typedef long long ll;
const int MAXN = 1e6+5;
const int Mod = 998244353;

int n, k, a[MAXN];
ll sum[MAXN];

void solve() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    sum[k] = 0;
    for (int i = k - 1; i; i--) sum[i] = sum[i + 1] + a[i];
    for (int i = k + 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];

    int l = k, r = k;
    ll mxL = 0, mxR = 0;

    while (l > 1 && r < n) {
        if (mxR + a[k] + sum[l - 1] >= 0) mxL = max(mxL, sum[--l]);
        else if (mxL + a[k] + sum[r + 1] >= 0) mxR = max(mxR, sum[++r]);
        else break;
    }

    puts(l == 1 || r == n ? "YES" : "NO");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

E

题目大意

给定一个质数 $n$ 以及长度为 $n$ 的序列 $b_i$，构造 $n \times n$ 的方阵 $a_{i,j}$，满足:

• $a_{i,i}=b_i$.
• 对于任意 $1 \le r1 < r2 \le n,1 \le c1 < c2 \le n$，$a_{r1,c1}+a_{r2,c2} \not \equiv a_{r1,c2}+a_{r2,c1} \pmod{n}$.

sol.

将第二条限制移项得到 $a_{r1,c2}-a_{r1,c1} \not \equiv a_{r2,c2}-a_{r2,c1}$，由此我们考虑到差分，设 $d_{i,j}=a_{i,j}-a_{i,j-1}$，我们有 $\sum_{i=c1+1}^{c2}d_{r1,i} \not \equiv \sum_{i=c1+1}^{c2} d_{r2,i}$，考虑如下构造 $d_{i,j}$:

$$ \begin{bmatrix} 0 &0 &\cdots &0 \ 1 &1 &\cdots &1 \ 2 &2 &\cdots &2 \ \dots &\dots &\ddots &\dots \ n-1 &n-1 &\cdots &n-1 \end{bmatrix} $$

即 $d_{i,j}=i-1$。

如此一来，设 $x=c2-c1$，那么有 $\sum_{i=c1+1}^{c2}d_{r1,i}=x(r1-1), \sum_{i=c1+1}^{c2} d_{r2,i}=x(r2-1)$。
因为 $r1 \not \equiv r2, 1 \le c1 < c2 \le n$，而以上全部为等价变换，所以限制二被满足当且仅当对于任意 $x \in [1,n-1],x \cdot r1 \not \equiv x \cdot r2$，又因为 $n$ 为质数，所以 $x$ 的逆元一定存在，也就证明了如此构造一定满足限制。

接下来只需要根据 $a_{i,i}=b_i$ 推出 $a$ 每一行的值即可。

F

题目大意

你有一个下标从 $0$ 开始的无限长的字符串 $S$，按照如下方式生成：

• $S$ 初始为 $\texttt{0}$。
• 令 $S'=S$，将 $S'$ 的每一位 0-1 翻转，然后执行 $S \gets S+S'$，重复该操作无限次。

给定 $n,m$，求出 $S_{0,\dots m-1}$ 与 $S_{n, \dots n+m-1}$ 间的汉明距离。

sol.

首先注意到 $S_i= \texttt{1}$ 当且仅当 $\operatorname{popccount} (i) \bmod 2=1$，很好证明，第 $i$ 次操作相当于给下标 $j(0 \le j < 2^i)$ 全部加上 $2^i$，$\operatorname{popccount} (j)$ 奇偶性翻转，恰好对应于 0-1 翻转。赛时降智没想到这个结论，想到了就马上会了。

那么两个位置 $S_i,S_{i+n}$ 不同当且仅当两个下标的 $\operatorname{popccount}$ 奇偶性不同，现在做法已经十分明晰了——数位 dp，设数组 $f_{i,0/1,0/1,0/1}$，表示考虑到第 $i$ 位时对应的下标 $j$ 的个数，满足 $j$ 与 $j+n$ 两个下标 $\operatorname{popccount}$ 异或结果的奇偶性、第 $i-1$ 的进位以及 $j$ 是否大于 $n$，转移比较明显。

代码：

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

typedef long long ll;
const int MAXN = 1e5+5;
const int Mod = 998244353;

ll n, m;
ll f[64][2][2][2];

inline ll dp() {
	scanf("%lld%lld", &n, &m); m--;

	memset(f, 0, sizeof(f));
	f[0][0][0][0] = 1;

	for (int i = 0; i <= 61; i++)
		for (int j = 0; j < 2; j++)\/\/异或和
			for (int k = 0; k < 2; k++)\/\/进位
				for (int l = 0; l < 2; l++) if (f[i][j][k][l]) {\/\/大小关系
					bool gm = m >> i & 1, gn = n >> i & 1;
					for (int p = 0; p < 2; p++)
						f[i + 1][j ^ p ^ (p + gn + k & 1)][gn + p + k >> 1][p > gm || (p == gm && l)] += f[i][j][k][l];
				}

	return f[62][1][0][0];
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		printf("%lld\n", dp());
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-10-01 15:08:43

传送门： F. Almost Sorted

题目大意：

给定长度为 $n$ 的排列 $p_i$ 和常数 $k$，一个长度为 $n$ 的排列 $q_i$ 是合法的当且仅当对于任意 $1 \le i < j \le n$，$p_{q_i} \le p_{q_j}+k$。求合法的排列的逆序对数的最小值。

看到 $k \le 8$，八九不离十就是状压 dp。
考虑从 $1$ 至 $n$ 挨个位置填数，注意到我们若在某个位置上填了 $i$，那么 $[1,i-k)$ 必定在这个位置之前就已经填上了，同理，$(i+k,n]$ 必定还没有填过，现在我们就只需要关心 $[i-k,i) \cup (i,i+k]$ 这 $2k$ 个数的状态，直接设 $f_{i,j,S}$ 表示第 $i$ 位填 $j$，$[j-k,j) \cup (j,j+k]$ 中填上的数的集合为 $S$ 时的最小逆序对数，看起来状态数达到了 $O(n^24^k)$ 级别，但实际上第 $i$ 位上填的数的范围是 $[i-k,i+k]$，所以 $j$ 这一维是 $O(k)$ 的，然后 $S$ 这一维中最大的填过的数和最小的没被填过的数的差不应超过 $k$，搜一下发现只有 $1280=5 \times 2^8$ 种合法的 $S$，所以状态数只有 $O(nk2^k)$ 级别。

然而常数还是太大了，必须考虑继续优化。

注意到 $S$ 这一维中最大的填过的数和最小的没被填过的数的差不超过 $k$，最小的没被填过的数说明小于该数的数全部都填上了，同理最大的填过的数说明大于该数的数全部未填，而现在我们就只需要考虑两数之间的 $O(k)$ 个数了，重新设计 dp 状态 $f_{i,S}$ 表示最小的未被填上的数是 $i$，$(i,i+k]$ 中填上的数的集合为 $S$ 时的最小逆序对数，这时状态数就降到了 $O(n2^k)$ 级别了，转移时选择 $[i,i+k]$ 中一个没被填过的数填上，使用主席树计算其与已经填过的数形成的逆序对数，可在 $O(nk2^k(k+\log n))$ 时间内解决该问题。

代码：

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

typedef long long ll;
const int MAXN = 5005;
const int Mod = 998244353;

int n, K, p[MAXN], id[MAXN];
int f[MAXN][1 << 8];\/\/f[i][S] 表示未填的数中最小的是 i，(i,i+k] 填的情况为 S 时的最小逆序对数

inline void chkMin(int &a, int b) { if (a > b) a = b; }

int tot, rt[MAXN];

struct node {
    int ls, rs, sum;
} T[MAXN * 15];

void upd(int &p, int vp, int l, int r, int gk) {
    T[p = ++tot] = T[vp];
    T[p].sum++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mid >= gk) upd(T[p].ls, T[vp].ls, l, mid, gk);
    else upd(T[p].rs, T[vp].rs, mid + 1, r, gk);
}

int query(int p, int l, int r, int gl, int gr) {
    if (gl > gr) return 0;
    if (l >= gl && r <= gr || !p) return T[p].sum;
    int mid = (l + r) >> 1, ret = 0;
    if (mid >= gl) ret = query(T[p].ls, l, mid, gl, gr);
    if (mid < gr) ret += query(T[p].rs, mid + 1, r, gl, gr);
    return ret;
}

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        id[p[i]] = i;
        upd(rt[i], rt[i - 1], 1, n, p[i]);
    }
    
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;

    for (int i = 1; i <= n; i++)
        for (int S = 0; S < 1 << K; S++) if (f[i][S] < 1e9) {
            int mn = min(K + 1, n + 1 - i);
            for (int j = min(K, n - i); j; j--) if (!(S >> j - 1 & 1)) {
                mn = j;
                int cnt = (id[i] < id[i + j]) + query(rt[id[i + j]], 1, n, i + K + 1, n);
                for (int k = min(K, n - i); k; k--) if (!(S >> k - 1 & 1))
                    cnt += (id[i + k] < id[i + j]);
                chkMin(f[i][S | 1 << j - 1], f[i][S] + cnt);
            }

            int cnt = query(rt[id[i]], 1, n, i + K + 1, n);
            for (int j = min(K, n - i); j; j--) if (!(S >> j - 1 & 1))
                cnt += (id[i + j] < id[i]);
            chkMin(f[i + mn][S >> mn], f[i][S] + cnt);
        }

    printf("%d", f[n + 1][0]);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-10-31 09:41:41

T1 假期计划

首先可以用 bfs 在 $O(nm)$ 时间内算出任意两点间的最短路 $dis_{i,j}$，很明显 $i,j$ 两点间可转车 $k$ 次通达当且仅当 $dis_{i,j} \le k+1$，然后 $O(n^2)$ 枚举景点B,C，那么景点A就是满足 $dis_{1,A} \le k+1$ 且 $dis_{A,B} \le k+1$ 的权值最大的点（不和景点B相同），景点D同理，因为要求A,B,C,D两两不同，所以不能只维护权值最大的点，还要加上次大和次次大点，这个可以 $O(n^2)$ 预处理，总体复杂度 $O(nm+n^2)$。

我的实现多了个排序，复杂度 $O(n^2 \log n)$
代码：

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

typedef long long ll;
const int MAXN = 2505;

inline ll read() {
	ll x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

ll s[MAXN], ans;
int n, m, k;
int dis[MAXN][MAXN];
bool vis[MAXN], igl[MAXN];

vector<int> G[MAXN], cdd[MAXN];
queue<int> Q;

int main() {
\/\/ 	freopen("holiday.in", "r", stdin);
\/\/ 	freopen("holiday.out", "w", stdout);
	n = read(), m = read(), k = read();
	for (int i = 2; i <= n; i++) s[i] = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) vis[j] = 0, dis[i][j] = 1e9; dis[i][i] = 0;
		Q.push(i);
		vis[i] = 1;
		while (!Q.empty()) {
			int top = Q.front();
			Q.pop();
			for (int to : G[top]) {
				if (vis[to]) continue;
				dis[i][to] = dis[i][top] + 1;
				vis[to] = 1;
				Q.push(to);
			}
		}
	}
	
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= n; j++)
			if ((i != j) && dis[1][j] <= k + 1 && dis[i][j] <= k + 1)
				cdd[i].push_back(j);
		sort(cdd[i].begin(), cdd[i].end(), [](int a, int b) { return s[a] > s[b]; });
	}
	
	for (int i = 2; i <= n; i++)
		for (int j = i + 1; j <= n; j++) if (!cdd[i].empty() && !cdd[j].empty() && dis[i][j] <= k + 1) {
			auto p1 = cdd[i].begin(), p2 = cdd[j].begin();
			if (*p1 == j) p1++;
			if (*p2 == i) p2++;
            if (p1 == cdd[i].end() || p2 == cdd[j].end()) continue;
			
			auto pp = p1;
			while (pp != cdd[i].end() && (*pp == *p2 || *pp == j)) pp++;
			if (pp != cdd[i].end()) ans = max(ans, s[i] + s[j] + s[*pp] + s[*p2]);
			pp = p2;
			while (pp != cdd[j].end() && (*pp == *p1 || *pp == i)) pp++;
			if (pp != cdd[j].end()) ans = max(ans, s[i] + s[j] + s[*p1] + s[*pp]);
		}
		
	printf("%lld", ans);
	return 0;
}

T2 策略游戏

简单分类讨论，这里把 $0$ 看作正数，第一个选下标的人叫 Alice，另一个叫 Bob。

首先考虑 $l1=1,r1=n,l2=1,r2=m$ 时的情况。

当 $B$ 中既有正数也有负数时，很明显因为 Bob 要最小化得分，所以无论 Alice 怎么选数， Bob 都会选一个与 Alice 选的数异号的且绝对值最大数，而 Alice 在保证选的数的符号不变的情况下，绝对值必然越小越好，所以答案即为：

$$ \max(-(\min_{ A_{i \ge 0}} |A_i|)(\max_{A_i < 0} |A_i|), -(\min_{A_i < 0}|A_i|)(\max_{A_i \ge 0} |A_i|)) $$

当 $B$ 中只有负数时，若 $A$ 中有负数，那么 Alice 选负数中绝对值最大数肯定最优，此时 Bob 必然要选绝对值最小的数；否则 Alice 只有正数可选，必然选择绝对值最小的，然后 Bob 选择绝对值最大的。答案即为：

$$ \begin{cases} &(\max_{A_i < 0} |A_i|)(\min_{B_i < 0} |B_i|) &\exists i,A_i < 0\ &-(\min_{A_i \ge 0} |A_i|)(\max_{B_i < 0} |B_i|) &\forall i, A_i \ge 0 \end{cases} $$

当 $B$ 中只有正数时与只有负数时同理。

加上区间限制，我们只需要查询区间是否全部为正/负数以及区间正/负数的最大/小绝对值即可，用 ST 表或者线段树均可维护，复杂度 $O(n \log n)$。

代码：

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

typedef long long ll;
const int MAXN = 1e5+5;

inline ll read() {
	ll x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int n, m, q;
int a[MAXN], b[MAXN];

struct info {
	int sgn;
	int pmx, pmn;\/\/正数中最大\/小的绝对值 
	int nmx, nmn;
	info() { sgn = 0, pmn = nmn = 1e9, pmx = nmx = -1; }
};

struct segTree {
	info T[MAXN << 2];
	
	#define ls (p << 1)
	#define rs (p << 1 | 1)
	
	inline info merge(info x, info y) {
		info ret;
		ret.sgn = x.sgn | y.sgn;
		ret.pmx = max(x.pmx, y.pmx);
		ret.pmn = min(x.pmn, y.pmn);
		ret.nmx = max(x.nmx, y.nmx);
		ret.nmn = min(x.nmn, y.nmn);
		return ret;
	}
	
	void build(int p, int l, int r, int *a) {
		if (l == r) {
			if (a[l] >= 0) T[p].sgn = 1, T[p].pmx = T[p].pmn = a[l];
			else T[p].sgn = 2, T[p].nmx = T[p].nmn = -a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid, a);
		build(rs, mid + 1, r, a);
		T[p] = merge(T[ls], T[rs]);
	}
	
	info query(int p, int l, int r, int gl, int gr) {
		if (l >= gl && r <= gr) return T[p];
		int mid = (l + r) >> 1;
		info ret;
		if (mid >= gl) ret = query(ls, l, mid, gl, gr);
		if (mid < gr) ret = merge(ret, query(rs, mid + 1, r, gl, gr));
		return ret;
	}
	
	#undef ls
	#undef rs
} T[2];

int main() {
\/\/	freopen("game.in", "r", stdin);
\/\/	freopen("game.out", "w", stdout);
	n = read(), m = read(), q = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= m; i++) b[i] = read();
	
	T[0].build(1, 1, n, a);
	T[1].build(1, 1, m, b);
	
	while (q--) {
		int l1 = read(), r1 = read(), l2 = read(), r2 = read();
		info A = T[0].query(1, 1, n, l1, r1);
		info B = T[1].query(1, 1, m, l2, r2);

		if (B.sgn == 3) {
            ll ans = -1e18;
            if (A.sgn & 1) ans = max(ans, (ll) -A.pmn * B.nmx);
            if (A.sgn & 2) ans = max(ans, (ll) -A.nmn * B.pmx);
			printf("%lld\n", ans);
		} else if (B.sgn == 1) {
			if (A.sgn & 1) {
				printf("%lld\n", (ll) A.pmx * B.pmn);
			} else {
				printf("%lld\n", (ll) -A.nmn * B.pmx);
			}
		} else {
			if (A.sgn & 2) {
				printf("%lld\n", (ll) A.nmx * B.nmn);
			} else {
				printf("%lld\n", (ll) -A.pmn * B.nmx);
			}
		}
	}
	return 0;
}

T3 星战

一直在想根号分治。

首先我们发现可以实现反击其实是可以实现连续穿梭的必要条件，因为只要每个点都有出边，那么一定可以无限走下去（实际上就是个内向基环树森林）。考虑维护一个可重无序集合 $S$，若一个虫洞可用，那么它的出发节点就将在 $S$ 中多出现一次，那么满足限制当且仅当 $S = \{1,2,3,\dots,n\}$。每次操作就相当于给定任意一个集合 $T$，将 $T$ 加入 $S$ 或者从 $S$ 中删去一个 $T$，这种东西看起来就很不可以低于 $O(n^2)$ 的时间精准维护（至少我没想到），于是可以考虑哈希，给每个节点规定一个随机权值，直接维护当前 $S$ 中所有点的权值和即可，维护非常简单。

我代码的哈希方式是维护编号平方和，欢迎来叉XD。
代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 5e5+5;
const int Mod = 998244353;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int n, m, q;
ll stdHsh, curHsh, Hsh[MAXN][2], cursiz, siz[MAXN][2];

int main() {
    \/\/ freopen("galaxy.in", "r", stdin);
    \/\/ freopen("galaxy.out", "w", stdout);
    n = read(), cursiz = m = read();
    stdHsh = (ll) n * (n + 1) * (2 * n + 1) \/ 6;
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        curHsh += (ll) u * u;
        Hsh[v][1] += (ll) u * u;
        siz[v][1]++;
    }

    q = read();
    while (q--) {
        int op = read(), u = read(), v;
        if (op == 1) {
            v = read();

            cursiz--;
            siz[v][1]--, siz[v][0]++;

            curHsh -= (ll) u * u;
            Hsh[v][1] -= (ll) u * u;
            Hsh[v][0] += (ll) u * u;
        } else if (op == 2) {
            curHsh -= Hsh[u][1];
            Hsh[u][0] += Hsh[u][1];
            Hsh[u][1] = 0;

            cursiz -= siz[u][1];
            siz[u][0] += siz[u][1];
            siz[u][1] = 0;
        } else if (op == 3) {
            v = read();

            cursiz++;
            siz[v][0]--, siz[v][1]++;

            curHsh += (ll) u * u;
            Hsh[v][0] -= (ll) u * u;
            Hsh[v][1] += (ll) u * u;
        } else {
            curHsh += Hsh[u][0];
            Hsh[u][1] += Hsh[u][0];
            Hsh[u][0] = 0;

            cursiz += siz[u][0];
            siz[u][1] += siz[u][0];
            siz[u][0] = 0;
        }
        puts(cursiz == n && curHsh == stdHsh ? "YES" : "NO");
    }
    return 0;
}

T4 数据传输

这比去年T4简单到不知道哪里去了。

首先 $k=1$ 时就是查询路径权值和，不再赘述。

当 $k=2$ 时，可以发现此时我们一定是沿着从 $u$ 到 $v$ 的路径走的，不可能走到路径之外的节点，如图：

很明显红色路径花了两步，能走到的最远的点也能从出发点一步走到，所以不可能走到路径之外。
将从 $u$ 到 $v$ 的路径抽出来，设 $f_i$ 表示到达第 $i$ 个点所需的最小代价，转移方程非常好写。

当 $k=3$ 时，这时我们发现它是可能走到路径外的：

蓝色路径花两步能走到的最远节点最短也需要两步，而红色路径不能，所以可能走到距离路径为 $1$ 的节点。
将从 $u$ 到 $v$ 的路径以及距离该路径为 $1$ 的节点抽出来，我们发现 $k=2$ 时的 dp 状态不适用，不过可以从中得到启发，重新设 $f_{i,0/1/2}$ 表示现在考虑到了路径上第 $i$ 个点，目前所在的点到第 $i$ 个点的距离为 $0/1/2$，设 $mn_{i}$ 为第 $i$ 个节点的相邻节点中的最小权值，有转移方程：

$$ \begin{cases} f_{i,0} = \min(f_{i-1,0},f_{i-1,1},f_{i-1,2})+val_{i}\ f_{i,1} = \min(f_{i-1,0},f_{i-1,1}+mn_i)\ f_{i,2} = f_{i-1,1} \end{cases} $$

现在单次询问可以做到 $O(n)$，但还不够，注意到 $f_i$ 可以看成是 $f_{i-1}$ 某种意义下的线性组合，与矩阵乘法的形式相似，考虑新定义矩阵乘法：

$$ (AB){i,j} = \min_k(A{i,k}+B_{k,j}) $$

一个非常美妙的性质是，新定义下的矩阵乘法也是满足结合律的：

$$ \begin{aligned} \left [(AB)C \right ]{i,j} &= \min_k((AB){i,k}+C_{k,j})\ &= \min_k(\min_p(A_{i,p}+B_{p,k})+C_{k,j})\ &= \min_k(\min_p(A_{i,p} +B_{p,k}+C_{k,j}))\ &= \min_{k,p}(A_{i,p} +B_{p,k}+C_{k,j})\ &= \min_p(\min_k(A_{i,p} +B_{p,k}+C_{k,j}))\ &= \min_p(A_{i,p}+\min_k(B_{p,k}+C_{k,j}))\ &= \min_p(A_{i,p}+(BC){p,j})\ &= \left [A(BC) \right ]{i,j} \end{aligned} $$

点 $i$ 的转移矩阵即为：

$$ \begin{bmatrix} val_i &0 &+\infty \ val_i &mn_i &0 \ val_i &+\infty &+\infty \end{bmatrix} $$

询问就是求一个路径积，倍增，树剖，点分治，LCT，全局平衡二叉树，TopTree，随便拿个东西就能维护。
代码（倍增）：

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

typedef long long ll;
const int MAXN = 2e5+5;
const ll INF = 1e18;

inline ll read() {
	ll x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int n, q, K, val[MAXN];
int dep[MAXN], f[MAXN][18];

vector<int> T[MAXN];

struct Matrix {
	ll ele[3][3];
	ll &operator ()(int x, int y) { return ele[x][y]; }
	Matrix () { memset(ele, 0x3f, sizeof(ele)); }
} F[MAXN], up[MAXN][18], dwn[MAXN][18];

Matrix operator *(Matrix x, Matrix y) {
	Matrix ret;
	for (int i = 0; i < K; i++)
		for (int j = 0; j < K; j++)
			for (int k = 0; k < K; k++)
				ret(i, j) = min(ret(i, j), x(i, k) + y(k, j));
	return ret;
}

void dfs1(int x, int fa) {
	dep[x] = dep[fa] + 1;
	f[x][0] = fa;
	up[x][0] = F[fa];
	dwn[x][0] = F[x];
	for (int i = 1; i < 18; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
		up[x][i] = up[x][i - 1] * up[f[x][i - 1]][i - 1];
		dwn[x][i] = dwn[f[x][i - 1]][i - 1] * dwn[x][i - 1];
	}
	
	for (int son : T[x]) {
		if (son == fa) continue;
		dfs1(son, x);
	}
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	
	int h = dep[u] - dep[v];
	for (int i = 0; i < 18; i++)
		if (h >> i & 1)
			u = f[u][i];
	if (u == v) return u;
	
	for (int i = 17; ~i; i--)
		if (f[u][i] ^ f[v][i])
			u = f[u][i], v = f[v][i];
	
	return f[u][0];
}

int main() {
\/\/ 	freopen("transmit.in", "r", stdin);
\/\/ 	freopen("transmit.out", "w", stdout);
	n = read(), q = read(), K = read();
	for (int i = 1; i <= n; i++) F[i](0, 0) = F[i](1, 0) = F[i](2, 0) = val[i] = read(), F[i](0, 1) = F[i](1, 2) = 0;
		
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		T[u].push_back(v);
		T[v].push_back(u);
	}
	
	if (K == 3)
	for (int i = 1; i <= n; i++)
		for (int to : T[i])
			F[i](1, 1) = min(F[i](1, 1), (ll) val[to]);
	
	dfs1(1, 0);
	
	while (q--) {
		int u = read(), v = read();
		Matrix tmp, tmp1;
		tmp(0, 0) = val[u];
		for (int i = 0; i < K; i++) tmp1(i, i) = 0;
		
		int lca = LCA(u, v), h = dep[u] - dep[lca];
		\/\/printf("-%d %d %d-\n", u, v, lca);
		for (int i = 0; i < 18; i++)
			if (h >> i & 1)
				tmp = tmp * up[u][i], u = f[u][i];
		\/\/tmp.print();
		
		h = dep[v] - dep[lca];
		for (int i = 0; i < 18; i++)
			if (h >> i & 1)
				tmp1 = dwn[v][i] * tmp1, v = f[v][i];
				
		printf("%lld\n", (tmp * tmp1)(0, 0));
	}
	return 0;
}