考试总结
考试
成功垫底
难 T
度 1
倒 磕
序 了
自 一
闭 万
场 年
T1
我不会的题。
求有向图可达点数量实际上不存在低于 \(O(n^2)\)
的算法，所以得考虑给定图的性质。
显然给定的图是个平面图。
然后定义一个东边的点是有效的，当且仅当它能到一个西边的点，一遍 \(BFS\) 可以把有效点找出来。
然后对于所有点，它能到达的有效点集合一定是一段区间，考虑反证，对于某个点，如果被夹在中间的一个有效点到不了，那么如果其它点可以到就只能穿过一些边，这是不可能的。
写拓扑排序是非常傻逼的行为，直接对每个有效点拓展，算出西边每个点到达有效点坐标的最值就行。
T2
会但是考场写不出来的题。
Method1
考虑枚举排列计算 MST，本质上需要求前 \(i\) 个边能将图联通的排列一共有多少个。
可以考虑计算出任选 \(i\)
条边后图联通的选法有多少种，然后通过容斥计算出恰 \(i\) 个边联通的排列个数。
可以记录联通性动态规划搞定。
复杂度 \(O(bell(n)\times m^2)\)
Method2
枚举联通往往可以弄成二进制枚举联通状态，逆序考虑联通块的构成方式，发现求任
\(i\)
条边联通的方案数，转移的时候是不强调顺序的，所以枚举子集会导致重复，不妨直接考虑顺序，计算原问题的答案。
设 \(dp[mask][i]\) 表示只考虑 \(mask\) 子图，答案为 \(i\)
的排列个数，转移就可以枚举子集，从上一条边的状态转移，需要进行一些排列组合，复杂度
\(3^n\times m^4\)。
Method3
高达 \(m^4\)
的多项式复杂度还是太逊了，考虑继续优化。
其实我们很想直接任选 \(k\)
条边，然后排除掉不合法的情况，这样能够求出答案至多为 \(k\) 的个数，容斥之后就没有问题了。
所以考虑如何排除不合法的情况，就是边选好了但是图没联通，这个时候我们就可以枚举一个小连通块，可以用若干边连接内部，若干外部边任选，就是一类不合法的情况，但是这样会算重，我们可以钦定枚举的联通块和
\(1\) 联通。
复杂度 \(O(3^n\times m^2)\)。
总结
这一类图论上的二进制枚举问题，往往可以先从枚举联通块入手，再考虑子图的答案，最后综合运用容斥等计数手段，得到复杂度优秀的做法。
T3
非常有意思的题
Method1
考场上的想法，主要受到某道题的启发。
只考虑最大值，\(O(n)\)
可以扫一遍，单调栈维护当前每一段的最大值与和。
很浪费，因为我们本质上对每个右端点都求了合法左端点区间的答案，考虑能不能复用右端点的答案。
其中一种方式是分块，考虑一段右端点到每个左端点的答案的前缀和，然后查询就可以被拆分了。
Method2
为什么我们会分块，回到那道题，我们有办法通过一些预处理结果得到两个区间并的答案，但是无法快速合并两个预处理结果，所以我们分块，只需要预处理一次。
但是利用随机数的性质我们发现其实可以快速合并预处理的结果。
将问题转化为两种基本形式，相离和重合，这是容易的。
先考虑相离怎么做
考虑利用随机的性质，发现任意一段区间，其有效的贡献个数为 \(\ln\)
个，即从区间首或位开始的最长连续上升序列，然后枚举两个 \(\ln\) 的区间合并，搞定相离的情况，视实现是
\(\ln^2\) 或者 \(\ln\)，后者常数较大可能并不优秀。
然后是重合，能不能合并两个重合的区间得到新的区间，可以！转化为一个相离和两个更小的重合问题，因为数量是
\(\ln\)
的，所以合并预处理信息是可能的。
但是，为啥要用线段树，因为没有逆元！但是这道题是可以将一个大重合问题减去一个相离和一个小重合问题得到另一个小重合问题的，所以对大重合问题做前缀和即可。
Method3
对于二维统计问题，常常可以考虑固定预处理其中一维，尝试快速通过预处理结果查询第二维。
这道题中，我们可以预处理每个点作为第二个区间中的点时，在第一个区间中每个点的答案。但实际上这个数据量是
\(O(n)\)
的，没有办法快速搞定，那不妨考虑只处理其前缀和与后缀和，看看是否能够压缩信息。
一些不太正确的思考
考虑单个右端点对一段区间查询，考虑区间最大值，如果落在自身或者空区间，那么答案容易计算，如果落在左区间
考虑它前面第一个比它大的位置，如果不存在或者在空区间，那么答案可以通过前缀和快速计算
正确的思考
考虑区间相离的基本情况。由于单点我们都没有办法做，所以不太能直接搞，但是容易发现区间重合时可以搞定的，考虑区间最大值的位置，跨过它的答案容易统计，不跨过它，我们处理了每个点为右端点和左端点时答案的前缀和，那么由于不跨过最大值时，在最大值另一侧的答案完全不受同侧的影响，所以前后缀和减去最大值所在位置的前后缀和就可以得到重合的答案。
有了重合，我们可以解决区间相邻的答案，定义求两个区间答案的运算是
\(\oplus\)，那么对于两个相邻区间有\((a+b)\oplus(a+b)=a\oplus a+b\oplus b+a\oplus
b\)。
我们能搞定的是 \(a\oplus
a\)，对于相离的区间，转化为相邻区间做 \(a\oplus c = (a+b+c)\oplus (a+b+c)-a\oplus a-b
\oplus b-c\oplus c - a\oplus b -b\oplus c\)。
因而搞定了所有情况。
实现
如果直接这么写，写出来很丑，实际上由更优雅的写法，考虑差分区间，如果左端点大于右端点那么没有问题，\([l_1,r_2]\) 全部统计，那么会有重复 \([l_1,l_2-1]\)
这一段区间就是被重复统计的，当然这个区间可以不存在，需要减去，然后再减去
\([r_1+1,r_2]\)
这段有可能不存在的区间的答案，最后加上可能被算重的 \([r_1+1,l_2-1]\) 区间。
反正这个思想挺神的，看上去有问题但确实是对的，比直接写优雅很多。
Method4
思路
考虑每个数对答案的贡献，弄出左右两边第一个比它大的数，那么这些区间以内跨过它的，都在它的贡献范围内，左右端点可以弄成
\(x,y\) 坐标，这是一个矩阵加。
考虑查询，本质上也是在查询 \(x,y\)
坐标各在一段区间内的答案。
于是就是一个修改全部在查询前面的矩阵加矩阵查问题，可以用树状数组解决。
实现
说着轻松，但其实还没写过这种东西，简单思考下怎么做。
首先区间查被差分成 \(\ge x,\ge y\)
的区域加一，区间查变成 \(\le x,\le y\)
的区域查询，还是回到了二维偏序问题。
点是 \((x_1,y_1),(x_2,y_2)\)，条件是
\(x_2\ge x_1\wedge y_2\ge y_1\)，贡献是
\((x_2-x_1)\times(y_2-y_1)\)，是不是很阴间？所以多维护点东西，一个
\(cnt\) 树状数组搞定 \(x_2\times y_2\)，两个分别加 \(x,y\) 来搞定 \(x_2\times y_1,x_1\times y_2\)
，再来一个统计 \(xy\)
搞定剩下那一项，其实还算好写。
T4
考虑刻画出图的形态，它是一个基环内向树森林。
容易发现只用将 \(1\)
和其它点连边，然后有些点是必须连的，入度为 \(0\) 的，编号非 \(1\) 的点必须连。
先不考虑环，这样连了之后，又有一些点是必连的，而且容易发现连这些点一定最优，所以继续连。
连到不是环上的所有点都连上为止。
现在还剩一些环，环上一些点是合法的，需要用长度为 \(k-1\) 的线段取覆盖环，让所有点合法。
容易发现确定某个起点之后就能贪心了，考虑连续的 \(k+1\)
个不合法点，枚举每一个并确定最少数量，然后取 \(\min\) 就行，因为这连续的 \(k+1\) 个不合法点一定有一个是起点。
