pinkyHead's blog

Intro 首先要明确一点，LCT的应用场合是什么？ 回想以前的树上操作，树的拓扑结构都是不发生变化的，然后一般利用树链剖分结合线段树实现logn或logn^2的单次操作。 而LCT其实也是一个广义的“树链剖分”，它在树的拓扑结构发生变化时(例如要求能满足断开边，再连接新边的操作)，仍然能满足logn或logn^2的单次操作复杂度 实链剖分 对于一个点连向它所有儿子的边 , 我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边（当然，有可能所有儿子都是虚边）。 对于实边，我们称它所连接的儿子为实儿子。 对于一条由实边组成的链，我们同样称之为实链。 辅助树 在一条实链中的所有点，使用同一个splay维护。这个splay被称为辅助树。每棵辅助树维护的是一棵树，一些辅助树构成了LCT，其维护的是整个森林。 辅助树由多棵 Splay 组成，每棵 Splay 维护原树中的一条路径，且中序遍历这棵 Splay 得到的点序列，从前到后对应原树“从上到下”的一条路径。 原树每个节点与辅助树的 Splay 节点一一对应。 每棵 Splay 的根节点的父亲节点本应是空，但在 LC ...

区间最值 区间最值操作指，将区间[l,r][l,r][l,r]的数全部对x取max或min，例如ai=max(ai,x)a_i=max(a_i,x)ai​=max(ai​,x) HDU5306 Gorgeous Sequence 这里比较玄学的是，维护一个最大值和次大值即可，这样的复杂度就能降为logn。这里可以用势能分析法得到证明。 这里使用到的势能分析法在splay的复杂度证明中也用到了，但是没有系统学习，过段时间来填坑。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107#include <algorithm>#include <cctype>#include <cstdio& ...

intro Splay 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链 实现过程 主要过程参照传送门即可，讲得十分详细，这里就不再赘述 说一下删除操作吧，这部分当时看了比较长的时间才看明白 1234567891011121314151617181920212223242526272829303132void del(int k) { rk(k); if (cnt[rt] > 1) { cnt[rt]--; maintain(rt); return; } if (!ch[rt][0] && !ch[rt][1]) { clear(rt); rt = 0; return; } if (!ch[rt][0]) { int cur = rt; rt = ch[rt][1]; fa[rt] = 0; clear(cur); return; } if ( ...

现在 现在是12.14凌晨1点40，晚上八点的时候睡了一觉，刚才醒了就一直睡不着，想想还是写点东西吧。 一 这里聊一聊我目前人生中最喜欢的一部电影吧：《少年时代》。 这部电影花了12年拍摄，讲述了一个男孩从6岁到18岁的成长的故事。 我记得是在高二一个周六的晚上，一个人躺在沙发上看电视，无意间刷到了这部电影，然后就一口气看到了结束。 虽然很多剧情都记不太清了，但是我现在依然能清晰地回想起，在电影结束后泪流满面的我。 其实我的人生和男主的故事并没有太多相似之处，所以这份感动并没有来自所谓的“共情”，而是来自于目睹了一个男孩的成长经历后，感到无比的怅然。这里的伤感是因为我忽然意识到，其实我也目睹过了另一个男孩的成长——即我自己。 小时候，总觉得自己的人生有无限的可能性，总觉得只要自己肯努力，就一定会做成任何事情。可随着年龄的增长，我发现这种可能性在逐渐的消磨，对自己的怀疑与否定也越来越深。 当我回顾我的前几年，这种感觉愈发的强烈。 可能这里还有一个比较特殊的因素吧，那就是我现在的观念以及处事态度，是基于对更早的岁月的激烈否定以及兼并中形成的。而在那段更早的岁月里，却是我人生中对未来最为 ...

XXII Open Cup. Grand Prix of Korea C.Equivalent Pipelines 首先可以看到，树的数量很多，所以只能给每个树一个hash值，从而通过hash是否相同判断是否同类 这里可以首先意识到，对于两棵树而言，先把所有边断开，从大到小开始依次加边，一次操作只加相同长度的边，如果能保证每次连起来的若干个新的连通分量内部的点都是一样的，那么就符合要求。 通过归纳法可以容易得出：对于所有长度为w的边，我们记录这个长度w，还有连接发生前每个连通分量中编号最小的点，以及通过这条边连成的新连通分量中编号最小的点，形成一个三元组；如果对于两棵树而言，它们的三元组的集合完全一样，则一定满足上述条件。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include<bits/stdc ...

CCPC#2020威海 G.Caesar Cipher 很经典的hash+线段树，以后遇到“求解序列是否相同”都可以试试hash 这里的数字要对65536取模，可以存储每个区间的mn和mx值，这样就可以知道是否有数字达到了65536，然后，对于任何满足内部所有数字都达到了65536的区间清零。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128#include<bits/stdc++.h>using namespace std;typedef long long ll;type ...

一 现在是周六晚9点27分。现在我正一个人坐在校队机房里，虽然窗户外面就是著名的兴庆宫，但是在这寂静的夜里，也只有断断续续的车流声与我作伴…我想，这真是个写点东西，发发牢骚的好时机啊 于是打开博客，我又翻了翻一年前自己写的东西，感觉是真的中二(～￣▽￣)～不过了一下回顾当初立下的flag，也算是勉强达成了？如果不算cf的还没上橙的话 二 感觉人真的很神奇，随着时间的推进，不经意间就会领会到很多奇奇怪怪的东西。在大三的这个时候，在这样一个不算太舒服的处境下，我反而活得不那么拧巴了。这两个月里，每天的生活似乎都离不开共享单车了。下课后，要从主楼的教室骑到位于学校西北角的机房；晚上十点半，再从机房骑到学校东南角的宿舍。最有意思的是，因为每天晚上都是最后一个从西一楼二楼出来的人，那个负责关门的阿姨都认识我了🤣 五月开始到现在，头晕仍然没有好，每天写代码都是昏沉沉的，但是心情其实并没有太受影响。晚上收拾好电脑回宿舍，在梧桐西道骑行的时候，路灯撒下淡淡的黄晕，耳机里放着Carmen Suite No. 2:III. Nocturne，给了我有一种很不真实的祥和与平静。也许在若干年以后，我仍会 ...

小记 同样作为强连通分量相关的算法，tarjan算法似乎要出名得多，实际上我也是两天前才知道还有个叫Kosaraju的算法。后者与前者的理论复杂度其实是一样的，而且实际情况应用中前者甚至会稍快一些。但是Kosaraju算法有着tarjan所没有的优势——Kosaraju可以与bitset相结合，从而能够在极为优秀的复杂度内解决一些稠密图内的问题。 算法流程 首先对图进行第一遍dfs，并把遍历到的点压入栈中。值得注意的是，这里的压栈要写在dfs函数的最后，即在一个节点及其后继完全访问完毕后再压栈操作。 对这个图求反，即把所有边反向。然后在这个反图上跑dfs。注意这里跑dfs时，选取上一步中栈顶的元素作为起点。一次dfs中遇到的所有点，都属于同一个强连通分量，并且标记他们，注意在dfs过程中，不能访问已经标记过的点。如果dfs结束，那么再次从栈顶取一个未被标记的元素，以它为起点继续在反图上跑dfs，如此往复，直到栈为空。 算法结束，所有的强连通分量已求出。 123456789101112131415161718192021222324252627282930313233343536 ...

ICPC#2020澳门站 C.Club Assignment 挺小清新的一个构造题。要尽量使得高位能有1，如果无法避免有的异或值高位为0的话，那么就继续递归地往下讨论，并且这一位不同的数字之间的相对位置关系对答案就不会产生影响了。 模拟赛的过程中没写完，下来花了1个多小时一遍AC了，还是挺爽的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134#include<bits/stdc++.h>using namespace std;typede ...

二分图最大匹配 图的匹配，即由一组没有公共端点的不是圈的边构成的集合，我们这里需要使得这个集合尽可能大，即寻找二分图的最大匹配 这里需要先了解两个定义： 交错路：给定图G的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径 增广路（增广轨）：如果一条M-交错路径，它的两个端点都不与M中的边关联，我们称这条路径叫做M-增广路径 匈牙利算法 该算法本质上就是不停地找增广路并更新答案，复杂度为O(nm)O(nm)O(nm)。 算法的正确性证明可以看这里 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960struct augment_path { vector<vector<int> > g; vector<int> pa; // 匹配 vector<int> pb; vector<int> vis; ...