2024-08-01 训练总结

卡常卡爽了！

往事成风

赛事靠着自己的猜测水到了 80 pts，乱想能力还是有一定进步的。

正解和我的想法差不多。

先是转换题目思路——选择若干个数使得大于等于一个数。

思路是删的区间是连续的，猜想不会太多，就一段一段删。

其实只需要在线段树上先走右端再走左端就好了。

数数乐

推式子题。

赛事失误了一点：没想到式子之间有递推关系，是 \(O(Tn)\) 的。

事实上是可以递推实现 \(O(n)\) 的，为接下来的思考奠定了基础。

这种题一般是两种想法：

1. 数学意义
2. 组合意义

就像是这道题，可以通过组合意义将一坨式子进行转换。

组合意义一般是想不到的。我也没什么好的方法。

走廊

平衡树练手题。打完之后感觉对 Splay 的理解更深了。

就是用 Splay 维护一个类似链表的东西。使用了分裂和合并操作。

比如分裂点 \(a,b\)，若 \(a<b\)，就是先 splay(b) 再 splay(a)，那么此时 \(b\) 一定在 \(a\) 的右端点。断边就可以了。

合并同理。

感觉对平衡树的理解不够深。还需要进一步做题！

Ginger 的无向无环联通图

卡常卡爽了！

本质很简单，就是分为前缀最值操作，后缀最值操作，区间最值操作（都是取 max）。

前两个都很容易在 \(O(n)\) 内处理（赛时会，但是不会最后一个），而最后一个发现区间一定是 dfn 序，所以可以类似树形 dp 来处理。

查询就是前缀求某个数个数，后缀求某个数个数，区间求某个数个数。

这个赛时就不会了。其实我们发现这个求的区间和赋值的区间是一样的。所以这个区间的其他数肯定都大于等于这个要查询的数，只用维护前缀最小值，后缀最小值，dfn 区间最小值。

这些看了题解就会了。但是重要的是卡常！

一方面，我们不能用任何递归！求 dfn 序也不能。可以用类似树形 dp 的方法。当然，我们也不能真的树形 dp。可以按照 dfn 序从前往后操作即可。

另一方面，数组的连续访问也非常重要：

访问要连续，如果不连续访问尽量拆开for循环。

也就是说，for循环不能写太长！

举个例子，下面的代码需要跑3秒：

for(int i = 2; i <= n; ++ i) {
	// 求 dfn 序
	dfn[i] = dfn[fa[i]] + ch[fa[i]] + 1;
	ch[fa[i]] += sz[i];

	// 维护代价
	const ll in = (ll)w[i] * sz[i], out = (ll)w[i] * (n - sz[i]);
	a1[dfn[i] - 1] = max(a1[dfn[i] - 1], in);
	a2[dfn[i] + sz[i]] = max(a2[dfn[i] + sz[i]], in);
	a3[i] = max(a3[fa[i]], out);
}

然而你发现这是两个不同的任务，之间是没有关联性的，跳跃访问时间复杂度很大。

所以我们将它们拆开：

for(int i = 2; i <= n; ++ i) {
	dfn[i] = dfn[fa[i]] + ch[fa[i]] + 1;
	ch[fa[i]] += sz[i];
}
	
for(int i = 2; i <= n; ++ i) {
	const ll in = (ll)w[i] * sz[i], out = (ll)w[i] * (n - sz[i]);
	a1[dfn[i] - 1] = max(a1[dfn[i] - 1], in);
	a2[dfn[i] + sz[i]] = max(a2[dfn[i] + sz[i]], in);
	a3[i] = max(a3[fa[i]], out);
}

这样只用跑500毫秒。

同理，我们不要使用 dfu[dfn[i]]=i 来求 dfu 序，最好是不要使用 dfu 序，因为这样访问很不连续。

同时，学会了一个新的快读：mmap：

mmap基于Linux的黑科技，直接将文件映射到内存操作，中间不需要阻塞系统调用，不需要内核缓存，只需要一次lseek，因而有更优的速度，是极限卡常者不二选择。在fread(new)已经非常快的情况下再甩36ms，而且实际使用的时候速度更快。

#include <fcntl.h>
#include <unistd.h>
#include<sys/mman.h>
char *pc;
inline int read(){
int num = 0;
char c;
while ((c = *pc++) < 48);
while (num = num * 10 + c - 48, (c = *pc++) >= 48);
return num;
}
int main(){
	freopen("treeq.in","r",stdin);
	freopen("treeq.out","w",stdout);
	pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
}