动态kth

之前看了几天都不会，对着std写一份代码就自己领悟了，看来学算法还是离不开实践。

对于一些贡献互相独立的修改与查询操作，如果满足可二分性，可以按照时序放在一起离线二分处理，即整体二分。

题目要求在一个可以动态更新的序列里求出下标在([l,r])内的第(kth)数。一个非常经典的做法就是树状数组套主席树，时空复杂度都是(O(nlogn^2))的，并且常数较大。应用整体二分可以再(O(nlogn^2))的时间，(O(n))的空间内解决这个问题。

考虑对一个询问产生的贡献从哪里来，一部分是初始给出的序列，一部分是在询问区间内的修改。最朴素的方法就是直接修改并对区间扫描查询，时间瓶颈在于查询。

换一个角度来思考，树套树维护的就是值域，我们可以基于值域而对位置进行处理。先对原序列和修改离散。在当前区间([l,r])中，按照时间顺序依次处理操作和查询。

对于查询，比较要求的(kth)与区间([ql,qr])中的数的个数。如果(kth<=cnt)，则至多到(mid)的修改就可以满足，放入左子区间([l,mid])处理。如果(kth>cnt)，则只有(mid)中的修改无法满足要求，放入右子区间([mid+1,r])递归处理。递归边界(l==r)，此时所有的询问答案都是(l)。

ri v=fwt.qry(qr)-fwt.qry(ql-1);
if(qk<=v)subl[++sizl]=a[i];
else subr[++sizr]=a[i],req.k-=v;

递归边界(l==r)，此时所有的询问答案都是(l)。

if(l==r) For(i,1,siz)if(isreq)ans[req.id]=l;

对于修改，将所有前后值在区间终点异侧的修改加入树状数组。由于查询的判定区间是([l,mid])，只有从([l,mid])到非([l,mid])的修改或反之才对剩下的查询产生贡献。

if(bel(l,mid,cl)&&!bel(l,mid,cr))fwt.mdf(ck,-1);
if(!bel(l,mid,cl)&&bel(l,mid,cr))fwt.mdf(ck,1);

下放修改时根据是否有一侧在左右区间内有修改，不然没有贡献。

if(bel(l,mid,cl)||bel(l,mid,cr))    subl[++sizl]=a[i];
if(bel(mid+1,r,cl)||bel(mid+1,r,cr))subr[++sizr]=a[i];

还要注意每次把树状数组修改过的位置清零。

对值域分治，一共有(nlogn)层。需要利用树状数组，单次操作(logn)。总时间复杂度(O(nlogn^2))。由于并不需要维护多余的位置信息，空间复杂度(O(n))，在某些卡空间的毒瘤题中可以代替树套树。常数也远小于树套树，实现也较为简便。