1014T3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>
void read(T &x){
	x=0;char ch=getchar();int f=1;
	while((ch<'0'||ch>'9')&&ch!=45)ch=getchar();
	if(ch==45)f=-1,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
	x*=f;
}
template<typename T1,typename T2>void cmax(T1 &x,const T2 &y){if(y>x)x=y;}
template<typename T1,typename T2>void cmin(T1 &x,const T2 &y){if(y<x)x=y;}
const int N=1e3+10,mod=1e9+7,M=1e3+10;
int i,j,k,m,n,s,t;
int a[N],c[N],sum[N],dis[N],dp[N];
int quick(int a,int s,int ret=1){
	while(s){
		if(s&1)ret=1ll*ret*a%mod;
		a=1ll*a*a%mod;s>>=1;
	}
	return ret;
}
int iv(int x){
	return quick(x,mod-2);
}
signed main(){
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);
//	read(n),read(m),cout<<n<<' '<<m<<endl;
	read(n),read(m);
	for(i=1;i<n;i++)read(a[i]),sum[i]=sum[i-1]+a[i];
	for(i=1;i<=n;i++)read(c[i]);
	int sm=1ll*a[1]*c[1]%mod,sm2=0;dis[1]=0;
	for(i=2;i<=n;i++){
		dis[i]=(1ll*sm*quick(sum[i-1],mod-2)+c[i])%mod;
		sm=(sm+1ll*(dis[i]+c[i])*a[i])%mod;
		dp[i]=(1ll*a[i-1]*(c[i]+c[i-1])%mod*iv(sum[i-1])+1ll*iv(sum[i-1])*sm2)%mod;
		sm2=(sm2+1ll*dp[i-1]*a[i-1]%mod)%mod;
	}
	for(i=1;i<=m;i++){
		int u,v;read(u),read(v);
		if(u==v){
			puts("0");
			continue;
		}
		if(u>v)swap(u,v);
		printf("%lld\n",(dis[u]+dis[v]-2ll*dp[u+1]+mod*2)%mod);
	}
	return 0;
}

平衡树

既然标题敢写平衡树，那就需要来谈谈平衡树本身，而不仅仅是实现它的方法。

平衡树本身

平衡树是一颗二叉搜索树，每个节点权值大于左子树所有节点，小于右子树所有节点。

和线段树相比，它是一种动态结构，适合维护结构动态变化的信息，比如需要支持插入和删除以及翻转的序列，也可以用来维护一棵树（LCT）

和块状链表相比，它只能处理能够快速合并的信息，但是复杂度有所降低。

实现

Splay

已经很熟悉的方式，不再多说，不过可以多嘴提一句势能分析。

势能分析原理

定义势能函数 $F(S)$ 表示状态 $S$ 的势能，定义操作代价 $p_i=c_i+F(S’)-F(S)$，其中 $c_i$ 表示操作时间。

求解 $\sum p_i=\sum c_i + F(S_m)-F(S_0)$

移项得到 $\sum c_i=\sum p_i+F(S_0)-F(S_m)$

一般来说，$c_i$ 会比较奇怪，但是通过 $F$ 函数的变化值可以去抵消掉这个奇怪的值得到优雅的 $p_i$，然后一般来说最后的复杂度和 $\sum p_i,F(S)$ 同阶

分析 Splay 的复杂度和单旋的复杂度

定义势能函数，定义单点势能 $w(u)=\log_2(size_u)$， $F(S)=\sum\limits_{u\in S} w(u)=O(n\log n)$。

旋转点为 $x$，父亲为 $f$，祖父为 $g$。

左旋代价

注意到 $size_{x’}=size_{fa}$。

$1+w(x’)+w(fa’)-w(x)-w(fa)\le 1+w(fa)-w(x)\le 1+w(x’)-w(x)$

双左旋代价

$1+w(x’)+w(f’)+w(g’)-w(x)-w(f)-w(g)\le 1+w(f’)+w(g’)-w(x)-w(f)$

$w(f)\ge w(x),w(f’)\le w(x’)$

$w(x’)-w(x)\ge w(f’)-w(f)$

$1+w(f’)+w(g’)-w(x)-w(f) \le 1+ w(x’)+w(g’)-2w(x)$

若 $w(x’)-w(x) \ge 1$

则 $ 1+ w(x’)+w(g’)-2w(x)\le3(w(x’)-w(x))$

否则因为先旋的 $f$，所以 $g’$ 下的点不包括 $x$ 中的点，所以有 $size_x\ge size_{g’}$，因此 $w(x’)-w(g’) \ge1$

得到 $1+ w(x’)+w(g’)-2w(x)\le 2(w(x’)-w(x))$

综上 $1+w(x’)+w(f’)+w(g’)-w(x)-w(f)-w(g)\le 3(w(x’)-w(x))$

左右旋代价

$1+w(x’)+w(f’)+w(g’)\le 1+w(f’)+w(g’)-w(x)-w(f)\le 1+w(f’)+w(g’)-2w(x)$

由于最终 $f’,g’$ 都是 $x’$ 的儿子，所以 $1+w(f’)+w(g’)-2w(x)\le2w(x’)-2w(x)$

所以 $1+w(x’)+w(f’)+w(g’)\le 2w(x’)-2w(x)$

双旋代价

注意到只会进行一次 zig 操作，所以可以忽视 zig 的那个 1，其余代价直接相加，得到 $3$，因此 $p_i=O(\log n)$。

观察到一次 Splay 操作的每个子操作可以弄成 $3$ ，然后相加抵消掉得到 $3+3w(x’)-3w(x)$，是 $O(n\log n)$ 级别，势能变化量为 $O(n\log n)$ 级别，故时间为 $O(n\log n)$ 级别。

单旋代价

单旋代价为左旋代价的和，每次 Splay 操作数为 $O(n)$，故单旋的复杂度上界是 $O(n^2)$

总结

以上势能分析对 Splay 操作的要求是非常严格的，因此如果在查询中没有进行 Splay 操作，那么操作时间无法导致对应的势能变化，最后出现不正确的复杂度。

Treap

数据随机的情况下，一个堆（每个节点的权值均大于它全部后代的权值）的期望高度是 $\log n$ 的，通过左右旋保证堆的性质，可以保证 Treap 的复杂度，左旋右旋和 Splay 完全相同。

FHQ_Treap

元素 val：需要维护的值。

权值 height：随机的，用于保持堆性质的值。

核心操作是 Merge 和 Split。

过程中需要时刻保证满足堆的性质

merge(u,v)

合并两个子树 u,v ，保证 u 中元素全部小于 v，返回根。

和线段树合并非常像。

1
2
3
4
5
6
7
8
9
10
11

int merge(int u,int v){
    if(!u||!v)return u^v;
    if(height[u]>height[v]){
        son[u][1]=merge(son[u][1],v);
        push_up(u);return u;
    }
    else{
        son[v][0]=merge(u,son[v][0]);
        push_up(v);return v;
    }
}

Split(u,x,y,k)

按照元素值小于等于 $k$ 划分为两颗树，较小的那棵树树根为 $x$，较大的那个树根为 $y$。

细看这个函数其实相当妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void split(int u,int &x,int &y,int k){
	if(u==0){
    	x=y=0;
        return ;
    }
    if(val<=k){
        x=u;
        split(son[u][1],son[u][1],y,k);
    }
    else{
		y=u;
        split(son[u][0],x,son[u][0],k)
    }
    push_up(u);
}

其实也可以按照子树大小划分，用于文艺平衡树。

其它操作

• get_l(element)：按照小于 element 划分，然后返回较小那边的大小，重新 merge
• get_element(rank)：与 splay 没有差异。
• insert(element)：按照小于等于它划分，然后 merge 两遍。
• erase(element)：按照小于等于它划分，然后按小于它划分，然后把划分得到的两个儿子 Merge 起来再 merge，然后再 merge，这样是能够处理元素相同节点的。
• get_prev(element)：按照小于它划分，用 get_element()
• get_next(element)：按照小于等于它划分，用 get_element()
• 合并的时候也可以按概率选择父亲，$sz$ 较大的权重较大，期望复杂度可以证明是 $O(n\log n)$ 的。

某些实验

采用佳老师的神奇插入删除方式：

可以发现正常的插入方式需要 $14S$，$18S$ 是按子树大小概率合并，加上佳老师优化后变为 $10S$，有一定改进。

如果直接实现 get_rank 系列函数可以更快，但是没什么必要了。

手写 get_rank 系列后耗时为 $9S$，手写 get_rank 系列，采用正常插入方式，用时 $12S$。

全实现的 Splay 需要 11S。

vector

一般来说，如果数据范围 $\le 5\times 10^4$，或者时限比较宽松，可以用 vector 实现平衡树。

pb_ds

自带平衡树，一般用于操作比较简单的情况，如果需要打 Tag 之类的，重写 node_update 不如手写一颗。

可持久化平衡树

可持久化平衡树一般用于解决强制在线的历史版本问题，对于非强制在线问题，其实可以离线到树上实现一个支持撤销的平衡树。

对于强制在线问题，基本思路都是复制修改过的路径，复用没有修改过的路径。

可以发现其实任何一个版本创建之后就是静态的，所以可持久化数据结构的核心是：任何时刻访问先前的版本，都能得到正确的结果，任何修改不能影响到先前的版本。

Splay 实现

其它操作不变，Splay 时复制涉及的所有点作为一个新版本。

但是，这玩意的复杂度有问题，Splay 的复杂度保证在于对操作进行势能分析，引入可持久化后，势能的变化量会变成 $n^2\log n$ ,因此复杂度会退化。

由于实际应用中，很少存在只能用 Splay 的情况，因此没有必要深究 Splay 的可持久化。

FHQ-Treap 实现

听说这种实现有点问题，但是实际中并没有出现过问题，如果觉得不太行可以换下面那种奇怪的实现。

Split

由于操作都是从 Split 开始的，所以每次 Split 前都复制一个版本出来，具体的，像可持久化线段树一样把不变的儿子共用，改变的儿子复制。

Split 的路径上所有点的信息都被改变了，需要复制一遍得到新的，这样原先版本的所有节点不会有任何变化。

大致刻画以下 Split 中被修改的点，它呈一条链

Merge

Merge 过程中的复制不是必须的，原因是每个被修改的点都是被新建出来的点，这个证明可以考虑归纳，合并深度为 $1$ 的节点时，两点显然都是被复制的，不影响原树，合并任何被复制的两个节点时，较小的那个的右儿子，较大的那个的左儿子要么不存在，要么是被复制的，因为在被复制的节点处，链一定会向下延申。

因此合并时可以不用新建节点。

神奇方法

佳老师有一个神奇写法，理论常数为 $\frac{1}{2}$，具体的，插入和删除时先找到第一个 key 小于当前点 key 的点，然后这个点一定是被插入/删除点的儿子，然后把只对这个儿子做一遍 Split，并把树分到插入点的两个儿子上面去，这个思路同样可以用于一般 FHQ-Treap，运用在普通平衡树中，实际效率改进因子在 $0.33$ 左右。

一般来说删除就正常搞，不然容易写错。

考试的时候如果不卡常就写正常写法，减少可能的错误。

一般来说，空间得开 50 倍。

注：效率改进因子，若效率改进因子为 $x$，原时间 $t$，则改进后时间为 $\frac{t}{1+x}$。

Treap 实现

由于期望树高是 $\log n$ 的，所以直接复制所有已经被修改的点的信息

某种奇怪的实现

类似 FHQ-Treap，但是 Merge 的时候按照子树大小作为权重，随机选一个做父亲，这样的复杂度是有保证的。

文艺平衡树

文艺平衡树是一类用于维护区间的平衡树，它和正常的平衡树类似，但是用树的结构来决定一个元素的大小，适合用来维护结构动态变化的序列。

一般用 Splay 和 FHQ-Treap 实现。

FHQ-Treap 实现时需要支持按 size 划分。

动态树

一般用 Splay 实现，复杂度 $O(n\log n)$，进行实链剖分，每条实链被一颗 Splay 维护，思想和文艺平衡树类似，用平衡树树的结构表明了原树节点中的的高度关系。

核心操作是 access 和 make_root。

access(x)

使得 $x$ 到树根上的路径成为一条实链，断开 $x$ 和它实儿子的连接，并让 $x$ 成为该 Splay 的根。

make_root(x)

使得 $x$ 成为树根，操作方式是先 accsess，然后翻转这条实链，使得 $x$ 的深度最小。

由于虚儿子认父不认子，所以整个结构都没有问题。

实现

一般采用 Splay，FHQ-Treap 也没有问题。

但是不能用一般 Treap，因为一般 Treap 对树结构的要求决定了它无法进行旋转操作。

FHQ-Treap 的复杂度很难证明是 $n\log n$，但是可以保证上界为 $O(n\log n^2)$，Splay 的复杂度则为 $O(n\log n)$

似乎有 $O(n\log n)$ 的 FHQ-Treap 实现。

考试总结

考试

发挥一般

T1

很趣味的题，考虑计算答案的过程，首先从某个点开始，遇到

T2

平衡树模板，不做评价，权当练习使用 pb_ds。

其实有平衡树之外的多种解法。

值域分块

对这个东西其实一直不熟悉，如果序列分块不容易解决或者复杂度多一个 $\log$，那么考虑对值域分块，记录和每块数值有关的信息。

$O(1)$ 改可以只改对应数值块和自身的数据，$O(1)$ 查可以对块和块内维护前缀信息或者其它预处理信息。

树状数组上二分

写过若干次，但不熟练。

以前缀和树状数组为例，它每个节点 $x$ 维护的信息是 $(x-lowbit(x),x]$ 区间的全部信息。

更新时一直 +lowbit，保证了恰好能够维护这些信息。

所以如何二分也比较明晰了。

1
2
3
4
5
6
7
8
9

int now=0,sum=0;
for(int i=18;i>=0;i--){
    // 现在认为在 (now,now+1<<i+1]
	if(1<<i|now<=n&&sum+c[now|1<<i]<k){//在 (now|1<<i,now|1<<i+1]
        now |= 1<<i;
        sum += c[now];
    }
}
int res = now + 1;

T3

有些价值的题，”优化状压DP” 还是有一些话题可谈。

T4

李超树模板题，类似 CDQ 分治的思路或者平衡树维护凸包其实很趣味，但是没有什么启发意义。

等有时间了写一份斜率优化的总结。

20221011 考试总结

考试

T1

假的可持久化题，弄到树上做撤销就行。

其实写可持久化 FHQ-Treap 更容易

参考 关于平衡树

还可以用块状链表搞定。

T2

树套树模板题，但是有一些不同的思考方式。

我采用了线段树套值域线段树，但是需要同时二分多个主席树，不够优雅。

值域树套位置树

一般来说，位置树套值域树更加常见，但如果有些涉及到二分的操作，也许把它们反过来会更加容易，因为反过来之后就可以在数据结构上二分，减少一个 $\log$。

其实位置树套值域树也可以在数据结构上二分，只是实现起来相对麻烦一些。

可以采用值域线段树套平衡树。

这个时候 FHQ-Treap 的优势就体现出来了，很简单的可以查到 $[l,r]$ 区间内数的个数。

莫队和值域分块

带修莫队可以处理单点改区间查的问题，修改一共 $O(n^{\frac{5}{3}})$ 次，查询 $O(n)$ 次，使用 $O(\sqrt n)-O(1)$ 的值域分块即可处理问题。

题意

• 给你一棵有根树，定义一个点合法当且仅当它到根上的点全为黑色，否则不合法。

• 最开始所有点为白色，每次选一个不合法的点涂黑，每个点可以被涂黑多次。

• 问所有点被涂黑的期望次数

思考1

这次想题引爆了某人概率论基础不扎实的炸弹。

考虑每个点被涂黑的顺序，是一个排列，取到每种排列的概率相同。

考虑使用全期望公式计算，先考虑固定一个排列时的答案。

先假设只有 $3$ 个点，且顺序为 $3,2,1$，也就是赠券收集问题。

选第一个点的期望次数为 $1$，因为所有满足这个排列的样本点都是以 $3$ 开头，选第二个点，期望次数是多少，或者说，选出第一个点后，下一个被选择的点，在顺序为 $3,2,1$ 的前提下，是 $2$ 的概率是多少？

$\frac{1}{2}$ 的来历

选第二个点时，可以选的点有 $3,2$，选择每个点的概率相同，所以概率为 $\frac{1}{2}$

虽然原本每个点概率时相同的，但是我们求的时条件概率，条件概率的样本空间已经被改变了，所以选择每个点的概率不再相同。

$\frac{2}{3}$ 的来历

考虑概率的定义，$P=\frac{事件大小}{样本空间大小}$，考虑该条件的集合和事件与条件的交集，因为此题样本空间无限大，所以考虑将一个无限长序列映射到我们的样本空间，容易发现这样的映射不会改变概率函数。

设 $k$ 为已经选取的数的个数，$n$ 为数的总数。

这是在正确的样本空间算出的正确结果。

从 Beyes 公式考虑：

神奇吧？

贝叶斯公式连接了条件概率和原问题的样本空间。

总结

样本空间无限大的时候要小心，不能轻易认为两个元素等价，因为此时 $\infty \ne \infty$。

用贝叶斯公式好好算算吧。

草率的断言概率为 $\frac{1}{2}$，很大一部分原因都是认为两个正无穷时相等的。

有了这个东西就可以愉快的推狮子 NTT 了。

思考2

其实这种题还有一种更加普遍的做法，期望线性性，考虑每个点被选的次数，相加可以得到最终答案。

期望线性性来源于期望的定义，一个随机变量是一个函数，定义域为样本空间，值域为 $\R$，随机变量的期望为其密度函数积分的收敛值。

因此，无论两个随机变量是否独立，它们的期望都是可加的。

感性理解的话，两个随机变量之和的期望等于这样一个随机变量的期望：每个样本点的取值为两个随机变量在该样本点的取值之和，期望可以粗略理解为随机变量在样本空间每个点的平均值，因此随机变量的期望可加。

所以可以考虑每个点被选的期望次数，如果选到了不在这个点到根路径上的点，那么我们忽略这一次选择，这样的忽略不会影响这个点被选的期望次数，然后问题变成了一条链上的最后一个点被选择的期望次数。

注意，我们只关心这个点被选择的期望次数。

考虑怎么求这玩意，因为整个过程在点到根路径上所有点被选择之后才会结束，所以像赠券收集问题一样倒序。假设有 $k$ 个点还没选，总共 $n$ 个点，其中 $w$ 个点可以选，那么转移答案是 $dp[k]=\frac{k}{w}dp[k+1]+\frac{w-k}{w}dp[k]+\frac{1}{w}$

移项得到 $dp[k]=dp[k+1]+\frac{1}{k}$，实际上和 $w$ 无关，所以就很好算了。

官方题解的说法是如果考虑可以选已经 good 的点，最终答案不变，我理解不了这个过程。

upd：其实现在也可以理解了，因为如果选了已经 good 的点，那么再选一次就行了。

有几个比较重要的地方，一是忽略和答案绝对无关的操作，二是考虑计算过程。

事件和条件

以下概率均为古典概率模型，暂时不讨论几何概型。

这两个东西是我自己定义的，算概率之前，必须搞清楚事件和条件的区别，下面提两个搞不清楚事件和条件导致的问题。

三门问题

• 有三个门，一个门后面有汽车，另外两个门后面是山羊。

• 你可以先选择一个门，之后主持人打开一个门，门后是山羊

• 问此时两个门后有汽车的概率是多少

思考方式一（错误）

每个门后有山羊的概率是相等的，打开一个门不会影响另外两个门的状态，故另外两个门后有山羊的概率是相等的，故答案为 $50\%$

思考方式二（不严谨）

另外两个门有山羊的概率是 $\frac{2}{3}$，排除一个选项，所以选择的门后有山羊的概率是 $\frac{1}{3}$，另一个门的概率为 $\frac{2}{3}$。

不知道叫什么名字的问题

有个酒鬼，每天各有 $30\%$ 的概率去 $A,B,C$ 三个酒吧，还有 $10\%$ 的概率呆在家。

一个警察要找他，警察已经找了 $A,B$ 酒吧，都没找到他，问在 $C$ 酒吧找到酒鬼的概率。

思考方式一（错误）

在酒吧的概率是 $90\%$，$A,B$ 都没找到，说明一定在 $C$，所以在 $C$ 找到酒鬼的概率是 $90\%$。

这个思路和上一个问题思考方式二类似，但是是错误的，因此说它不严谨。

思考方式二（不严谨）

已知不在 $A,B$ 酒吧，那么在 $C$ 酒吧和在家的概率之比是 $3:1$，因此答案为 $75\%$。

这种方式的问题在哪里不必多说了。

解释

思考这个问题前应该回到概率定义的几个要素：样本空间，样本点，事件。

一个事件的概率被定义为事件大小除以样本空间大小。

三门问题

第一个问题中，样本空间的大小为 $3$，需要计算在某个不被选择的门后面是羊的情况下，选择的门后面是车的概率。

事件的大小为 $1$，因此概率为 $\frac{1}{3}$，另一个不被选择的门后面有车，其事件大小为 $2$，因为最初样本空间中在两个门后的样本点都属于该事件（如果是这两个事件之一，那么没被打开的另一扇门后必定是车）。

推广到 $n$ 门问题，主持人随机打开一个未被选择且没有车的门，那么样本空间大小为 $1$，不改变选择的事件大小为 $n-2$，改变选择的事件大小为 $n$。

酒吧问题

事件域

通常解决一个概率问题需要明确事件域，即我们关心的所有事件，如果事件域不合法，那么

某个样本空间不正确导致的悖论

假设选的门是 $1$ 号，已知 $2$ 号门没有车，那么 $3$ 号门有车的概率是 $$

我们需要明确问题中这个概率定义是在哪个样本空间下的，问题中样本空间的大小很明显是 $3$，而在被开的门后是山羊的事件大小为 $2$

样本空间无限的问题

最小生成树 X 动态规划

​ |

​ |

​ |

​ / \

​ / \

F1: xxxx oooo

…………

最小生成树(MST)

常用算法有 Kruscal 和 Prime，以下会谈一些 MST 的性质和两种算法的证明

Kruscal 证明（参考 OI-wiki）

核心思路是证明任意时刻边集均为一颗 MST 的子集。

归纳的，令当前边集 $F$ 属于的 MST 为 $T$，考虑新加入的一条边 $e$，如果 $e\in T$，自然成立。

如果 $e\notin T$，那么 $e+T$ 构成了一个环，考虑该环上所有边 $E_i$，一定满足 $w_{E_i} \le w_e$，否则 $e$ 应该在 $T$ 中，得到更优的 MST，所以 $E_i$ 已经在 $e$ 之前被加入，构成了一条完整的链。

所以不会加入 $e$，进行下一步。

一些性质

Prime

动态规划最小生成树

一般这种题都是指数级的题，有 这道，这道，和 这道

例题

给你一张图，问任选 $i$ 条边，使得图联通的方案数有多少种。

Method1

记录联通性动态规划

Mehod2

考虑 $dp[mask][i]$ 表示子图 $mask$ 的答案，转移时发现重复了，因为两种不同的子图分配方案最后可能对应到同一种选边方式，所以我们需要一个顺序一类的东西来保证不重复。

一种比较可行的方式是计算记录顺序的情况下的方案，这样可以钦定枚举的两个子图一定是最后连上的，最后除以一个阶乘。

另一种方式是直接容斥，考虑计算选 $k$ 条边后不联通的答案，枚举得到的两个连通块就是断开的，还是有重复的问题，但是我们可以钦定每种图只会在与 $1$ 相连的连通块处被统计，这是经典的连通图计数方式。

考试总结

考试

​ 成功垫底

​ 难 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$ 个不合法点一定有一个是起点。

总结

考试

T1

挺套路的题，通过 00 11 得到 $1,0$ 的个数，容易发现 10 01 的总个数已经被确定且容易构造。

但是有边界，考虑 00 11 个数为 $0$，此时可以取 $1$ 个也可以取 $0$ 个。然后 100->55

这种两个构成的计数问题，一定要考虑只有一个的边界情况，

注意我们通过题目信息得到新信息的过程，要看看是否为一一映射。

T2

有趣的题。

我先思考了如果一个问题我限定一个时间 $T$，等 $T$ 秒过完，得到的收益，实际上我们可能有根据当前信息改变等待的这个时间，所以这样不行。

接着考虑 $t$ 时刻到 Trie 上 $j$ 点的最优方案，发现其实不好转移。

注意到我们能决定的只有回答还是等待，所以这样的话转移会带上一个概率，但是这个概率却是无法相加后取最值的。

正难则反，考虑到 $j$ 点时还剩时间 $t$，最优能得到什么，这样的话，转移就只和我们的决定有关，成功解决这道题。

T3

等价于求最优解并构造方案。

它的修改本质上是需要决定一个最值，付出对应的代价，然后如果某个数绝对值严格小于最值，那么这个数的正负性就可以被指定，然后指定最值后最优化代价就是要求出删去的数的最小个数。

我们需要求出对于每个最值的删除数最小个数。

由于不让 $0$ 出现，所以先判掉不修改只删除的方案，这个是简单的。

有两种思考方式，对应了两种求答案的方式。

一个数为负视为 -1，为正视为 1，可调整视为 0

Method1

考虑一段极长连续相同子段，如果不为 0，那么必须删去然后只剩下一个。

如果为 0，其左右两边的状态和自身长度决定了它应该被删去一个或者不做任何处理。

如果能够维护机场连续相同子段，就可以得到答案。

考虑最值从小到大变化的过程，每次会把一个非 0 数改为 0，经典的 set 维护线段问题。

Method2

考虑动态规划。

设 $dp[i][0/1]$ 表示考虑到第 $i$ 个数，末尾为 $-1/1$ 的代价。

然后就是动态 DP，考虑能不能写成矩阵乘法的形式，发现是一个 $+\min$ 矩阵乘法。

线段树维护即可。

计算几何

写一下学计算几何的感悟。

向量

点积

$\mathbf{a} \cdot \mathbf{b} = |\mathbf{a}|\times|\mathbf{b}| \times \cos\theta = x_1x_2+y_1y_2$

常用来计算向量夹角。

叉积

$\mathbf{a} \times \mathbf{b} = |\mathbf{a}|\times |\mathbf{b}|\times \sin\theta = x_1y_2-x_2y_1$

几何意义是两个向量围成的平行四边形的面积。

从 $\mathbf{a}$ 旋转到 $\mathbf{b}$，如果角度小于 $\pi$，那么为正，否则为负。

证明的话，方向是直接定义的，先不管，尝试证明。

我觉得这个不太适合用 markdown 写下来。

为什么方向是对的，可以替换一下 $x,y$ 变成 $\sin,\cos$，然后很自然是对的。

可以用来求线段交点。

算一下 $BCD,ACD$ 的面积，用相似求 $AO$，就可以得到 $O$ 点坐标。

向量旋转

有人不会用这个东西，我不说是谁。

$\mathbf{a}$ 转 $\alpha$ 角：$(|\mathbf{a}|\cos(\theta+\alpha),|\mathbf{a}|\sin(\theta+\alpha))$。

和差角公式记不住的话朱某要来找麻烦，所以有人还是能记住。

多边形

三角剖分

$S=\dfrac{\sum\mathbf{a_i}\times \mathbf{a_{(i+1)\%n}}}{2}$

盗一波图。

凸包

按照逆时针方向看，多边形凸包永远往左拐。

直线

可以用一个点 $P$ 加方向向量 $\mathbf{v}$ 存储，也可以顺便记一个 $P_2$。

点在直线的哪边

求 $PQ\times \mathbf{v}$ 即可，为正在下方，为负在上方，$0$ 则在线上，前提条件是向量 $\mathbf{v}$ 的 $x$ 为正 。

快速排斥实验和跨立实验

两个矩阵不交，则通过快速排斥实验。

比较简易的方式是对于两维独立判断线段是否有交，如果任何一维无交，则通过快速排斥实验。

跨立实验则是判断一条线段的两端是否在另一条线段的两边，可以用向量叉乘做。

相互做跨立实验，如果均能通过，则线段有交或共线，结合快速排斥实验可以判断线段是否有交。

两条线段共线但不交也能通过跨立实验。

两直线交点

先判断平行和重合。

然后对于两条直线 $(P_1,\mathbf{a_1}),(P_2,\mathbf{a_2})$，设 $Q=k\mathbf{a_1}+P_1$，则有 $(P_2-(k\mathbf{a_1}+P_1))\times \mathbf{a_2}=0$

叉积有分配律，所以直接拆开解 $k$ 然后带回去。

$k=\dfrac{(P_2-P_1)\times \mathbf{a_2}}{\mathbf{a_1}\times\mathbf{a_2}}$

如果你敢约分，朱某就敢把你鲨了。

线和直线的垂足

算出 $PQ$ 在 $\mathbf{v}$ 上投影的长度和方向（点积），$P$ 加上这个就行。

点到直线距离

可以先算垂足，也可以用记下来的另一个点带面积公式算。

角平分线

模长相同的方向向量相加，得到角平分线的方向向量，证明考虑构造菱形。

凸包

于是乎求凸包的时候多了一种判定方式：

如果是上凸包，弹出点的充要条件是上个点在该点与上上个点的连线下方

下凸包，弹出条件就是在上方，比斜率好一点，而且判共线很方便。

圆

线援交圆交

求出点到直线距离和垂足，然后勾股定理算两个点。

圆圆交

半径相等可以求中点勾股定理偷懒，半径不等可以选一个三角形解三角形。

具体的，可以算出一个角的 $\cos$ 然后旋转向量，最后乘半径再加上去。

切点

勾股定理，旋转，解三角形。