P2824 排序（二分答案加线段树）

传送门

很巧妙的一个题

直接排序肯定会\(T\)飞

我们发现问题只有一个：第\(q\)个位置上的数字

不难想到从这里入手，二分答案，考虑第\(q\)个位置上的数字是什么，不妨设他为\(x\)

然后把大于等于\(x\)的数变成\(1\)，小于\(x\)的数变为\(0\)，把他转换为一个\(01\)排序问题：

对于区间\([l,r]\)的排序，我们找到\([l,r]\)中有多少个\(1\)，记为\(cnt_1\)，同理记\(cnt_0\)为区间中\(0\)的个数，若其为升序，则令\([l,cnt_0+l-1]\)变为\(0\)，\([r-cnt_1+1,r]\)变为\(1\)，降序同理，令\([l,cnt_1+l-1]\)变为\(1\)，\([r-cnt_0+1,r]\)变为\(0\)。

这样就变成了线段树基操：区间修改，区间查询

时间复杂度：

二分答案\(O(\log n)\)，一次修改\(O(\log n)\)，要修改\(m\)次\(O(m)\)，再加上每次二分答案前初始化\(O(n\log n)\)

总共就是\(O((n+m)\log_2^2 n)\)，可以接受

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50;
ll n,m,q,a[N],b[N];
ll op[N],l[N],r[N];
ll tr[N*16],tag[N*16],cnt0,cnt1;
void BT(ll wz,ll l,ll r)
{
	if(l==r)
	{
		tr[wz]=b[l];
		tag[wz]=-1;
		return ;
	}
	ll mid=(l+r)/2;
	BT(wz*2,l,mid);
	BT(wz*2+1,mid+1,r);
	tr[wz]=tr[wz*2]+tr[wz*2+1];
	tag[wz]=-1;
}
void pushdown(ll wz,ll l,ll r)
{
	ll mid=(l+r)/2;
	tr[wz*2]=(mid-l+1)*tag[wz];
	tr[wz*2+1]=(r-mid)*tag[wz];
	tag[wz*2]=tag[wz];
	tag[wz*2+1]=tag[wz];
	tag[wz]=-1;
}
ll query(ll wz,ll l,ll r,ll le,ll ri)
{
	if(le<=l&&ri>=r) return tr[wz];
	if(tag[wz]!=-1) pushdown(wz,l,r);
	ll mid=(l+r)/2,re=0;
	if(le<=mid) re+=query(wz*2,l,mid,le,ri);
	if(ri>mid) re+=query(wz*2+1,mid+1,r,le,ri);
	return re;
}
void gai(ll wz,ll l,ll r,ll le,ll ri,ll x)
{
	if(le<=l&&ri>=r)
	{
		tr[wz]=(r-l+1)*x;
		tag[wz]=x;
		return ;
	}
	if(tag[wz]!=-1) pushdown(wz,l,r);
	ll mid=(l+r)/2;
	if(le<=mid) gai(wz*2,l,mid,le,ri,x);
	if(ri>mid) gai(wz*2+1,mid+1,r,le,ri,x);
	tr[wz]=tr[wz*2]+tr[wz*2+1];
} 
bool check(ll x)
{
	for(ll i=1;i<=n;i++)
	if(a[i]<x) b[i]=0;
	else b[i]=1;
	BT(1,1,n);
	for(ll i=1;i<=m;i++)
	{
		cnt1=query(1,1,n,l[i],r[i]);
		cnt0=r[i]-l[i]+1-cnt1;
		if(op[i]==0)
		{
			if(cnt0!=0) gai(1,1,n,l[i],l[i]+cnt0-1,0);
			if(cnt1!=0) gai(1,1,n,r[i]-cnt1+1,r[i],1);
		}
		if(op[i]==1)
		{
			if(cnt1!=0) gai(1,1,n,l[i],l[i]+cnt1-1,1);
			if(cnt0!=0) gai(1,1,n,r[i]-cnt0+1,r[i],0);
		}
	}
	ll re=query(1,1,n,q,q);
	if(re==1) return true;
	return false;
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	for(ll i=1;i<=m;i++)
	scanf("%lld %lld %lld",&op[i],&l[i],&r[i]);
	scanf("%lld",&q);
	ll l=1,r=n,mid;
	while(l<r)
	{
		mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%lld\n",l);
	return 0;
}