[洛谷P2824][题解][HEOI2016/TJOI2016]排序

0.概览

原题

1.解法

每次都排序太麻烦了，我们考虑如何转化。
简化问题：给定一个只由0和1组成的序列，进行相同的操作和查询。
对于01序列的排序，我们可以直接使用线段树区间修改实现（统计出1的个数后把一边赋为1一边赋为0）。
这道简化问题与原题的唯一区别就是原题是一个排列。
众所周知，求答案的题经常可以通过二分转化为较简单的判定，此题也不例外。
我们二分一个答案\(limt\)，每次将所有大于它的数置为1，小于它的数置为0。
接下来？接下来就可以用简化问题的方法判定了！
我们只要转化成01序列之后进行操作，最终\(q\)位置上的是1就满足条件。

2.代码

#define N 1000010
int n,m,num[N],ans,q;
struct Input {
	int l,r,opt;
}in[N];
struct Node {
	int l,r,wei,tag;
}tr[N<<2];
inline void Pushup(int k){
	tr[k].wei=tr[ls].wei+tr[rs].wei;
}
void Build(int k,int l,int r,int limt){
	tr[k].l=l,tr[k].r=r,tr[k].tag=0;
	if(l==r){
		tr[k].wei=num[l]>=limt;
		return;
	}
	Build(ls,l,nmid,limt);
	Build(rs,nmid+1,r,limt);
	Pushup(k);
}
inline void Pushdn(int k){
	if(tr[k].tag){
		tr[ls].tag=tr[rs].tag=tr[k].tag;
		if(tr[k].tag==1){
			tr[ls].wei=tmid-tr[k].l+1;
			tr[rs].wei=tr[k].r-tmid;
		}else tr[ls].wei=tr[rs].wei=0;
		tr[k].tag=0;
	}
}
void Modify(int k,int l,int r,int num){
	if(l<=tr[k].l&&tr[k].r<=r){
		tr[k].wei=num*(tr[k].r-tr[k].l+1);
		tr[k].tag=num?1:-1;
		return;
	}
	Pushdn(k);
	if(l<=tmid)Modify(ls,l,r,num);
	if(tmid