P2824 [HEOI2016/TJOI2016] 排序-526互联

针对区间排序，显然能够上值域线段树类似，但这里有个更强的做法。
如果能转化成01序列，那么一个区间排序的时候，只需区间询问1的个数+区间修改就可以了。
因为是排列，很清晰的二分一个mid，把大于等于它的设为1，小于它的设为0，再跑上面的算法，最后check一下询问位置是否为1即可。
单调性？感性理解，假设 \(mid1<mid2\) 且 \(mid2\) 返回的是true，那么 \(mid1\) 只会让限制更加宽泛，所以一定返回的是true，那么一定能找到一个 \(mid\) 使得它和它前面的返回是true，它后面的都是 false

#include<bits/stdc++.h>

#define maxn 100005 

using namespace std;

bool Mbg;

template<class T>
  
inline T read(){
	T r=0,f=0;
    char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r*10)+(c^48),c=getchar();
	return f?-r:r;
}

int n,m,q;

int a[maxn];

struct QUERY{
	int opt,l,r;
}query[maxn];

int num;

namespace SGT{
	
#define lson cur<<1
#define rson cur<<1|1
	
	int tree[maxn<<2],tag[maxn<<2];
	
	inline void pushup(int cur){
		tree[cur]=tree[lson]+tree[rson];
	}

	void build(int cur,int lt,int rt){
		tag[cur]=-1;
		if(lt==rt){
			tree[cur]=(a[lt]>=num);
			return;
		}
		int mid=(lt+rt)>>1;
		build(lson,lt,mid);
		build(rson,mid+1,rt);
		pushup(cur);
	}

	inline void addtag(int cur,int lt,int rt,int val){
		tag[cur]=val;
		tree[cur]=(rt-lt+1)*val;
	}

	inline void pushdown(int cur,int lt,int rt){
		if(tag[cur]==-1)return;
		int mid=(lt+rt)>>1;
		addtag(lson,lt,mid,tag[cur]);
		addtag(rson,mid+1,rt,tag[cur]);
		tag[cur]=-1;
	}

	void update(int cur,int lt,int rt,int qx,int qy,int val){
		if(rt<qx||lt>qy)return;
		if(lt>=qx&&rt<=qy){
			addtag(cur,lt,rt,val);
			return;
		}
		pushdown(cur,lt,rt);
		int mid=(lt+rt)>>1;
		update(lson,lt,mid,qx,qy,val);
		update(rson,mid+1,rt,qx,qy,val);
		pushup(cur);
	}

	int ask(int cur,int lt,int rt,int qx,int qy){
		if(rt<qx||lt>qy)return 0;
		if(lt>=qx&&rt<=qy)return tree[cur];
		pushdown(cur,lt,rt);
		int mid=(lt+rt)>>1;
	    return ask(lson,lt,mid,qx,qy)+ask(rson,mid+1,rt,qx,qy);
	}
	
#undef lson
#undef rson
	
}

inline bool check(){
	SGT::build(1,1,n);
	for(int i=1;i<=m;i++){
		if(query[i].opt==0){
			int len=SGT::ask(1,1,n,query[i].l,query[i].r);
			SGT::update(1,1,n,query[i].r-len+1,query[i].r,1);
			SGT::update(1,1,n,query[i].l,query[i].r-len,0);
		}
		else{
			int len=SGT::ask(1,1,n,query[i].l,query[i].r);
			SGT::update(1,1,n,query[i].l+len,query[i].r,0);
			SGT::update(1,1,n,query[i].l,query[i].l+len-1,1);
		}
	}
	return SGT::ask(1,1,n,q,q);
}

bool Med;

int main(){
    double Mb=(&Mbg-&Med)/1e6;
	fprintf(stderr,"%.2lfMB\n",Mb=Mb<0?-Mb:Mb);
	if(Mb>256)fprintf(stderr,"MLE!!!\n");
	n=read<int>();
	m=read<int>();
	for(int i=1;i<=n;i++)
		a[i]=read<int>();
	for(int i=1;i<=m;i++){
		query[i].opt=read<int>();
		query[i].l=read<int>();
		query[i].r=read<int>();
	}
	q=read<int>();
	int lt=0,rt=n+1;
	while(lt+1<rt){
		int mid=(lt+rt)>>1;
		num=mid;
		if(check())lt=mid;
		else rt=mid;
	}
	printf("%d\n",lt);
	return 0;
}

2016

P2824