操作过程：每次把小的集合合并进大的集合里。
每个点所在集合大小每次至少会翻倍，每点最多被插入O(logn)次。
#include#include#include#include#include#include#include#include#includeusingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#defineRregister/*【p3224】永无乡n个点，每个点有权值：1.用一条无向边连接两个点；2.查询一个点所在联通块里面点第kth权值。*///如何查询连通块第k大？平衡树。/*【平衡树启发式合并】对于每个联通块，用一个平衡树来维护这个联通块里面所有点的权值。每次连接两个联通块的时候，把小的联通块的平衡树插入到大的联通块的平衡树里。使用splay或者带fingersearch的数据结构的总复杂度是O(nlogn)。*/voidreads(int&x){//读入优化（正负整数）intf=1;x=0;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f;//正负号}
【分析】先考虑静态链kth怎么做。
从根DFS，建立可持久化Trie（主席树）;每次查询链，把链差分为四个前缀的差。
然后在这四个可持久化Trie（主席树）上面一起二分即可。然后考虑启发式合并。
#include#include#include#include#include#include#include#include#includeusingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#defineRregister/*【p3302】森林1.link两个点；2.查询一条链上的kth。保证随时是一棵树，强制在线。*//*【分析】先考虑静态链kth怎么做。从根DFS，建立可持久化Trie（主席树）;每次查询链，把链差分为四个前缀的差。然后在这四个可持久化Trie（主席树）上面一起二分即可。然后考虑启发式合并。*/voidreads(int&x){//读入优化（正负整数）intf=1;x=0;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f;//正负号}
即：从上一次到达的位置开始，经过lca走到所需节点。
2.区间排序；3.ODT类问题。
类似序列颜色段数均摊，不过是均摊O((n+m)logn)次修改。
复杂度证明：和lct的access类似。
平衡树旋转/重构的节点的size的和是O(nlogn)，
这样可以在旋转的时候暴力重构一些信息。
#include#include#include#include#include#include#include#include#includeusingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#defineRregister/*【p3987】珂朵莉1lrx:把区间[l,r]中所有x的倍数/x，2lr:查询区间[l,r]的和。*//*【分析】考虑一个数最多被除logxT次，问题变成了如何快速找出x的倍数。把每个下标插入到其约数的所有平衡树里，每次x的倍数/x，就在x对应的平衡树里面暴力查询一段区间的每个数是否是x倍数。平衡树复杂度O(logn+s)（s是区间点数），总复杂度O(nd(n)+nlog^2n+mlogn)。*/voidreads(int&x){//读入优化（正负整数）intf=1;x=0;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f;//正负号}
#include#include#include#include#include#include#include#include#includeusingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#defineRregister/*【CF250D】单点修改，区间modp，区间和。*///If(x>=p)-->xmodp<=x–p-->xmodp<=x/2//每次减半，最多log次就会变成0。线段树维护区间max即可。voidreads(int&x){//读入优化（正负整数）intf=1;x=0;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f;//正负号}
静态分块：每块为整体，零散用暴力。
【经典例子】区间众数，区间逆序对数。
动态分块：每块里面维护一个数据结构，可动态修改。
【经典例子】区间加区间rank，区间加区间kth。
（1）维护一个序列，支持：O(1)单点修改，O(sqrt(n))区间求和。
-->分块维护块内和，修改时更新块内和、和对应数组上的值。
（2）维护一个序列，支持：O(sqrt(n))单点修改，O(1)区间求和。
-->分块维护块内前缀和、块外前缀和。
即：维护每个块块内位置前x数的和、以及前x的块的和。
更新的时候分别更新，查询的时候把这两个前缀和拼起来。
（3）维护一个序列，支持：O(sqrt(n))区间加，O(1)单点求值。
-->直接分块即可。按整块、零散块修改，单点求值。
（4）维护一个序列，支持：O(1)区间加，O(sqrt(n))单点求值。
-->每次对区间[l,r]加x的时候，差分为前缀[1,l-1]减x，前缀[1,r]加x。
同时在数组上和块上打标记，使得区间[l,r]加x。
查询的时候就扫过块外的标记和块内的标记即可。
（5）维护一个集合，支持：O(1)插入一个数，O(sqrt(n))查询第k小。
-->离散化后对值域进行分块，维护第i个块里面有多少个数。
查询时从第一块开始往右，最多走过sqrt(n)个整块和sqrt(n)个零散数。
（6）维护一个集合，支持：O(sqrt(n))插入一个数，O(1)查询第k小。
-->值域分块。对于每个数维护一下其在哪个块里面。
对于每个块维护一个OV（有序表）表示这个块内的所有数存在的数，从小到大。
这样我们修改的时候只会改变sqrt(n)个数所从属的块。
查询的时候定位到其所属于的块，然后找到其在该块中对应的值。
#include#include#include#include#include#include#include#include#includeusingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#defineRregister/*【p3245】大数求数字串S的一个子串中有多少子串是P的倍数。*//*【分析】记suf[i]为i->n构成的后缀串。如果对于l,r有suf[l]%p==suf[r+1]%p。即(suf[l]–suf[r+1])%p==0。那么问题转化为统计多少个二元组lr满足suf[]%p相等。则s[l...r]*10^(n-r-1)为p的倍数。注意：对p=2、5时特判。数据离散化，得到类似小z的袜子。*/voidreads(int&x){//读入优化（正负整数）intf=1;x=0;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f;//正负号}
