10月每日总结

日々私たちが過ごしている日常は、実は、奇跡の連続なのかもしれない。

我们所经历的每个平凡的日常，也许就是连续发生的奇迹。

——《日常》

10.1

有一款游戏，它有 $n$ 个关卡，第 $n$ 个关卡的难度是 $p_i$ ，已知 $n$ 是 $1,\dots,n$ 的一个排列。玩家不必按照 $1$ 到 $n$ 的顺序通过这 $n$ 个关卡，他们可以自己选择闯关的顺序。对于每一个关卡，游戏定义了一个重要度 $d_i$ ，为 $p$ 的前缀最小值，小k每次惠选择 $d$ 最低的关卡闯关，特殊地，如果这样的关卡有很多个，那么他会选择编号最小的那一个。

给出小k 通关的顺序，求出所有可能的难度中字典序最小的

简单构造。先构造 $d$ ，必要的时候加一，也就是说 $a$ 的下标比 $b$ 的下标更靠前，却先打了 $b$ ，那么 $a$ 的重要度一定是更高的

然后根据 $d$ 构造 $p$ 即可

T2洛谷 P3616

小P的家门前有一条河，它每天要观察这条河，并且统计河中岛屿的个数。

河床的地形可以抽象为一个长度为 $n$ 的数列 ${a_i}$ ，第 $i$ 位的数字代表河床对应位置的高度。当水位为 $h$ 时，所有高度低于 $h$ 的位置都会被水覆盖，高度大于等于 $h$ 的地形就露出水面，连成了岛屿。

请你协助小 P 统计每一天的岛屿的个数。河床每个位置的高度可能会发生变化，而且水位也会发生变化。

如果形成了岛屿一定是 $h_i \ge h, h_{i+1} < h$ 那么以 $h_i$ 为横坐标， $h_{i+1}$ 为纵坐标构建一个二维平面那么答案应该是这部分

使用树状数组维护

给定一个只由非负整数和加减号组成的算式。它想给这个算式添加合法的括号，使得算式的结果最大，括号可以嵌套。

线性 dp

$f_{i, j}$ 表示前 $i$ 个数，缺了 $j$ 个右括号需要配对的最大答案，根据当前位置加什么括号转移

Code

f[0][0] = 0;
f[0][1] = f[0][2]=-1e18;
for (int i = 1; i <= n; i++) if (a[i] < 0)
{
	f[i][0] = f[i-1][0] + a[i];
	f[i][2] = max(f[i-1][1], f[i-1][2]) - a[i];
	f[i][1] = max(max(f[i-1][0], f[i-1][1]), f[i-1][2]) + a[i];
}
else
{
	f[i][0] = max(max(f[i-1][0], f[i-1][1]), f[i-1][2]) + a[i];
	f[i][1] = max(f[i-1][1], f[i-1][2]) - a[i];
	f[i][2] = f[i-1][2] + a[i];
}

10.2

有两类奇特的生物 A 和 B，其基因序列只由 l 和 t 两种字母组成。

一开始，两类生物体内的基因序列都是一个 l，A 类生物体内的 l 基因可能突变为 lt 和 ltl，B 类生物体的 l 基因则可能突变为 ltl,lt 和 tl。

给定一些生物的基因序列，判断是否可能属于 A 类和 B 类

首先不可能出现连续的两个 l

对于 A 类来说，实际上是在 l 后插入 t 或 tl，那么绝对不可能有 t 前面没有 l

给定一棵 $n$ 个结点构成的树。

你需要给树上的 $n$ 个结点进行编号，其中有 $a$ 个结点需要编号为 $1,2,\dots,a$ 中的不重复的编号作为白点；剩下的 $b$ 个结点需要编号为 $-1,-2,\dots,-b$ 中的不重复的编号，作为黑点

现在有一个程序，它会对这棵树运行次如下步骤：

从黑色和白色中随机一个颜色，且需要保证目前图上仍然存在这种颜色的点。
如果随机到的是白色，程序将会删除编号绝对值最小的白点，并删除与之相连的所有边；
如果随机到的是黑色，程序将会删除编号绝对值最小的黑点，并删除与之相连的所有边。
请给这些点合适的编号，使得任何情况下，程序运行过程中都不会出现剩余未被删除的点不连通的情况

我们把整棵树分为大小分别为 $a$ 和 $b$ 的两部分，从叶子节点分别向上标号即可

Code

int siz[MAXN], fa[MAXN];
void dfs1(int u, int dad)
{
	siz[u] = 1; fa[u] = dad;
	for (int v : e[u]) if (v != dad)
	{
		dfs1(v, u);
		siz[u] += siz[v];
	}
}
void worka(int u, int dad)
{
	for (int v : e[u]) if (v != dad)
	{
		worka(v, u);
	}
	num[u] = ++cnta;
}
void workb(int u, int dad)
{
	for (int v : e[u]) if (v != dad)
	{
		workb(v, u);
	}
	num[u] = --cntb;
}
int main()
{
	dfs1(1, 0);
	for (int i = 1; i <= n; i++)
	{
		if (siz[i] == a)
		{
			flag = 1;
			worka(i, fa[i]);
			workb(fa[i], i);
			break;
		}
		if (siz[i] == b)
		{
			flag = 1;
			workb(i, fa[i]);
			worka(fa[i], i);
			break;
		}
	}
}

有一棵 $n$ 个结点的树，编号为 $1$ 到 $n$ ，每个点有一个颜色，颜色编号的范围是 $1$ 到 $m$ ，保证每种颜色至少出现一次。

你需要选择一个结点作为根，同时找一个树上节点的非空子集 $T$ ，满足每种颜色都至少在 $T$ 中出现一次，并且 $T$ 中所有点的 $LCA$ 的深度最大。定义你选的根深度为 $1$ ，儿子的深度是父亲深度 $+1$ 。

枚举 $LCA$ ，问题实际上变为了选取 $LCA$ 的某些子树作为点集，在剩下的子树中找以 $LCA$ 为一端的最长链，以另一端作为根

使用 dsu on tree 维护点集颜色即可

10.3

小 C 生活的城市可以用一个长度为 $n$ 的线段来表示。线段上（包含端点）平均分布着 $n+1$ 个点，从左到右编号为 $1,\dots,n+1$ 。

他将第 $i$ 个点称为 $A_i$ ，线段 $A_iA_{i+1} (i \leq i \leq n)$ 称为第 $i$ 个区。第 $i$ 个区的人对晴天的渴望度形式化成 $s_i$ 。

晴天的范围不能覆盖整个城市，形式化地说，若 $A_p$ 为覆盖范围的中心，那么当且仅当第 $i$ 个区和 $A_p$ 之间隔着的区域少于 $d$ 个（不包括第 $i$ 个区本身），第 $i$ 个区会被晴天覆盖。

如果第 $i$ 个区在晴天的覆盖范围内，并且和晴天中心还隔着 $x$ 个区，那么这个区的人的开心值为 $(d-x)^2 \times s_i$ 。这个城市的开心值为每一个区的开心值之和。

小 C 想知道如果晴天的地点可以任选，那么最后城市的开心值最大是多少。

我们分别处理中心左右两侧的贡献

假如 $d = 3$ ，那么周围这些区的贡献的系数为 $9, 4, 1，0$ ，中心向后移动一个点，系数变为 $0, 9, 4, 1$ ，变化了 $5, 3, 1$ ，维护中心移动的变化 $O(n)$ 扫一遍

需要 $O(1)$ 维护变化，动态维护 $d$ 项的和。

Code

for (int i = 1; i <= d; i++) {
	ans1[1] += (d - i + 1) * (d - i + 1) * a[i];
	if (i > 1)
		tmp += (d - i + 1) * a[i];
}
for (int i = 1; i <= n; i++) {
	int l = max(1, i), r = min(n, i + d);
	ans1[i + 1] = (ans1[i] - d * d * a[i] + tmp * 2 + sum[r] - sum[l]);
	tmp += sum[r] - sum[l];
	tmp -= a[i + 1] * d;
}

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

for (int i = 1; i <= d; i++) {
	ans2[1] += (d - i + 1) * (d - i + 1) * a[i];
	if (i > 1)
		tmp += (d - i + 1) * a[i];
}
for (int i = 1; i <= n; i++) {
	int l = max(1, i), r = min(n, i + d);
	ans2[i + 1] = (ans2[i] - d * d * a[i] + tmp * 2 + sum[r] - sum[l]);
	tmp += sum[r] - sum[l];
	tmp -= a[i + 1] * d;
}
reverse(ans2 + 1, ans2 + 2 + n);
for (int i = 1; i <= n + 1; i++) {
	ans = max(ans, ans1[i] + ans2[i]);
}

给一个长度为 $n$ 的序列 $A$ ，你可以删去原序列的一些数，或者一个数都不删除，将剩下的数按照原来的顺序组成新的长度为 $m(1 \ge m \ge n)$ 的序列。

现在你想知道，对于所有合法的序列 $B$ ， $\sum_{i=1}^{m}\left[B_{i}=i\right]$ 的最大值是多少。

先考虑暴力DP

$f_{i}$ 表示前 $i$ 个数，以 $i$ 结尾的答案

f(i)=\max \left\{f(j)+1 \mid j<i, a_{j}<a_{i}, a_{i}-a_{j}<i-j\right\}

那么转移的条件就是 :

$j < i$
$a_j < a_i$
$a_i - a_j < i - j$

将序列按照 $a_i$ 排序，然后求⼀个最⻓的 $i - a_i$ 不下降的⼦序列⻓度即可

10.4

div.1

小 A 和小 B 竞选班长流程如下：
在 $[1, n]$ 中随机选取一个区间 $[l, r]$ ，统计区间内同学的投票情况，如果二人票数之差的绝对值不超过 $k$ ，那么平局，都是班长；否则票数高的同学当选。小 A 担心落选，准备收买一些同学，使得在任何情况下自己都能成为班长。已知收买编号为 $i$ 的同学的花费为 $2^i$ ，请问小 A 的最少花费是多少

进行一个贪心，每次在不满足的情况下选取下标最小的人收买，所以倒序枚举，不行就收买一下

有 $n$ 个被抽象成矩形的同学在拍照。其中第 $i$ 个同学宽为 $w_i$ ，高为 $h_i$ 。
需要宽为所有 $w$ 之和，高为所有 $h$ 最大值的相框才能容下所有的同学。
为了缩小相框的面积，你可以让一部分同学躺下。第 $i$ 个同学躺下之后，他的宽变成 $h_i$ ，高变成 $w_i$ 。
同时，太多人躺着不好看，所以最多只能有 $\left \lfloor \frac{n}{2} \right \rfloor$ 个同学躺下。

我们枚举最后相框的高度 $h$ ，对于第 $i$ 个人，有以下几种情况：

$h_i \leq h, w_i \leq h$ ，躺不躺都可
$h_i \ge h, w_i \leq h$ ，一定要躺
$h_i \leq h, w_i \ge h$ ，一定不能躺
$h_i \ge h, w_i \ge h$ ，说明 $h$ 不合法
那么只有第一种情况的人有操作空间，如果躺下的话，宽度会减小 $w_i - h_i$ ，按这个值排序取最优的即可

求出满足以下条件的 $n \times m$ 矩阵个数:

对于每一行有 $l_i, r_i$ ，表示 $1 \sim l_i$ 有且仅有一个 $1$ ， $r_i \sim m$ 有且仅有一个 $1$ , 其余全为 $0$

每一列最多有一个 $1$

因为每列最多都只能有一个 $1$ ，所以我们一每一列划分状态来 DP 。

把每一行的限制为前缀和后缀两个，一共有 $2n$ 个限制，每一列只能满足这 $2n$ 个限制中的一个

$prel_i$ 表示 $l \in[1, i]$ 的行有多少个， $prer_i$ 表示 $r \in[1, i]$ 的行有多少个。 $f(i,j)$ 表示前 $i$ 列，有 $j$ 列用来满足 $r \in [i, i]$ 的后缀限制的方案数，那么

f(i, j) = f(i-1,j) + f(i-1,j-1) \times (prer_i - j + 1)

以及 $l = i$ 的前缀限制

f(i,j) = f(i,j) \times \frac{\left(i-prel_{i-1}-j\right) !}{\left(i- prel_i-j\right)!}

div.2

期望不会

给定一些长度的边，求用这些边的其中一些组成 $k$ 个三角形的最大边长和

贪心，尽量选边长大的。

具体来说就是先预处理出一组最大的边长，然后按长度递减枚举， $a, b, c$ 为当前枚举的一组， $x, y, z$ 为上一组

如果 $x, y, z$ ，满足构成三角形的条件，直接更新，接着枚举
否则考虑拆开 $a, b, c$ $a, b, c$ ，使得 $x, y, z$ $x, y, z$ 也可以被选，枚举一下几种情况：
- $(a, x, y)$ 和 $(b, c, z)$
- $(a, b, x)$ 和 $(c, y, z)$
- $(a, c, x)$ 和 $(j, y, z)$
- 都不行接着枚举 $(x, y, z)$

10.5

有一个长度为 $n$ 的序列 $A$ 和模数 $p$ ， $A_i$ 表示 $a^{i-1}$ , 但是不知道 $a$ 是多少的，求出 $a$

好像正解挺复杂的，但是人类智慧整出来了和T1相匹配的难度。

$mul$ 表示整个序列的乘积， $sum$ 表示整个序列的和

$mul = a^{\frac{n-1}{2}}$ ， $sum$ 使用等比数列求和公式，枚举 $a$ 来 check 即可

小S被老师安排去排一个新班级的座位。新班级有 $n$ 位同学，他们的成绩按顺序分别为 $a_1,a_2,\dots,a_n ,(a_i\leq a_{i+1})$ 。为促进互帮互助，一对同桌的成绩之差的绝对值必须大于等于给定的 $K$ ，但这样会导致一些同学没有同桌，所以请你求出他最多能排出几对同桌

对于每个数，贪心配对即可，没什么好说的

小k在下飞行棋，棋盘是一行共 $n$ 个格子，编号依次为 $1 \sim n$ 。小K有外挂，所以他会通过外挂来前进，他共有 $m$ 个外挂，第 $i$ 个外挂能让他从第 $l_i$ 格瞬移到第 $r_i$ 格，并花费 $1$ 的时间，并且小K很D，所以他不需要外挂就能往回走，且往回走不需要时间。

但是小K的 rp 不太好，现在发生了 $q$ 次事件，每次事件中，小K的某一个挂会坏（这次事件结束后又会恢复），而你需要帮他求出此时他从 $s$ 走到 $t$ 要花费的最小时间

倍增跳，维护第 $i$ 个位置出发的最大值和次大值。挂失效了就重新跳

Code

#include <bits/stdc++.h>
#define MAXN 200005
#define MXBT 19

using namespace std;
namespace OCTANE
{
	template <typename  T> inline void read(T &x)
	{
		x = 0; bool f = 0;
		char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = 1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9')
		{
			x = (x << 1) + (x << 3) + (ch^48);
			ch = getchar();
		}
		if (f) x = -x;
	}
	template <typename T, typename ... TT>
	void read(T &x, TT &... xx)
	{
		read(x); read(xx...);
	}

}using namespace OCTANE;

struct node
{
	int to, id;
};

struct nood
{
	node mxz, mxxz;
	void change(node a)
    {
        if(a.to > mxz.to) mxxz = mxz, mxz = a;
        else if(a.id != mxz.id and a.to > mxxz.to)
        {
			mxxz = a;
		}
	}
}a[MAXN];

int n, m, q;

int l[MAXN], r[MAXN];

int f[MAXN][20];
int g[MAXN][20];

int main()
{
	read(n, m);
	for (int i = 1; i <= m; i++)
	{
		read(l[i], r[i]);
		a[l[i]].change({r[i], i});
	}
	for (int i = 1; i <= n; i++)
	{
		a[i].change(a[i-1].mxz);
		a[i].change(a[i-1].mxxz);
		f[i][0] = a[i].mxz.to; g[i][0] = a[i].mxxz.to;
	}
	for (int j = 1; j <= MXBT; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			f[i][j] = f[f[i][j-1]][j-1];
			if (a[g[i][j-1]].mxz.id == a[i].mxz.id)
				g[i][j] = g[g[i][j-1]][j-1];
			else
				g[i][j] = f[g[i][j-1]][j-1];
		}
	}

	read(q);
	while(q--)
	{
		int id, s, t, ans = 0;
		if (t < l[id]) id = 0;
		if (s < l[id])
		{
			for (int i = MXBT; ~i; i--)
			{
				if (f[s][i] < l[id]) ans += (1 << i), s = f[s][i];
			}
			ans++; s = f[s][0];
		}
		if (s >= t)
		{
			printf("%d\n", ans); continue;
		}
		for(int i = MXBT; i >= 0; i--)
		{
			if (a[s].mxz.id == id)
			{
				if (g[s][i] < t) ans += (1 << i), s = g[s][i];
			}
			else
			{
				if (f[s][t] < t) ans += (1 << i), s = f[s][i];
			}
		}
		ans++;
        if (a[s].mxz.id == id) s = g[s][0]; else s = f[s][0];
		if (s < t) printf("-1\n"); else printf("%d\n", ans);
	}

	return 0;
}

教练给小Z布置了一个作业，教练给出了 $n$ 个命题，让他证明 $n$ 个命题全部为真。但是小Z非常的懒，一旦需要证明的命题数量大于 $k$ ，小Z就会摆烂不完成作业。因此小Z向他的好朋友黑恶卷怪小L求助。小L帮小Z证明了 $m$ 个等价关系，即对于 $1\leq i \leq m$ ，小L证明了 $u_i$ 和 $v_i$ 是等价的。小L把他的成果发给了小Z，但是网络质量不佳，小Z只收到了一个区间的等价关系证明。现在有 $q$ 条时间线，你需要对于每条时间线，求出假如小Z收到了第 $l \sim r$ 个等价关系的证明，小Z是否能够完成作业

维护一个 $f_i$ 表示以 $i$ 为左端点，能够完成需要的最近的 $r$

使用并查集维护联通性。用线段树分治处理时间段，因为 $f$ 从 $m$ 开始枚举，所以先处理右儿子

Code

#include <bits/stdc++.h>
#define MAXN 1000005

using namespace std;

int n, m, k, Type, q;

namespace union_set
{
	struct node
	{
		int x, y, add;
	};

	int fa[MAXN], siz[MAXN], cnt;
	node sta[MAXN << 2]; int top;

	void init()
	{
		for (int i = 1; i <= n; i++) { fa[i] = i; siz[i] = 1; cnt = n; }
	}

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

	void merge(int x, int y)
	{
		int fx = find(x), fy = find(y);
		if (fx == fy) return;
		if (siz[fx] > siz[fy]) swap(fx, fy);
		siz[fy] += siz[fx]; fa[fx] = fy;
		cnt--;
		sta[++top] = {fx, fy, 1};
	}

	void eko(int x, int y, int z)
	{
		fa[x] = x; siz[y] -= siz[x]; cnt += z;
	}

}using namespace union_set;

#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)

struct nood
{
	int x, y;
}e[MAXN];

vector <int> v[MAXN << 2];

int f[MAXN], now;

void add(int i, int l, int r, int L, int R, int u)
{
	if (l >= L && r <= R) { v[i].push_back(u); return; }
	int mid = (l + r) >> 1;
	if (mid >= L) add(ls(i), l, mid, L, R, u);
	if (mid+1 <= R) add(rs(i), mid+1, r, L, R, u);
}

void solve(int u, int l, int r)
{
	int last = top;
	for (auto k : v[u]) merge(e[k].x, e[k].y);
	if (l == r)
	{
		while (now && cnt > k)
		{
			if (now < l) add(1, 1, n, now, l-1, now);
			merge(e[now].x, e[now].y);
			now--;
		}
		if (cnt <= k) f[l] = now + 1;
	}
	else
	{
		int mid = (l + r) >> 1;
		solve(rs(u), mid+1, r); solve(ls(u), l, mid);
	}
	while (top > last) eko(sta[top].x, sta[top].y, sta[top].add), top--;
}

int main()
{
	read(n, m, k, Type);
	for (int i = 1; i <= m; i++)
	{
		int u, v; read(u, v); e[i] = {u, v};
	}
	now = m; init();
	solve(1, 1, m);
	read(q);
    unsigned int lastans = 0;
    while (q--)
	{
		int l, r; read(l, r);
        if (Type)
		{
            l = ((unsigned int)l + lastans) % m + 1;
            r = ((unsigned int)r + lastans) % m + 1;
            if (l > r) swap(l ,r);
        }
        lastans <<= 1;
        if (f[r] >= l) lastans++;
        puts(f[r] >= l ? "Yes" : "No");
    }
	return 0;
}

10.6

我们定义一个序列是单峰的，当且仅当它满足以下一个条件：

存在一个下标 $k(1\le k\le n)$ 满足 $a_1 < a_2 < a_3 < \dots < a_k > a_{k+1} > \dots > a_n$

存在一个下标 $k(1\le k\le n)$ 满足 $a_1 > a_2 > a_3 > \dots > a_k < a_{k+1} < \dots < a_n$

一个非单峰序列可以进行若干次Swap操作使得序列变成单峰的。小C每次会在序列的末尾添加一个新的元素 $x$ ，小C想知道每次添加新的元素后，序列最少进行几次Swap操作可以变成单峰的

考虑到单峰的定义，我们保证每次添加的元素在之前没有出现过

对于每一个新插进来的数，可以插到前面，也可以插到后面

它的贡献是中间是没放的数中下标比它大的比下标比它小的更多就放前面，否则放后面

考虑逆序对，二分即可

Code

#include <bits/stdc++.h>
#define ll long long
#define MAXN 300005

using namespace std;
int n;

namespace doubleForkIndexTree
{
    #define lowbit(i) (i & -i)

    int t[MAXN];

    void add(int pos, int val)
    {
        while (pos <= n) { t[pos] += val; pos += lowbit(pos); }
    }
    int query(int pos, int res = 0)
    {
        while (pos) { res += t[pos]; pos -= lowbit(pos); } return res;
    }

}using namespace doubleForkIndexTree;

int a[MAXN], h[MAXN];

vector <int> q[MAXN];

int iOrderPair[MAXN];

ll ans[MAXN];

void solve()
{
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= n; i++) q[i].clear();
    for (int i = 1; i <= n; i++)
    {
        h[a[i]] = i;
        iOrderPair[i] = query(a[i]);
        add(a[i], 1);
    }
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= n; i++)
    {
        int l = h[i], r = n, mid;
        while (l < r)
        {
            mid = (l + r) >> 1;
            if (query(mid) >= 2 * iOrderPair[h[i]]) r = mid; else l = mid + 1;
        }
        q[l].push_back(i); add(h[i], 1);
    }
    memset(t, 0, sizeof(t));

    ll v = 0;
    for (int i = 1; i <= n; i++)
    {
        v += query(n) - query(a[i]);
        for (int j : q[i]) add(j, -1);
        add(a[i], 1); ans[i] = min(ans[i], v);
    }
}

int main()
{
    read(n); memset(ans, 0x3f, sizeof(ans));
    for (int i = 1; i <= n; i++) read(a[i]), h[i] = a[i];
    sort(h+1, h+1+n);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(h+1, h+1+n, a[i]) - h;

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

    for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);

    return 0;
}

小 Q 要进行 $n$ 组体能训练。需要 $m$ 种配重圆盘。在第 $i$ 组训练中，需要 $w_{i,j}$ 个配重为 $j$ 的圆盘。小 Q 的训练器械是一个类似栈的结构，每次只能取出最上方的圆盘或把一个圆盘放在最上方，每次操作都要消耗一点体力。淸帮助小 Q 安排放圓盤的順序，使得消耗的體力最少

与处理出每次最多可以保留的圆盘，也就是 $min(w_{i-1, j}, w_{i,j})$ ，然后区间Dp

Code

memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n;i++)
{
	for (int j = 1; j <= m; j++) read(w[i][j]), g[j] = w[i][j];
	for (int j = i; j >= 1; j--) for (int k = 1; k <= m; k++)
	{
		g[k] = min(g[k], w[j][k]); cost[j][i] += g[k] * 2;
	}
	f[i][i] = cost[i][i];
}
for (int len = 2; len <= n; len++) for (int l = 1; l <= n - len + 1; l++)
{
	int r = l + len - 1;
	for (int k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] - cost[l][r]);
}

有 $n$ 个小朋友，第 $i$ 个小朋友站在 $x_i, y_i$ ，小 Q 在地上放置了 $n$ 个普通 🍬 ，小 Q 每次回选择一个小朋友，小朋友回每次选择距离他最近的糖果拿下，但是小 Q 还不小心把它喜欢的艾尔登法环掉到地上了，请问是否存在使唤小朋友的顺序，使得最后选剩下的是艾尔登法环

考虑一个贪心，处理出每个小孩不拿法环的情况下可以拿到的糖果，还有对应糖果可以被拿的小孩。

每次选择可以拿糖果的最少的小孩去拿可以被最少的小孩拿的糖果。这个贪心是对的

选择可以选点最少的小孩可以避免在这个小孩身上出锅，然后选择小孩最少的糖果可以给别的小孩操作空间

然后就是可行性，题目里的要求就是让小孩拿离他最近的糖果，根本没有选糖果的权利，那我们为什么可以选择呢？

经过手玩一下，可以发现可以构造方案使得想法成立。反正考场上又不会让证明贪心，想到就冲就完了

Code

#include <bits/stdc++.h>
#define MAXN 1005
#define ll long long

using namespace std;
int n;

struct node { ll x, y; };

node a[MAXN], b[MAXN], c;

vector <int> kid[MAXN];
vector <int> bel[MAXN];

int vis[MAXN];

ll dis(node a, node b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main()
{
    read(n);
    for (int i = 1; i <= n; i++) read(a[i].x, a[i].y); read(c.x, c.y);
    for (int i = 1; i <= n; i++) read(b[i].x, b[i].y);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
    {
        if (dis(a[i], c) >= dis(a[i], b[j]))
        {
            kid[i].push_back(j); bel[j].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int who = 0, which = 0;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && (!who || kid[j].size() < kid[who].size()))
            who = j;
        }
        for (int j : kid[who])
        {
            if (!which || bel[j].size() < bel[which].size())
            which = j;
        }
        if (!kid[who].size())
        {
            printf("IMPOSSIBLE"); return 0;
        }
        vis[who] = 1;
        for (int j : kid[who])
        bel[j].erase(lower_bound(bel[j].begin(), bel[j].end(), who));
        for (int j : bel[which])
        kid[j].erase(lower_bound(kid[j].begin(), kid[j].end(), which));
    }
    printf("POSSIBLE");

    return 0;
}

10.7

给定一个序列 ${a_1, a_2, \dots, a_n}$ 和一个整数 $s$ ，求有多少正整数序列 $\{k_{1}, k_{2}, \cdots, k_{n}\}$ ，满足 $\sum_{i=1}^{n} a_{i}^{k_{i}} \leq s$ ，其中 $n \le 8$ 。

$n \le 8$ 耶！

难得考试整签到题，直接上爆搜哇，但是就算是签到题直接搜也会寄的辣，折半搜就行了

Code

#include <bits/stdc++.h>
#define ll long long
#define the_great_will 10
#define Marika 10000005

using namespace std;

int great_will, ye_dead;

ll Dung_eater, deathbed[the_great_will], ye_live, Tarnished_elden_lord;

ll elden_ring[Marika]; int Tarnished;
ll elden_lord[Marika]; int demigods;

void dfs(int black_knives, int bless, ll goldmask)
{
    if (goldmask > Dung_eater) return;

    if (black_knives > bless)
    {
        if (bless == ye_dead) elden_ring[++Tarnished] = goldmask; else elden_lord[++demigods ] = goldmask;
        return;
    }

    ll lands_between = deathbed[black_knives];
    for (int grace = 1; grace; grace++)
    {
        if (lands_between + goldmask > Dung_eater) break;
        if (lands_between + ye_live - deathbed[black_knives] > Dung_eater) break;
        dfs(black_knives + 1, bless, goldmask + lands_between);

        lands_between *= deathbed[black_knives];
    }
}

int main()
{
    read(great_will, Dung_eater); ye_dead = (great_will >> 1);
    for (int grace = 1; grace <= great_will; grace++) read(deathbed[grace]), ye_live += deathbed[grace];

    dfs(1, ye_dead, 0); dfs(ye_dead+1, great_will, 0);
    sort(elden_ring+1, elden_ring+1+Tarnished);
    sort(elden_lord+1, elden_lord+1+demigods );

    for (ll grace = 1; grace <= Tarnished; grace++)
    {
        ll j = upper_bound(elden_lord+1, elden_lord+1+demigods , Dung_eater - elden_ring[grace]) - elden_lord - 1;
        Tarnished_elden_lord += j;
    }

    printf("%lld", Tarnished_elden_lord);

    return 0;
}

梅琳娜想种树，但是木头没脑子，决定让第 $i$ 个点的父亲在 $[1, i-1]$ 之间随机。但是木头又觉得太矮了，就决定给每个点加两个权值 $a_i, b_i$ , 表示第 $j$ 个点作为第 $i$ 个点的父亲的概率是 $\frac{a_{j}}{a_{1}+a_{2}+\cdots+a_{i-1}}$ , 且边 $(j, i)$ 的长度为 $b_i + b_j$ 。

要求贼拉多的燃料梅琳娜小姐很好奇这颗树的结构，每次询问 $u, v$ 的期望距离

根据期望的线性，答案是 $E(dep(u))+E(dep(v))-2 \times E(dep(lca(u, v)))$

$E(dep(u))$ 枚举父亲来求

\frac{\sum_{i=1}^{u-1} a_{i}\left(E(dep(i))+b_{i}+b_{u}\right)}{\sum_{i=1}^{u-1} a_{i}}

还有就是 $u, v$ 的 $lca$ 到到根的期望距离

E(lca(u, v))=\frac{a_{u} f_{u}+\sum_{i=1}^{u-1} E(lca(i, u))}{\sum_{i=1}^{u} a_{i}}

10.8

给两个序列 $a$ , $b$ ，⻓度分别为 $n$ , $m$ ，求相邻元素属于给定点对的 $a,b$ 公共⼦序列个数

先离散化。然后DP。

$f(i)$ 表示前 $j$ 个能配成几对，新找到一对，就加上以前找到的，所以前缀和优化就完了奥

Code

for (int i = 1;i<=n;i++)
{
	int s = 1;
	for (int j=1;j<=m;j++){
		int t=f[j];
		if (a[i]==b[j])	add(f[j],s),add(ans,s);
		if (mp[b[j]][a[i]])	add(s,t);
	}
}

$n$ 个点，初始时没有边项链，链接第 $i$ 和第 $j$ 个点的代价是 $d_{i,j}$
每个结点上住着一个魔法居民，若两个节点间有边直接相连，则他们成为邻居。居民一共有三种类型：

村民：他们只能拜访自己的邻居；

巫师：他们可以拜访自己的邻居以及邻居的邻居；

大魔法师：可以拜访所有与自己连通的人。
每种类型的居民要么不出现，要么至少出现两个。每个居民都希望可以拜访其他所有的居民。求在道路数目最少的前提下的最小代价。

进行一个情况的分与贪心

如果有村民的话，直接把每一个村民都和其他人连上边就行辣。这样巫师三：狂猎和大魔法师也满足了。

如果只有大魔法师的话，直接最小生成树就行了。

对于剩下的情况主要是这样的，可以以一个点为根向其余的点全连上边，所以最少的边数是 $n-1$ 。
巫师之间必须要连边或者连向同一个人，那么也就是说可以枚举上面说的 $n$ 。

还有就是只有两个巫师的情况，也可以直接他们之间连边，然后剩下的点哪个代价少连那个。特判取 $min$ 即可

给定两个序列，安排顺序，使得对应位置异或出来的新序列字典序最少

建两颗 Trie 树贪心，真是没什么好说的，怎么考试就没想出来呢麻麻地

Code

void query(int u, int v, int d, int now)
{
	a.siz[u]--; b.siz[v]--;
	if (cnt >= n) return;
	if (d < 0) { ans[++cnt] = now; return; }
	while (a.siz[lsa(u)] && b.siz[lsb(v)]) query(lsa(u), lsb(v), d-1, now);
	while (a.siz[rsa(u)] && b.siz[rsb(v)]) query(rsa(u), rsb(v), d-1, now);
	while (a.siz[lsa(u)] && b.siz[rsb(v)]) query(lsa(u), rsb(v), d-1, now + (1 << d));
	while (a.siz[rsa(u)] && b.siz[lsb(v)]) query(rsa(u), lsb(v), d-1, now + (1 << d));
}

10.10

有n座山，m只猫和p个工作人员。山从左往右编号为 $1 \sim n$ ，山 $i$ 和 $i-1$ 之间的距离是 $d$ 米。有一天，猫都到山上去玩了∶第 $i$ 只猫会到山 $h_i$ 去，并一直玩到时间 $t$ ，之后就在那座山等待工作人员来接它。每个工作人员的线路都是从1走到n，并带走沿途任意只在等待的猫。工作人员速度为每单位时间1米，不能在山上停留。安排每个工作人员出发的时间，使所有猫的等待时间总和最小

斜率优化DP

首先可以发现的是每个人一定是选择恰好可以接到一只猫的时候出发

$tim_i$ 表示想要恰好接到第 $i$ 只猫要从什么时刻出发。先对 $tim_i$ 排个序，那么在 $i$ 前面的都能被 $i$ 接到

那么 $f_{i, j}$ 表示第 $i$ 个人选第 $j$ 只猫的最小花费。

转移的话，比如说第 $i-1$ 个人选择了第 $k$ 只猫，第 $i$ 个人选择了第 $j$ 只猫，那么这个人可以把 $[k+1, j]$ 的猫全拿下，这些猫一共等待 $\sum\limits_{i = k+1}^{j} t_j - t_i$ 的时间，记录 $s$ 为 $t$ 的前缀和，转移就是

f_{i,j} = f_{i-1, k} + \sum\limits_{p = k+1}^j (t_j - t_p)

稍微变一变

\begin{align} f_{i,j} &= f_{i-1, k} + \sum\limits_{p = k+1}^j (t_j - t_p) \\ &= f_{i-1, k} + (j-k) \times t_j - s_j + s_k \\ &= f_{i-1, k} + jt_j - kt_j - s_j + s_k \\ \end{align}

发现对于 $k$ 是一个一次函数，斜率优化

给定一个长为 $n$ 的序列 $a$ ，对 $k \in [1, n]$ 求
$\sum\limits_{i = 1}^{k} \sum\limits_{j = 1}^{k} a_imod a_j$

每次 $k$ 加一会向外扩展一行和一列，也就是 $\sum\limits_{i = 1}^{k} a_k \% a_j + a_j \% a_k$

考虑优化，对于 $a_j \% a_k$ 我们把模运算变为除，分块，枚举 $a_k$ 的倍数

对于 $a_k \% a_j$ 我们在每个 $a_j$ 的位置上加上 $a_j$ , 然后查询 $a_k$ 位置上的前缀和就行辣

维护两个树状数组

Code

for (int k = 1; k <= n; k++)
{
	ll bs = a[k], t = 0;

	sum += bs; t1.add(bs, 1);

	ll tmp = 0;
	for (ll i = 0; i <= mx; i += bs, t++)
	{
		tmp += t1.query(i, i + bs - 1) * t;
		t2.add(i, a[k]);
	}
	ans += k * bs - t2.query(1, a[k]);
	tmp = sum - bs * tmp;
	ans += tmp;
	printf("%lld ", ans);
}

10.11

寄

10.12

有一个长度为 $n$ 的环， $s_i$ 表示 $i$ 位置上的颜色。每次从上面剪去一段长度为 $k$ 的连续段。再把剩余部分首尾相接，询问每次操作后的花环是不是美丽的

美丽指的是环上任意两个相邻位置的颜色不同

从保留的部分下手，对于一个确定的左端点 l, 它能保留到的右端点 r 是单调不增的，我们固定一个长度为 $k$ 的区间，如果区间有两个相邻相同的，那么这个区间就不能六，还有就是区间的做右端点不能相同

给一个竞赛图，令 $dist(u,v)$ 表示最短路，求 $\min\limits_{1\le u \le n} \max\limits_{1 \le v \le n} dist(u, v)$

手玩一下发现，答案只有 $0, 1, 2$ 三种可能

如果只有一个点，那么答案为 $0$

如果存在一个点和其他边都有连边，那么答案为 $1$

否则为 $2$

最大权完美匹配，转化为费用流，点之间连流量为 $1$ ,费用为 $$

给定一个数列 $A_{1 \dots n}$ ,

10.14 15

给定一个数列 $A_{1 \dots n}$ , 对于 $1 \dots n$ 的每一个 $k$ ，要把它分成 $k$ 的非空的连续段，对每段分别求和，得到 $k$ 个数，最大化他们的最大公约数

记前缀和为 $sum$ 那么也就是把和分为 $k$ 个部分，然后找到一个 $d$ 满足 $d \mid sum$ 并且 $d \mid sumk$

枚举约数即可

给定一个长度为 $n$ 的非负整数序列 $a_1,\cdots,a_n$ 。统计二元组 $(i,j)$ 的数量，满足 $1\leq i\leq j\leq n $ 且 $a_i\oplus a_{i+1}\oplus \cdots\oplus a_j\leq \max\{a_i,a_{i+1}\cdots,a_j\}$ 。

冷门数据结构，用笛卡尔树维护最大值，现在需要 $n^2$ 枚举最大值和区间然后可持久化 01Trie，考虑如何优化

我们枚举最大值是一定的，那么区间左右端点的维护可以类似于启发式合并，改为 01Trie 合并即可

给定一个 $k$ 求 $[L, R]$ 内满足下列条件的值的和
$\forall i \in [2, min(x-1, k)], i \nmid x$

一眼筛，我们先确定所有可能成为 $x$ 的约数的数。无非是比 $k$ 小的质数。

然后再用这些质数筛就完了

您在打音游，给定一个长为 $n$ 的序列 $p$ ，表示第 $i$ 个拍子您 $pperfect$ 的概率，您的得分由基础分和连击分构成。您已经出神入化，如果没有 $perfect$ ，就只会 $miss$
$S_i$ 表示第 $i$ 个音符是否 $perfect$
基础分 $= A \times \sum_{i-1}^{n} S_i$
连击分需要一个计算的函数 $f$
$f(i)=\left\{\begin{array}{lr} S_{i} & i=1 \\ f(i-1)+1 & i \neq 1 \wedge S_{i}=1 \\ f(i-1) \times t & \text { otherwise } \end{array}\right.$
连击分 $= B \times \left(\sum_{i-1}^{n} S_i\right)$
因为您一边睡觉一边打，会有一些突发事件导致某个位置的 $p$ 改变。每次询问 $[l, r]$ 的期望得分

推推小柿子，维护 $f$ 和总得分 $sum$ ，推式子发现可以矩阵优化，转移矩阵 $f, sum$ 和常数

然后就是线段树维护矩阵，单点修改，区间乘

其实也可以直接 $kx + b$ 维护总得分。矩阵的做法更好理解

10.16

一个 $n$ 个点的森林，每个点被涂成黑色或白色，需要删去一些边使得所有黑点的度数为奇数，所有白点的度数为偶数。求保留的边字典序最小的方案。

最能想到的方案就是直接把两个黑点连起来，实际上直接把两个黑点之间的路径连起来确实是对的。
除了在端点上的两个黑点，路径上的其他点都是一条边进，一条边出，度数不会改变，所以也就是说每次找两个黑点，打通之间的路径就行了，黑点个数不是偶数就无解

线段树维护边区间取反表示保留不保留就完了奥

一张图，每个点有点权，小 $k$ 和边之间有颜色，不能通过和自己一样颜色的边，但是小 $k$ 可以中途在任意一个点改变颜色，每次询问从给定的点出发，最多的点权和。

疯狂 $bfs$ 去处理出每个颜色的连通块和相交部分的连通块.

10.17

开始有 $n$ 个物品排成一行，每个物品有一个代价和一个价值。你可以选择两个相邻的代价之和不超过 $k$ 的物品，将它们从序列中删去，并获得两个物品价值之和的收益。求最大收益

区间 DP ， $f_{l,r}$ 表示 $l, r$ 个物品的贡献

for (int len = 2; len <= n; len++)
for (int l = 1, r = l + len - 1; r <= n; l++, r++)
{
	for (int _k = l+1; _k < r; _k++)
		f[l][r] = max(f[l][r], f[l][_k] + f[_k+1][r]);

	if (f[l+1][r-1] == sum[r-1] - sum[l] && a[l] + a[r] <= k) // 可以合并
		f[l][r] = max(f[l][r], f[l+1][r-1] + b[l] + b[r]);
}

一张 $n$ 个点的图，每条边有边权 $d , (d \le 9)$ ，每通过一条边后下一条边的花费都会乘 $10$ 。求从 $1$ 到 $n$ 的最短路。

因为边权小于 $9$ 所以少走一条边肯定更优，所以要尽量走少的边。

$bfs$ 预处理出只经过 $0$ 边可以到达 $n$ 的点，

然后每一条边的边权在答案中都贡献一位数，然后 $bfs$ 分层，最后 $bfs$ 找路径

Code

#include <bits/stdc++.h>
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;

int n, m, k;

int cnte = 1, head[MAXN];
struct edge
{
	int st, to, nxt, dis;
}e[MAXN << 2];
void adde(int u, int v, int w)
{
	e[++cnte].st = u;
	e[cnte].to = v;
	e[cnte].nxt = head[u];
	e[cnte].dis = w;
	head[u] = cnte;
}

int cnt0[MAXN], dep[MAXN];

queue <int> q; 
void bfs()
{
	memset(cnt0, -1, sizeof(cnt0));
	q.push(n-1); cnt0[n-1] = 0;
	while (q.size())
	{
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if (e[i].dis == 0 && cnt0[v] == -1)
			{
				cnt0[v] = cnt0[u] + 1;
				q.push(v);
			}
		}
	}
}

void bfs1()
{
	memset(dep, 0x3f, sizeof(dep));
	q.push(0); dep[0] = 0;
	while (q.size())
	{
		int u = q.front(); q.pop();
		if (cnt0[u] != -1) continue;
		for (int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if (dep[v] == 0x3f3f3f3f)
			{
				dep[v] = dep[u] + 1;
				q.push(v);
			}
		}
	}
}
int minc[MAXN]; bool vis[MAXN];
int pre[MAXN], st[MAXN];
void work()
{
	memset(minc, 0x3f, sizeof(minc));
	int dop = INF;
	vector <int> vq;
	for (int i = 1; i <= n; i++) if (cnt0[i] != -1)
	{
		if (dep[i] < dop)
		{
			dop = dep[i];
			vq.clear();
		}
		if (dep[i] == dop)
		{
			vq.push_back(i);
			st[i] = i;
		}
	}
	for(;dop!=0;dop--)
	{
		vector <int> tmp;
		sort(vq.begin(), vq.end(), [&](int x, int y)
		{
			return cnt0[st[x]] < cnt0[st[y]];
		});
		while (vq.size())
		{
			int u = vq.front(); vq.pop_back();
			if (vis[u]) continue; vis[u] = 1;
			for (int i = head[u]; i; i = e[i].nxt)
			{
				int v = e[i].to; if (dep[v] >= dop) continue;
				if (e[i].dis < minc[dop-1])
				{
					tmp.clear(); minc[dop-1] = e[i].dis;
				}
				if (e[i].dis == minc[dop-1])
				{
					tmp.push_back(v); pre[v] = u;
					st[v] = st[u];
				}
			}
		}
		vq = tmp;
	}
}
void pr1nt(int x)
{
	if (cnt0[x] != -1) return;
	pr1nt(pre[x]);
	print(minc[dep[x]]);
}
int main()
{
	#ifdef ONLINE_JUDGE
		freopen("great.in", "r", stdin);
		freopen("great.out", "w", stdout);
	#endif
	read(n, m);
	for (int i = 1; i <= m; i++)
	{
		int u, v, w; read(u, v, w);
		adde(u, v, w); adde(v, u, w);
	}
	bfs();
	
	bfs1();
	
	work();

	if (cnt0[0] == -1) pr1nt(0), putchar('\n');
	else puts("0");
	print(dep[st[0]] + cnt0[st[0]] + 1);

	return 0;
}

一棵 $n$ 个点的树，每条边都有一个边权，每次可以选择两个点 $u, v$ 让他们之间的路径都异或一个数 $x$ 。询问最少几次操作可以使所有边边权为 0

定义一个点的权值为它的所有出边异或起来。那么如果我们对 $u, v$ 进行操作，权值会改变的只有 $u, v$ 。
因为其他点一个进一个出，异或了白异或。

显然所有边权为 $0$ 。当且仅当所有点权值为 $0$

于是问题转化为了把这些点分为几组，分别操作。首先两个权值一样的点可以异或上这个权值，其他的状压枚举子集即可。

10.18

有 $n$ 堆石子，第 $i$ 堆有 $x_i$ 个，每次可以取从一堆中 $a \sim b$ 个。询问先手必胜还是必败。

经典套路打 SG 表找规律。

发现 SG 值是有规律的，大概是 1,0,2,3 构成的循环段，每段长为 $a$ ，每段一起看循环节为 a+b

T2ARC104F

给一个长度为 $N$ 的数列 $H_{1..N}$ ，第 $i$ 项在 $[1,H_i]$ 中选一个数，得到数列 $X_{1..N}$ 。再构造一个数列 $P_{1..N}$ ， $P_i=\max j(j<i, X_j > X_i)$ ，若不存在这样的 $j$ ， $P_i=-1$ 。求能够早出多少种 $P$

我真服了。

转化一下， $i$ 向 $p_i$ 连边，发现是一棵树》》。然后就开始区间 DP

$f_{l, r, v}$ 表示 $l$ 到 $r$ ， $x$ 的最小值的最大值为 $v$ 的森林数量

$g_{l, r, v}$ 表示 $l$ 到 $r$ ， $x$ 的最大值为 $v$ 的森林数量

转移的话

g_{L, R, V}=f_{L+1, R, V-1}\left(H_{L} \geq V\right) \\ f_{L, R, V}=g_{L, R, V}+\sum_{K=L}^{R-1} \sum_{W=1}^{V} f_{L, K, W} \times g_{K+1, R, V}+\sum_{K=L}^{R-1}\left[H_{K+1} \geq V\right] \sum_{W=1}^{V-1} F_{L, K, V} \times g_{K+1, R, W}

$g$ 的转移的意思是：因为 $H_{l} > v$ , $l$ 这个位置的树可以当作 $[l+1, r]$ 的根把他们都连起来

$f$ 的转移的意思是：首先是树的数量，然后枚举可能成为根的树，把他和和他差不多的连起来，然后枚举可能成为跟但没有的树，和其他树构成森林

T3CF1140F

定义一个点集合 $S=\{(x_i,y_i)\}(1\leq i\leq n)$ 的拓展操作为将符合以下条件的 $(x_0,y_0)$ 加入 $S$ ：

存在 $a,b$ ，使得 $(a,b),(a,y_0),(x_0,b)\in S$ 。
不断执行以上操作直到不能操作，此时得到的集合即为拓展集合。现在给定 $q$ 个操作，每次加入或删除一个点，重复点即为删除，你需要输出每个操作之后的拓展集合大小（

看扩展的这个过程，其实就是二分图，左边左部点，右边右部点，并查集维护 siz 乘起来就是答案。
时间轴用线段树分治维护

Code

s1z 表示左部点大小, s2z 表示右部点大小， res 表示答案

void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	if (fx == fy) return;
	if (rk[fx] > rk[fy]) swap(fx, fy);
	sta[++top] = {fx, fy, s1z[fy], s2z[fy], rk[fy], res};
	fa[fx] = fy;
	rk[fy] += rk[fy] == rk[fx];
	res -= 1LL * s1z[fx] * s2z[fx] + 1LL * s1z[fy] * s2z[fy];
	s1z[fy] += s1z[fx]; s2z[fy] += s2z[fx];
	res += 1LL * s1z[fy] * s2z[fy];
}

10.19

T1CF1163F

一个无向图，每次把修改一条边的边权，询问 $1$ 到 $n$ 的最短路长度。询问间相互独立

分类讨论

令 $dis1_i$ 表示 $1$ 出发到 $i$ 的最短路， $dis2_i$ 表示 $n$ 出发到 $i$ 的最短路，修改的边的端点为 $u$ 和 $v$ , 修改的边原来的权值是 $x$ ，现在的权值是 $y$ ，原来最短路为 $dist$

如果修改的边不在原来的最短路上，那么答案为 $min(dist, dis1_u + y - x + dis2_v, dis2_u + y - x + dis1_v)$ 。可以 $O(1)$

如果修改的边在原来的最短路上，那么答案为 $min(dist - y + x, \text{不经过 u, v 的最短路})$

那么不好维护的就是不经过 $u, v$ 的最短路。枚举不在 $u, v$ 的边权，线段树维护，区间修改

T2CF1630B

给定一个长度为 $n$ 的数组 $a$ 。你需要确定一个范围 $[x,y]$ ，并将 $a$ 数组分成 $k$ 段，使得对于每一段，在范围 $[x,y]$ 以内的元素个数大于在范围 $[x,y]$ 以外的元素个数。请求出任意一组使得 $y-x$ 最小的 $x,y$ 和划分的方案。

答案区间显然是越大越行，双指针枚举值域，对于每个 $r$ ，求出最小的合法的 $l$ ，贪心构造方案即可

Code

void ma1n()
{
	read(n, k); res = 561651561; cnt0 = 0; cnt1 = n;
	for (int i = 1; i <= n; i++)
	{
		read(a[i]); cnt[a[i]]++;
	}
	int l = 1; 
	for (int r = 1; r <= n; r++)
	{
		cnt0 += cnt[r]; cnt1 -= cnt[r];
		if (cnt0 - cnt1 < k) continue;
		while (l <= r && cnt0 - cnt1 >= k)
		{
			int tmp = r - l + 1;
			if (tmp < res)
			{
				res = tmp;
				resl = l; resr = r;
			}
			else if (tmp == res && l < resl)
			{
				resl = l, resr = r;
			}
			cnt0 -= cnt[l]; cnt1 += cnt[l++];
		}
	}
	cout << resl << ' ' << resr << '\n';
	cnt0 = 0; cnt1 = 0;
	int last = 1, tot = 0;
	for (int i = 1; i <= n; i++)
	{
		cnt[a[i]]--;
		if (a[i] >= resl && a[i] <= resr)
		cnt0++; else cnt1++;
		if (cnt0 - cnt1 == 1 && tot < k - 1)
		{
			cout << last << ' ' << i << '\n';
			last = i + 1; tot++;
			cnt1 = cnt0 = 0;
		}
	}
	cout << last << ' ' << n << '\n';
}