大意：

给一个n的排列（n<=10^5），有m（m<=10^5）个操作：

• 1 l r 表示把[l, r]区间内的数降序排序；

• 0 l r 表示把[l, r]区间内的数升序排序。

最后询问这个序列的第p个位子上的数是多少。

做法：

由于将一个普通序列排序很慢，需要nlogn的时间，所以我们试着把它转化为对01序列排序。先来考虑一个简单的问题：

• 如何将一个01序列排序？（logn的复杂度）

• 对于这个问题，我们使用线段树来维护。查询一段区间内的1的个数记为cnt1，如果是升序，就将这段区间的[r-cnt1+1, r]都更改为1，将[l, r-cnt1]更改为0。降序则将[l, l+cnt1-1]更改为1，将[l+cnt, r]更改为0。这样我们就成功地把排序转化为了区间查询和区间修改。

接下来我们来说本题的做法：

这是一个离线的做法。首先二分答案mid。我们把原排列中大于等于mid的数都标记为1，小于mid的都标记为0。然后对于每个操作我们就将01序列排个序。最后如果第p个位子仍是1的话就是可行的。

这个二分成立因为是满足单调性的：可以简单地假设一下，如果你二分的答案是1，那么原序列所有的值都转化为了1，所以最后肯定是true。如果二分一个值成立当且仅当这个位子的值大于等于mid，故如果check返回true，则l = mid+1，否则r = mid-1。

（这题的思想可以借鉴，比较巧妙）

#include<cstdio>
#include<cstring>
#include<cctype>
#define lc o<<1
#define rc o<<1|1
#define mid (l+r)/2
using namespace std;

const int N = 100010;
int n, m, p;
int T[4*N], lazy[4*N];//segment tree
int a[N], ch[N], L[N], R[N];//the information by reading

inline int read()
{
    char ch = getchar(); int x = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)){ x = x*10+ch-'0'; ch = getchar(); }
    return x;
}

inline void build(int o, int l, int r, int x)
{
    if (l == r){
        T[o] = a[l] >= x;
        lazy[o] = 0;
        return;
    }
    build(lc, l, mid, x); build(rc, mid+1, r, x);
    T[o] = T[lc]+T[rc]; lazy[o] = 0;
}

inline void pushdown(int o, int l, int r)
{
    if (!lazy[o]) return;
    lazy[lc] = lazy[rc] = lazy[o];
    if (lazy[o] == 1){
        T[lc] = mid-l+1; T[rc] = r-mid;
    } else T[lc] = T[rc] = 0;
    lazy[o] = 0;
}

inline int query(int o, int l, int r, int x, int y)
{
    if (x <= l && y >= r) return T[o];
    if (x > r || y < l) return 0;
    pushdown(o, l, r);
    return query(lc, l, mid, x, y) + query(rc, mid+1, r, x, y);
}

inline int queryPoint(int o, int l, int r, int x)
{
    if (l == x && r == x) return T[o];
    pushdown(o, l, r);
    if (x <= mid) return queryPoint(lc, l, mid, x);
    else return queryPoint(rc, mid+1, r, x);
}

inline void update(int o, int l, int r, int x, int y, int val)
{
    if (x <= l && y >= r){
        T[o] = val*(r-l+1); lazy[o] = val ? 1 : -1;
        return;
    }
    if (x > r || y < l) return;
    pushdown(o, l, r);
    update(lc, l, mid, x, y, val);
    update(rc, mid+1, r, x, y, val);
    T[o] = T[lc]+T[rc];
}

inline bool check(int x)
{
    build(1, 1, n, x);
    for (int i = 1; i <= m; i ++){
        int cnt1 = query(1, 1, n, L[i], R[i]);
        if (ch[i] == 0){
            update(1, 1, n, R[i]-cnt1+1, R[i], 1);
            update(1, 1, n, L[i], R[i]-cnt1, 0);
        }
        else{
            update(1, 1, n, L[i], L[i]+cnt1-1, 1);
            update(1, 1, n, L[i]+cnt1, R[i], 0);
        }
    }
    return queryPoint(1, 1, n, p);
}

int main()
{
    n = read(); m = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    for (int i = 1; i <= m; i ++){
        ch[i] = read(); L[i] = read(); R[i] = read();
    }
    p = read();
    int ll = 1, rr = n, midd, ans;
    while (ll <= rr){
        midd = (ll+rr) >> 1;
        if (check(midd)) ans = midd, ll = midd+1; else rr = midd-1;
    }
    printf("%d\n", ans);
    return 0;
}

线段树分裂

以某个键值为中点将线段树分裂成左右两部分，应该类似Treap的分裂吧（我菜不会Treap）。一般应用于区间排序。

方法很简单，就是把分裂之后的两棵树的重复的$\log$个节点新建出来，单次时间复杂度严格$O(\log n)$。

至于又有合并又有分裂的复杂度，蒟蒻一直不会比较有说服力的证明，直到看见SovietPower巨佬的题解

对于只有合并：合并两棵线段树的过程，是找到它们$x$个重合的节点的位置，并将它们合并，而对于不重合的节点会跳过。

注意到合并与分裂类似互逆过程，也就是说可以看做是删掉了这$x$个节点。

所以可以得出，时间复杂度上界，等于被删去的节点数的上界，不大于若干线段树最开始的节点数。

那么，对于一些既有合并又有分裂的题目，复杂度也是可以分析滴！

$n$棵线段树初始有$O(n\log n)$的节点，每一次分裂只会新增$O(\log n)$的节点

于是总点数就是$O((n+m)\log n)$级别的，线段树合并的总代价就不会超过$O((n+m)\log n)$了。

接下来回到这题

如果一个区间有序，那么顺序是唯一的，我们就可以把它们插到一个权值线段树里，记录一下是升序还是降序。区间排序就变成了线段树合并。

但是我们的排序端点可能会落在一个有序区间内，这时候就要拆开。额外用一个set标记已经有序的区间（像珂朵莉树一样），需要拆开时线段树分裂。

突然暂时变成了洛谷rk1

#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;
}

C38 线段树+二分 P2824 [HEOI2016/TJOI2016] 排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
int n,m,q;
int a[N],op[N],L[N],R[N];
struct trnode
{
    int l,r;
    int sum,tag;
}tr[N<<2];
//sum:区间1的个数
//tag:-1:区间无标记,0/1:区间赋值为0/1

void pushup(int p){tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;}
void pushdown(int p)
{
    if(tr[p].tag==-1) return;
    tr[lc(p)].sum=tr[p].tag*(tr[lc(p)].r-tr[lc(p)].l+1);
    tr[rc(p)].sum=tr[p].tag*(tr[rc(p)].r-tr[rc(p)].l+1);
    tr[lc(p)].tag=tr[rc(p)].tag=tr[p].tag;
    tr[p].tag=-1; //清空懒标记
}
void bt(int p,int l,int r,int x)
{
    tr[p]={l,r,a[l]>=x,-1};
    if(l==r) return;
    int m=l+r>>1;
    bt(lc(p),l,m,x);bt(rc(p),m+1,r,x);
    pushup(p);
}
void change(int p,int l,int r,int k)//区修
{
    if(r<tr[p].l || tr[p].r<l) return;
    if(l<=tr[p].l && tr[p].r<=r)
    {
        tr[p].sum=k*(tr[p].r-tr[p].l+1);
        tr[p].tag=k;
        return;
    }
    pushdown(p);
    change(lc(p),l,r,k);change(rc(p),l,r,k);
    pushup(p);
}
int query(int p,int l,int r)//区查
{
    if(r<tr[p].l || tr[p].r<l) return 0;
    if(l<=tr[p].l && tr[p].r<=r)return tr[p].sum;
    pushdown(p);
    return query(lc(p),l,r)+query(rc(p),l,r);
}
bool check(int x)
{
    bt(1,1,n,x);
    for(int i=1;i<=m;i++)
    {
        int l=L[i],r=R[i];
        int cnt=query(1,l,r); //1的个数
        if(op[i]==0)
        {
            change(1,r-cnt+1,r,1);
            change(1,l,r-cnt,0);
        }
        else
        {
            change(1,l,l+cnt-1,1);
            change(1,l+cnt,r,0);
        }
    }
    return query(1,q,q); //q位置的数，如果>=x返回1
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&op[i],&L[i],&R[i]);
    scanf("%d",&q);
    int l=0,r=n+1; //二分答案，可枚举0~n
    while(l+1<r)
    {
        int mid=l+r>>1;
        check(mid)?l=mid:r=mid;
    }
    printf("%d\n",l);
    return 0;
}

C72 线段树分裂合并+集合维护 P2824 [HEOI2016TJOI2016] 排序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

void read(int &x){ //快读
  x=0; char c=getchar();
  while(!isdigit(c))c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar();
}
const int N=100005;
#define mid ((l+r)>>1)
typedef set<int>::iterator it; //set定位器
set<int> st;
int n,m,tot,root[N],o[N];
int ls[N*55],rs[N*55],sum[N*55];
//o[p]:记录p位置之后的一段是升序还是降序
//sum[x]:记录区间权值个数之和

void change(int &x,int l,int r,int p){ //点修
  x=++tot; sum[x]=1;
  if(l==r) return;
  if(p<=mid)change(ls[x],l,mid,p);
  else change(rs[x],mid+1,r,p);
}
int query(int x,int l,int r){ //点查
  if(l==r) return l;
  if(ls[x]) return query(ls[x],l,mid);
  else return query(rs[x],mid+1,r);
}
void merge(int &x,int y){ //合并
  if(!x||!y){x+=y;return;}
  sum[x]+=sum[y];
  merge(ls[x],ls[y]);
  merge(rs[x],rs[y]);
}
void split(int x,int &y,int k,int o){ //分裂
  //将x从k处斩断，一段归x，另一段归y
  if(sum[x]==k) return;
  y=++tot; sum[y]=sum[x]-k; sum[x]=k;
  if(o==0){ //升序，前k小归x
    if(k<=sum[ls[x]]) split(ls[x],ls[y],k,o),swap(rs[x],rs[y]);
    else split(rs[x],rs[y],k-sum[ls[x]],o);
  }
  else{     //降序，后k大归x
    if(k<=sum[rs[x]]) split(rs[x],rs[y],k,o),swap(ls[x],ls[y]);
    else split(ls[x],ls[y],k-sum[rs[x]],o);