题解 P2824 【[HEOI2016/TJOI2016]排序】
FlashHu
2019-02-01 08:49:45
### 线段树分裂
以某个键值为中点将线段树分裂成左右两部分，应该类似Treap的分裂吧（我菜不会Treap）。一般应用于区间排序。
方法很简单，就是把分裂之后的两棵树的重复的$\log$个节点新建出来，单次时间复杂度严格$O(\log n)$。
至于又有合并又有分裂的复杂度，蒟蒻一直不会比较有说服力的证明，直到看见[SovietPower巨佬的题解](https://www.cnblogs.com/SovietPower/p/9300819.html)
对于只有合并：合并两棵线段树的过程，是找到它们$x$个重合的节点的位置，并将它们合并，而对于不重合的节点会跳过。
注意到合并与分裂类似互逆过程，也就是说可以看做是删掉了这$x$个节点。
所以可以得出，时间复杂度上界，等于被删去的节点数的上界，不大于若干线段树最开始的节点数。
那么，对于一些既有合并又有分裂的题目，复杂度也是可以分析滴！
$n$棵线段树初始有$O(n\log n)$的节点，每一次分裂只会新增$O(\log n)$的节点
于是总点数就是$O((n+m)\log n)$级别的，线段树合并的总代价就不会超过$O((n+m)\log n)$了。
接下来回到这题
如果一个区间有序，那么顺序是唯一的，我们就可以把它们插到一个权值线段树里，记录一下是升序还是降序。区间排序就变成了线段树合并。
但是我们的排序端点可能会落在一个有序区间内，这时候就要拆开。额外用一个set标记已经有序的区间（像珂朵莉树一样），需要拆开时线段树分裂。
~~突然暂时变成了洛谷rk1~~
```cpp
#include<bits/stdc++.h>
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
using namespace std;
typedef set<int>::iterator IT;
const int SZ=1<<19,N=1e5+9,M=6e6;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
int p,rt[N],lc[M],rc[M],s[M],o[N];
set<int>t;
void ins(R&x,R l,R r,R k){
s[x=++p]=1;
if(l==r)return;
R m=(l+r)>>1;
k<=m?ins(lc[x],l,m,k):ins(rc[x],m+1,r,k);
}
int qry(R x,R l,R r){
if(l==r)return l;
R m=(l+r)>>1;
return lc[x]?qry(lc[x],l,m):qry(rc[x],m+1,r);
}
void mer(R&x,R y){//合并
if(!(x&&y)){x|=y;return;}
s[x]+=s[y];
mer(lc[x],lc[y]);
mer(rc[x],rc[y]);
}
void spl(R&x,R y,R k,R o){//分裂
if(s[y]==k)return;
s[x=++p]=s[y]-k;s[y]=k;
if(o){
if(k<=s[rc[y]])spl(rc[x],rc[y],k,o),lc[x]=lc[y],lc[y]=0;
else spl(lc[x],lc[y],k-s[rc[y]],o);
}
else{
if(k<=s[lc[y]])spl(lc[x],lc[y],k,o),rc[x]=rc[y],rc[y]=0;
else spl(rc[x],rc[y],k-s[lc[y]],o);
}
}
IT Split(R p){//拆区间
IT i=t.lower_bound(p);
if(*i==p)return i;
--i;spl(rt[p],rt[*i],p-*i,o[p]=o[*i]);
return t.insert(p).first;
}
int main(){
R n=in(),m=in();
t.insert(n+1);
for(R i=1;i<=n;++i)
ins(rt[i],0,n,in()),t.insert(i);
while(m--){
R op=in(),l=in(),r=in();
IT il=Split(l),ir=Split(r+1);
for(IT i=++il;i!=ir;++i)mer(rt[l],rt[*i]);
o[l]=op;t.erase(il,ir);
}
R q=in();
Split(q);Split(q+1);
printf("%d\n",qry(rt[q],0,n));
return 0;
}
```