逃离地球的做题记录

2020-03-26 · 34 min read

这个表格记录了我做过的一些觉得不错的题，不定期更新。🙃

	题目编号	一句话题意	简单题解	备注
1	luoguP1273	叶子节点有点权，边有边权，选出一些边，使得一些叶子节点与根节点相连，且使点权和减边权和大于 0，最大化与根节点相连的叶子节点个数	树上背包，设 $f[i][j]$ 表示 i 节点连接 j 个叶子节点的收益最大值，对每个孩子进行一次分组背包	需要进行一定优化，在背包时设容量最大值为节点的子孙叶子节点个数，而不是总叶子节点个数，否则会TLE.
2	SPOJ1716/1043	维护一个序列，支持区间修改，求区间最大子段和，数据范围 50000.	线段树，每个节点存区间最大子段和，以左端点为起点的最大子段和，和以右端点为终点的最大子段和，就可以进行 push_up 操作。
3	luogu1169	给一个 01 矩阵，求一个最大的 01 相间的子矩阵	悬线法，找到每个点向上最长扩展到哪，以那个点为上端点，向左右扩展。对每个点进行这样的操作，可以证明一定能找到正确答案。
4	cf Good Bye 2019 B	给一个数列，找到一个子序列使得这个子序列的最大值减最小值大于等于这个子序列的项数。	可以证明，假设存在一个子序列满足条件，那么这个子序列也一定存在一个长度为二的子序列也满足条件（如果没有，则任意两个数的差都为 1，那么显然最大值减最小值最大为长度减一，矛盾）。	做一道题一定要想想这道题有没有什么简单的性质，不要把题目想复杂。
5	SPOJ2713	维护一个数列，支持区间开方（向下取整），求区间和，数据范围 100000	线段树，但每次修改都遍历到叶子节点，并且记录每个节点的最大值，如果这个值为 1 ，则可以不用访问这个节点和它的孩子节点，因为根号 1 还是 1.	注意这题复杂度的分析
6	luoguP2151	给一个无向无权图，求从 S 点走到 E 点共走 T 步的方法数，不能沿着刚走来的边走回去，有重边无自环	由于不能沿刚走来的路走回去，则把每条边拆成两条有向边，把每条边看作一个点，把 $(x,y)$ 和 $(y,z)$ 这样连接同一个点的边之间连边。设 $dp[i][j]$ 表示从第 i 号边到 j 号边的方法数，可以使用矩阵加速优化。	注意看题意，应该是不能沿着刚走来的路走回去，而不是不能走回刚走来的地方。
7	luoguP5197	给一棵树，对这棵树进行染色，要求距离小于等于 2 的节点不能染相同颜色，求最少要染几种颜色	对于节点 $v$ ，所有与 $v$ 相连的节点之间和 $v$ 节点均不能染相同的颜色。而不和同一个节点相连的两个节点之间不互相影响。所以只需要找到度数最大的节点，并输出那个节点的度数 +1 即可。	同第4题
8	luoguP1083	给一个数列，支持区间减法（每次都一定减一个正数），且对于每次操作，如果这次操作后数列中有元素小于 0，则输出这次操作的编号，并结束程序。	显然答案满足单调性，即若第 i 次操作后有元素小于零，所有第 j $(j \ge i$ ) 次操作后一定也有元素小于 0. 考虑二分操作次数，每次使用差分数组进行统计，复杂度 $O(n)$ 。程序复杂度为 $O(n\log n)$ 。
9	POJ1733	给一个 01 数列，每次告诉你区间 $[l, r]$ 内的数和的奇偶性，问有多少个与前面给出的条件矛盾的条件	考虑前缀和，设 $\operatorname{sum}(i)$ 为前 $i$ 项的和，区间 $[l,r]$ 为奇即 $\operatorname{sum}(l)$ 与 $\operatorname{sum}(r)$ 奇偶性相同，区间 $[l,r]$ 为偶即 $\operatorname{sum}(l)$ 与 $\operatorname{sum}(r)$ 奇偶性不同。可以使用并查集的扩展域+离散化解决。	对于告诉区间某个性质的问题，有时可以转化为前缀和中两个数的性质的问题。
10	BNDSOJ1193	给 $n$ 个数，求有多少个连续的子序列，使得这个子序列的平均值大于 $k$ 。 $n\le 100000$	把数组中每个数减 $k$ ，即要求有多少连续子序列之和大于 $0$ .考虑计算前缀和，答案就是前缀和序列的“正序对”个数，可以用树状数组或归并排序以 $\Theta(n\log n)$ 的复杂度求解。	转化为前缀和的步骤思维难度较大。且一定要会归并排序和树状数组。
11	luoguP4451	给一颗有边权的树，找一条边权异或和最大的路径。	考虑统计每个点到根节点的异或和，设为 $d(x)$ ，不难发现， $d(x) \operatorname{xor} d(y)$ 就是 x 到 y 的路径的异或和（二者都包括 root 到 $\operatorname{lca}(x,y)$ 的一段路径，异或起来为0，剩余部分为 x 到 y 的路径），则问题转化为给出 n 个数，找出异或和最大的两个，可以用 trie 树求解。	注意异或的性质
12	LOJ10155	如果一个数 $x$ 的约数（不包括他本身）的和 $y$ 比他本身小，那么 $x$ 可以变成 $y$ ， $y$ 也可以变成 $x$ 。限定所有数字变换在不超过 $n$ 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。	把一个数和所有可以和它相互变换的数连边，容易发现形成了一个森林。（每个节点至多连接一个比自己小的数，视为父亲）只需求森林中出所有树的直径的最大值即可。
13	luoguP3177	将一颗有边权的树黑白染色，给定黑点和白点的个数，最大化黑点两两之间的距离之和加白点两两之间的距离之和。	考虑统计每条边 $(u,fa(u))$ 对答案的贡献，为这条边两边的黑点数之积乘边权加上这条边两边的白点数之积乘边权。再使用树形 dp 找到最优解，设 $f_{i,j}$ 表示 i 节点的子树中有 j 个黑色节点时，i 节点的子树中所有边对答案的贡献的最大值。转移时只需要统计所有边 $(u,son(u))$ 的贡献，并给每个儿子分配一些黑点，可以用树上背包求解。	注意 f 数组的初始化，令 $f_{i,0}=f_{i,1}=0$ （因为 i 点可能是黑点或白点，所以可以由 $f_{i,0}$ 或 $f_{i,1}$ 转移而来），其他设为无穷小。
14	luoguP6476	有 $10^{20}$ 个格子，给 $p_1$ 和 $p_2$ ，对格子染色， $p_1$ 倍数的格子染红， $p_2$ 倍数的格子染蓝，既是 $p1$ 又是 $p_2$ 倍数的格子可以染两种颜色，问有没有一种染色方法，使不存在 $k$ 个有颜色的格子的颜色相同	考虑 $p_1$ 和 $p_2$ 互质的情况，设 $p_1 \le p_2$ ，根据裴蜀定理， $\exist x,y\in\R,\ xp_1-yp_2=1$ ，这里是极限情况，如果要满足，必须要使 $(yp_2,(y+1)p_2)$ 中不超过 $k$ 个红色格子，即 $(k-1)*r+1\ge b$ ，判断即可。同时，若 $p_1$ 和 $p_2$ 不互质，由于格子数量可以看作 $\infin$ ，故先把 $p_1$ 和 $p_2$ 除 $\gcd(p_1,p_2)$ 即可。	注意特判 $k=1$ 时的情况
15	luoguP1972	给一个数列，多次询问，每次询问一个区间中有多少个不同的数。	考虑离线，把询问以右端点为关键字排序，把数列从左往右扫，建立一个树状数组，树状数组的第 k 项为 1 代表数列的第 k 项是当前扫到的最后一个大小为 $a_k$ 的数。在扫到 r 时统计所有右端点为 r 的询问，则询问 $[l,r]$ 的答案为树状数组第 l 项到第 r 项的和。	经典离线题，思路值得借鉴。
16	BNDSOJ770	有区间 $[1,N]$ ，区间的每个点上可以种若干种不同的树。有两个操作，第一个操作是在区间 $[L,R]$ 上种上第 $k$ 种树（保证所有种植第 $k$ 种树的区间两两交集为空），第二种操作是查询区间 ${L,R}$ 有几种树。	查询有几种树即查询有几个操作 1 的区间 $[l_i,r_i]$ 和当前的区间 $[L,R]$ 有交集，有交集的充要条件是 $r_i\ge L$ 且 $l_i \le R$ 。那么答案就是 $l_i\le R$ 的区间个数 $-$ $r_i<L$ 的区间个数（显然 $r_i<L$ 的区间是 $l_i\le R$ 的区间，不会减多），可以用树状数组维护。	此类线段覆盖问题比较常见，「有交集的充要条件是 $r_i\ge L$ 且 $l_i \le R$ 」和找到合适的区间进行容斥是问题的关键。
17	luoguP1850	有 $n$ 节课，分别在 $v$ 个教室中进行，每节课有两个可选教室，默认是第一个教室，如果你选择更换，会有一定概率更换成功。你总共至多可以选择申请更换 $m$ 间教室，有些教室之间有一条无向边，使所有教室形成一张连通图。问经过某种申请方式，依次走到每一节课的教室的路程的期望值最小是多少。 $n, m≤2000, v≤300$ .	先用 floyd 算法计算出两两点之间的距离，再用 dp 计算期望。设 $dp[i][j][k]$ 为前 $i$ 节课申请改了 $j$ 个教室的路程期望最小值。 $k$ 表示是否在这个教室申请更换。然后就容易写出转移方程了，注意要考虑上一个教室如果申请，仍有一定概率申请失败，并且考虑这个教室申请的成功率。	开 float 会爆精度，要开 double.
18	BNDSOJ1377	给一个 $n*m$ 的方格，其中 $k$ 个格子有数字，求一条从 $(1,1)$ 到 $(n,m)$ 的最短路，是的路上的格子的数字和最大。 $n,m\leq 10^9，K\leq10^5$	把所有格子离散化，以横坐标为第一关键字排序，纵坐标以第二关键字排序，依次处理。设 $f_i$ 为走到第 $i$ 个格子的最大值。设 $t_i$ 为所有已处理的纵坐标为 $i$ 的格子中的 dp 最大值。那么对于第 $i$ 个节点 $(x,y)$ 就有状态转移方程式 $dp[i]=\max\limits_{j=1}^{y}t[j]+k[i]$ ，发现 t 数组可以用树状数组维护。	二维偏序、nlogn 求最长上升子序列等问题和此问题思路类似。
19	BNDSOJ1378	给一个 $n*m$ 的 01 矩阵，可以对每一行、每一列进行翻转，对于每个反转操作需要的能量不一样，求最多能得到几个 1和达到最多的 1 时花费的能量最小值，最初有 $p$ 的能量。 $N\leq 5000,M\leq 6,p\leq 100$	操作的先后顺序对答案没有影响，且一个操作至多操作一次。由于行数较小，可以暴力枚举行数，然后统计每列操作后会增加多少个 1，进行背包统计。	数据范围的特殊性是突破口
20	luoguP2513	求有多少个由 1~n 中所有整数组成的数列，使得这个数列中恰有 k 组逆序对。 $n,k\le1000$	设 $dp[i][j]$ 表示 1~i 组成的恰有 j 组逆序对的数列的个数。考虑在 1~i-1 组成的数列中插入 i，则有转移方程式 $dp[i][j]=\sum_{\max(j-i+1,0)}^jdp[i-1][k]$ . 发现是连续的一段的和，可以使用前缀和优化。	状态的设计和前缀和优化值得参考。
21	luoguP4316	给一张有向无环有权图，给定起点和终点，且已知起点与所有点联通，所有点与终点联通。求从起点走到终点的期望路径长度。	设从 $x$ 号点走到终点的路径长度期望为 $f[x]$ ， $x$ 号点的出度为 $k$ ， $k$ 个点分别为 $y_1,y_2\cdots y_k$ ，边权分别为 $z_1,z_2\cdots z_n$ ，则有 $f[x]=\frac1 k\sum_{i=1}^k (f[y_i]+z_i)$ . 在原图的反图上进行拓扑排序并转移即可。	从后往前递推是概率期望的常用方法。
22	luoguP1654	给出一个长度为 $n$ 的 01 串，其中第 $i$ 位为 1 的概率为 $p_i$ ，且一段长度为 $x$ 的极长的 1 可以贡献 $x^3$ 的分数，问分数的期望是多少。	当第 $i$ 位为 1 时，设以第 $i$ 位结尾的最长连续 1 串长度为 $t_i$ 。设 $a_i$ 为 $t_i$ 的期望，则有 $a_i=(a_{i-1}+1)\times p_i$ ；设 $b_i$ 表示 ${t_i}^2$ 的期望，则有 $b_i=(b_{i-1}+2a_{i-1}+1)\times p_i$ ；设 $c_i$ 表示 ${t_i}^3$ 的期望，则有 $c_i=(c_{i-1}+3b_{i-1}+3a_{i-1}+1)\times p_i$ 。则答案为 $\sum_{i=1}^n c_i$ .	此类记录期望高次幂的套路比较常用。
23	luoguP4550	有 $1\sim n$ n 个数，每次随机选择 1 个，第 $i$ 次选择的代价是 $i$ ，若选出所有数至少一次就结束。问期望代价和是多少。	设 $a_i$ 表示选出 $i$ 个不同的数的选择次数的期望，则有 $a_i=\dfrac{i}{n}(a_i+1)+\dfrac{n-i}{n}(a_{i-1}+1)$ 。化简得 $a_i=a_{i-1}+\dfrac{n}{n-i}$ . 设 $b_i$ 表示选出 $i$ 个不同的数的选择次数的平方的期望，则有 $b_i=\dfrac{i}{n}(b_i+2a_i+1)+\dfrac{n-i}{n}(b_{i-1}+2a_{i-1}+1)$ 。化简得 $b_i=\dfrac{i}{n-i}(2a_i+1)+b_{i-1}+2a_{i-1}+1$ 。则答案为 $\dfrac{a_n+b_n}{2}$ （等差数列求和公式）。	同上题
24	luoguP3802	有一个随机的 $1\sim 7$ 7 个整数组成的序列，其中 $i$ 有 $a_i$ 个。问有这个序列期望有几个长度为 7 的子串，满足这个子串的 7 个数字两两不同。	设 $s=\sum_{i=1}^7a_i$ ，第 $i$ 位到第 $i+6$ 位这个子串满足条件的概率是 $p=7!\times \dfrac{\prod_{i=1}^7 a_i}{\prod_{i=s-6}^si}$ 。由期望的线性性，答案为 $p\times(s-6)=7!\times \dfrac{\prod_{i=1}^7 a_i}{\prod_{i=s-5}^si}$ .
25	luoguP2216	有一个 $a\times b$ 的整数组成的矩阵，现请你从中找出一个 $n\times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 $a,b\le 1000, n\le 100$ .	设 $a$ 数组为原矩阵， $b[i][j]$ 表示 $\max(a[i][j],a[i][j+1],\cdots,a[i][j+n])$ 。则 $b$ 数组可以由 $a$ 数组每行依次单调队列求出。设 $c[i][j]$ 表示以 $(i,j)$ 为左上角的边长为 $n$ 的正方形中所有数的最大值。则 $c$ 数组可以由 $b$ 数组每列依次单调队列求出。同理，求出最小值的对应数组，再统计答案即可。
26	luoguP2340	有 $n$ 个二元组 $(a_i, b_i)$ ，其中 $a_i$ 和 $b_i$ 都是整数。从中选出 $k$ 个二元组，使得在满足 $\sum a_i\ge 0,\sum b_i\ge0$ 的条件下，最大化 $\sum (a_i+b_i)$ .	01 背包，以 $a$ 为体积， $b$ 为价值，计算选出的 $\sum a_i=k$ 时 $\sum b_i$ 的最大值，设为 $f_k$ 。则答案为 $\max\limits_{i=0}^{\sum a}\{[f_i\ge 0]\times(i+f_i)\}$ 。	注意滚动数组和处理负数时的越界问题。
27	luoguP4931	把 $n$ 对情侣安排在 $n$ 行 $2$ 列的座位中，要求恰好有 $k$ 对情侣坐在一排中，问有多少种排法。询问数 $T\le2\times 10^5$ ， $k\le n\le5\times10^6$ 。	先考虑选出并排列坐在一起的 $k$ 对情侣，方案数为 $\binom{n}{k}^2\times k!\times 2^k$ ，其中 $\binom{n}{k}^2$ 为选出 $k$ 对情侣并选出 $k$ 行椅子的方案数， $k!$ 为 $k$ 对情侣排列顺序的方案数， $2^k$ 为每行情侣排列的方案数。设 $f_i$ 为 $i$ 对情侣都不坐在一排里的方案数（不考虑顺序），则最终答案为 $f_i\times 2^{n-k}\times(n-k)!\times\binom{n}{k}^2\times k!\times 2^k$ 。再考虑计算 $f_i$ ，在这 $i$ 对情侣中任选一对，设为 $(a,b)$ 。设 $a$ 与 $c$ 坐在一起，且 $c$ 的情侣为 $d$ ，则可分类讨论为两种情况：第一种是 $b$ 和 $d$ 坐在一起，则方案数为剩余 $i-2$ 对情侣不坐一起的情况数，即 $f_{i-2}$ ；第二种情况是 $b$ 和 $d$ 不坐一起，那么就可以把 $b$ 和 $d$ 也看作一对不能坐一起的情侣，情况数就是剩余 $i-2$ 对情侣和 $b$ 和 $d$ 这对“情侣“排列的方案数，即 $f_{i-1}$ 。则 $f_i=2(n-1)\times(f_{i-1}+f_{i-2})$ ，其中 $2(n-1)$ 为选出 $c$ 的方案数。则可以用递推预处理出 $f$ 数组和组合数、2 的幂等，然后 $O(1)$ 处理询问。	$f(0)=1,f(1)=0$
28	AT1983	有 n 个数对 $(a_i, b_i)$ ，求出 $\sum_{i=1}^{n} \sum_{j=i+1}^{n}\binom{a_{i}+b_{i}+a_{j}+b_{j}} {a_{i}+a_{j}}$ 。 $a_i,b_i\le 2000, n\le 200000$ 。	考虑 $\binom{a_{i}+b_{i}+a_{j}+b_{j}} {a_{i}+a_{j}}$ 的几何意义，为直角坐标系中点 $(-a_i,-b_i)$ 到点 $(a_j,b_j)$ 的方案数。则答案为 $\sum_{i=1}^n\sum_{j=i+1}^ndis((-a_i,-b_i),(a_j,b_j))$ 。直接递推即可，复杂度 $O(值域^2)$ 。
29	luoguP2627	给定 $n$ 个非负整数，选择其中若干个数，但不能有超过 $k$ 个连续的数字被选择。最大化选出的数字的和。 $k\le n\le 10^5$	设 $dp[i]$ 表示前 $i$ 个数选择的最大值，考虑上一个 0 点的位置一定在 $i-k$ 到 $i$ 之间，否则就会有一段大于 0. 于是转移方程为 $dp[i] = \max_{j=i-k-1}^{i-1}(dp[j]+sum(j+2, i))$ ，变形得 $dp[i] =\\ \max_{j=i-k-1}^{i-1}(dp[j]-sum(1,j+1)+sum(1, i))$ ，单调队列优化即可，时间复杂度 $O(nk)$ 。	要善于将题目的模型转化。
30	CF833B	将一个长度为 $n$ 的序列 $a$ ，让你将其分为 $k$ 段，使得总价值最大。一段区间的价值表示为区间内不同数字的个数。 $n≤35000,k≤50$	建 $k$ 棵线段树，设第 $i$ 棵的第 $j$ 项为 $t[i][j]$ 。从前往后遍历数组，遍历到第 $p$ 位时， $t[i][j]$ 表示将前 $p$ 个数划分成 $i$ 段，且第 $i$ 段的开头是第 $j$ 个数的最大答案，则此时可以更新 $t[i][p]$ 为 $\max_{j=1}^p(t[i - 1][j])$ 。同时，考虑向后移动一位时线段树的更新，设 $pre[a_i]$ 表示上一个等于 $a_i$ 的数的位置，则从 $i - 1$ 移动到 $i$ 时，新加入的数会对最后一个区间的开头在 $pre[a_i]+1\sim i$ 的答案产生贡献，所以要把 $t[1\sim k][pre[a_i]+1\sim i]$ 都加一。时间复杂度 $O(kn\log n)$ .	此类线段树扫描的套路比较常见。
31	luoguP3400	给一个 $n \times m$ 的 01 矩阵，求有多少个全为 0 的子矩阵。 $n, m\le 3000$ .	考虑以点 $(x, y)$ 为左上端点时，有多少个全 0 子矩阵。考虑第 $y$ 列向右的每一列 $j$ ，设 $t[j]$ 表示满足 $(x,y)$ 为左上角且 $(p,j)$ 为右下角的子矩阵是全 0 矩阵的所有点 $(p,j)$ 中， $p$ 的最大值。容易发现，这些数向右是单调递减的。那么对于某一行，从右到左遍历，使用单调栈维护 $t$ 数组，并从右边的点继承答案，在维护 $t$ 数组时减掉不合法的答案即可。	单调栈常见做法。
32	luoguP2827	有 $n$ 只数，定义一次操作为选出最大的数 $x$ ，加上两个数 $\lfloor px\rfloor$ 和 $x-\lfloor px \rfloor$ ，其中 $p$ 是给定的常数， $0\le p\le 1$ 。并删去 $x$ ，把其他所有数加上给定的非负常数 $q$ 。问 $m$ 次操作中每次被切断的蚯蚓的长度，和最后 $n+m$ 只蚯蚓的长度。 $n\le 10^5，m \leq 7 \times 10^6$ 。	考虑单调性，每次操作的数一定是单调不增的，故 $\lfloor px\rfloor$ 与 $x-\lfloor px \rfloor$ 相对之前操作中相应的数也是单调不增的。建三个队列，第一个按从大到小的顺序存原数的大小，第二个队列每次操作后向队尾插入 $\lfloor px\rfloor$ ，第三个队列每次操作后向对位插入 $x-\lfloor px \rfloor$ ，容易发现，这三个队列内部的元素都是单调递增的，故每次操作的数只可能是这三个队列队首中的最大值，并且向其他数加上 $q$ 的操作不影响单调性。故按照题意模拟即可。	注意单调性。
33	luoguP3287	给一个长度为 $n$ 的序列 $a$ ，最多执行 $k$ 次将 $[l,r]$ 区间加一的操作，问操作后的最长不下降子序列最长是多少。 $n \le 10000,k \le 500$ .	显然，每次操作以第 $n$ 个数为右端点一定是最优的，于是考虑 dp，设 $f_{i,j}$ 表示有 $j$ 次操作以 $[i,n]$ 中的数为左端点的情况下，以第 $i$ 个数为结尾的最长不下降子序列的长度。那么转移方程式为 $f_{i,j}=\max\limits_{1\le p<i,1\le q\le j,a_p+q\le a_i+j}(f_{p,q})$ ，可以使用二维树状数组优化， $t_{i,j}=\max\limits_{1\le p\le n,a_p+i=j} (f_{p,i})$ 。
34	luoguP2467	给定 $n$ ，求有多少个 $1\sim n$ 的排列满足 $\forall i\in[2,n-1]$ ， $a_{i+1},a_{i-1}< a_i$ 或 $a_{i+1},a_{i-1}> a_i$ 。	设 $f_{i}$ 表示由 $1\sim i$ 组成的摆动序列，且第一位是波峰的方案数，将这 $i$ 个不同的数映射到 $1\sim n$ ，考虑 $i$ 插入的位置，有 $f_{i}=\sum_{j\bmod 2=0}^{j\le i-1} f_{j}\times f_{i-j-1}\times\binom{i-1}{j}$ ，表示 $i$ 这个数插在第 $j+1$ 位，显然， $i$ 是波峰。 $\binom{i-1}{j}$ 表示将其他数分配到 $i$ 前和 $i$ 后的方案数，将前面的 $j$ 个数离散化到 $1\sim j$ ，则排列方案数为 $f_j$ ，后面同理。同时要保证第 $j$ 个数是波谷，故要保证 $j\bmod 2=0$ 。同时，显然第一位是波峰与第一位是波谷的方案数相同，故答案为 $2\times f_n$ 。
35	luoguP3616	给一个长度为 $n$ 的序列 $a$ ，有两个操作，第一个是单点修改，第二个是询问将序列有多少个极大的子序列，满足这个子序列的所有数大于等于 $x$ 。 $n\le 2\times 10^5$ 。	考虑计算每个极大子序列的端点，则端点 $i$ 满足 $\begin{cases}\max(a_{i-1},a_i)\ge x\\\min(a_{i-1},a_i)< x\end{cases}$ 。则这样的端点的个数为 $\max \ge x$ 的个数 $-$ $\min\ge x$ 的个数。使用权值树状数组记录即可。
36	CF526F	给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。求有多少个 $k\times k$ 的子棋盘中恰好有 $k$ 个棋子。 $n\le 3\times 10^5$ 。	考虑将问题转化成序列上，将 $n$ 个点的按横坐标从小到大的顺序排列写下纵坐标，组成一个序列 $a$ 。则答案为满足 $\max_{i=l}^r (a_i)-\min_{i=l}^r(a_i)=r-l+1$ 的区间的个数。从左往右扫，用单调栈维护每个后缀区间的 $\min$ 和 $\max$ ，扫到新的数时弹栈并线段树区间修改即可。
37	P2824	给一个 $1\sim n$ 的排列， $m$ 个操作，每个操作为把 $[l,r]$ 升序或降序排序，最后询问第 $q$ 个位置上的数是多少。 $n,m\le10^5$ 。	考虑如何判断排序后序列的第 $q$ 项与 $x$ 的大小关系，把排序前的序列所有大于等于 $x$ 的数标 1，小于 $x$ 的数标 0。则操作为对 01 串排序，使用线段树维护，单次排序复杂度为 $\log(n)$ 。则排序后判断第 $q$ 项是 0 还是 1 即可。二分 $x$ ，找到最小的 $x$ ，使得排序后数列第 $q$ 项为 1，则第 $q$ 项为 $x$ 。时间复杂度 $\mathcal{O}(m\times \log^2 n)$ 。	妙啊
38	P4597	给定一个序列，每次操作可以把某个数 +1 或 -1。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。 $n\le 5 * 10^5$ 。	考虑贪心，按次序遍历每个元素，并将决策好的元素放入大根堆中。每次对于新遍历到的数，取出堆顶元素，若堆顶元素小于等于该数，则一定合法，将该数放入堆中。若堆顶元素大于该数，则要将堆顶元素与该数都变成这两个数之间的同一个数一定是更优的，且代价相等。我们暂时不决策这两个数具体变成多少，但显然变成这两个数之间的同一个数一定能保证合法性。将这两个数能变成的最小的数（即当前数）放入堆中，表示若堆顶为该元素，则该元素需要第二次被修改。时间复杂度 $O(n\log n)$ 。	神仙贪心，但貌似可以用 dp 式子的凹凸性来做，代码与贪心差不多。
39	AT2567	有一个序列 $a$ ，要给序列中的每个元素一种颜色：红/绿/蓝。有 $m$ 条限制 $(l,r,x)$ ，表示格子 $l\sim r$ 中颜色的种数要恰好为 $x$ ，问可行的方案数。 $n,m\le300$	设 $f_{i,j,k}$ 表示处理到第 $i$ 个，与当前位置不同的两个颜色最后出现的位置分别是 $j$ 和 $k$ 时的方案数，显然，容易判断不符合限制的情况。转移时分类讨论新的颜色即可。	巧妙的状态设计

updated on 2021/1/26⌚️