P2824 [HEOI2016/TJOI2016] 排序

很巧妙的思路。最终求的是一个位置上的值，考虑一个暴力的思路，因为是排列所以可以考虑枚举答案是哪个，然后关注答案这个数的位置变化，如果经过所有操作后这个数的位置就是所求的

q

，那它就是答案。

所以我们可以发现，计算答案不需要知道每个数字的位置，只需要知道我们所枚举的数的最终位置就好了，但好像不排序就无法维护它的位置，又很矛盾。

考虑如何使一些不同大小的数在某种情况下等价，这样排序的意义就是针对我们所求的数字的了，在意义上不冗余后，还要把这个意义设计得足够广泛以使尽量多的元素等价，这样就方便排序了。

注意到当我们枚举答案时，所有大于这个数的其他数是同一个意义，而所有小于它的数也是同一个意义，所以把大于它的数全换成1，小于它的数全换成-1，自己是0，可以很大程度上缩减排序成本，但依旧需要枚举。

其实只差一点，因为对于只有0，1的序列的排序是简单的，可以用线段树很轻松维护，这提示我们能不能把当前枚举的答案和0或1等价，使排序简化。

这里假设和1等价，等价了的话我们关注的最终意义本来是所枚举的数的最终位置，因为我们不再知道这个数的具体位置，所以我们真正知道的是

\ge

这个数的所有数载最后的分布位置，而如果我们枚举的数

\le

最终答案，那么所求位置

q

上的数一定是

1

，这么一看，居然有了单调性，果断二分，

check

函数模拟以某个值为键值将所有数划分为两个意义（0,1）后模拟所有排序操作，最后返回

q

上值是否为

1

，是就往上继续二分。

复杂度

O(n\log^2{n})

CPP

#include<bits/stdc++.h>
using namespace std;
#define IR(u,l,r) l<=tree[u].l&&tree[u].r<=r
#define MAXN 100010
struct node{
	int l,r;
	int val,tag;
}tree[MAXN<<2];
int n,m,q,a[MAXN],p[MAXN];
void pushup(int u)
{
	tree[u].val=tree[u*2].val+tree[u*2+1].val;
}
void maketag(int u,int x)
{
	tree[u].val=(tree[u].r-tree[u].l+1)*x;
	tree[u].tag=x;
}
void pushdown(int u)
{
	if(tree[u].tag==-1)
		return;
	maketag(u*2,tree[u].tag);
	maketag(u*2+1,tree[u].tag);
	tree[u].tag=-1;
}
void build(int u,int l,int r)
{
	tree[u].l=l,tree[u].r=r;
	tree[u].tag=-1;
	if(l==r){
		tree[u].val=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}
void update(int u,int l,int r,int x)
{
	if(l>r)return;
	if(IR(u,l,r))
		maketag(u,x);
	else{
		pushdown(u);
		int mid=(tree[u].l+tree[u].r)/2;
		if(l<=mid)update(u*2,l,r,x);
		if(r>mid)update(u*2+1,l,r,x);
		pushup(u);
	}
}
int query(int u,int l,int r)
{
	if(IR(u,l,r))
		return tree[u].val;
	else{
		pushdown(u);
		int mid=(tree[u].l+tree[u].r)/2;
		int ans=0;
		if(l<=mid)ans+=query(u*2,l,r);
		if(r>mid)ans+=query(u*2+1,l,r);
		return ans;
	}
}
int l[MAXN],r[MAXN],opt[MAXN];
int check(int x)
{
	for(int i=1;i<=n;i++)
		a[i]=p[i]>=x;
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int sum=query(1,l[i],r[i]);
		if(opt[i]==0){
			update(1,l[i],r[i]-sum,0);
			update(1,r[i]-sum+1,r[i],1);
		}else{
			update(1,l[i],l[i]+sum-1,1);
			update(1,l[i]+sum,r[i],0);
		}
	}
	return query(1,q,q);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&opt[i],&l[i],&r[i]);
	scanf("%d",&q);
	int l=1,r=n,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))
			ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

P2824 [HEOI2016/TJOI2016] 排序

文章操作

P2824 [HEOI2016/TJOI2016] 排序

相关推荐

评论

P2824 [HEOI2016/TJOI2016] 排序