Link Cut Tree对我来说已经有点老生常谈了——目前为止理解的比较深的一种比较难的数据结构吧。         之前的初探以及次探已经基本阐明了LCT本身的功能和大部分的作用，在这里做一个简单点的回顾吧。         首先就是数据结构本身。LCT又叫做动态树，本身很像树链剖分+SplayTree，但是如其名，可以动态的变化。主要函数就是Access(expose)、Splay和Reverse。初始状态的时候，所有的点都自成一个SplayTree，每一个点都是一个SplayTree的root，于是就有了判根函数isroot(x)，如果是根，...

大致题意：给你n个点，第i个点在的位置为(xi,yi)，有两个属性值(ai,bi)。现在让你把这n个点划分为A和B两个部分，使得最后不存在i∈A和j∈B，使得xi>=xj且yi<=yj。然后对于所有的划分方法，找到并输出                                                   &nbsp...

大致题意：给你n个数字，然后让你求所有满足异或和为0的子集的大小之和。 首先这个子集大小之和，显然可以转换为计算每个数字的出现次数之和。考虑到异或和为0的子集，相当于可以用集合中的一部分数字去表示另外一部分数字，所以很容易想到用线性基解决这个问题。 对于这n个数字求线性基，假设线性基的个数为r(r<n)，那么对于线性基外的n-r个数字，他们的任意组合都可以在线性基内的r个数字找到一个组合，使得异或和为0。现在考虑计算线性基外每个数字的贡献，对于任意一个基外的数字，他都可以和任意剩下n-r-1个数字组合，对应有个方案，每个方案都能在基内找到一个组合使得异或和为0。所以这一部分的...