「Luogu2824」[HEOI2016/TJOI2016]排序

妙
真的妙

题目描述

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

输入格式：

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5，1 <= m <= 10^5

输出格式：

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

输入样例#1：

6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

输出样例#1：

说明

河北省选2016第一天第二题。原题的时限为6s，但是洛谷上是1s，所以洛谷的数据中，对于30%的数据，有 n,m<=1000,对于100%的数据，有 n,m<=50000

Solution

$O(nm\log n)$ ？
emmmmm

由于最后才有一个询问，考虑离线

我们可以二分最终 $q$ 位置上的值 $ans$ 是什么

然后把序列中大于等于 $ans$ 的值设为 $1$ ，小于 $ans$ 的值设为 $0$

于是每次排序操作相当于区间覆盖，可以用线段树实现

最后Check一下 $q$ 位置上是 $0$ 还是 $1$ ，进一步二分即可

时间复杂度 $O(m\log^2n)$

Code

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#define maxn 30005
#define maxm 30005
using namespace std;
typedef long long ll;
//1:>=mid 0:<mid

int n,m,Q;
int a[maxn];

struct querys
{
	int op,l,r;
}q[maxm];

struct node
{
	int cnt1,l,r,lazy;
}t[maxn*4];

void maintain(int num)
{
	t[num].cnt1=t[num*2].cnt1+t[num*2+1].cnt1;
}

void pushdown(int num)
{
	if(t[num].lazy==1)
		t[num*2].cnt1=t[num*2].r-t[num*2].l+1,t[num*2+1].cnt1=t[num*2+1].r-t[num*2+1].l+1;
	if(t[num].lazy==0)
		t[num*2].cnt1=t[num*2+1].cnt1=0;
	if(t[num].lazy!=2)
		t[num*2].lazy=t[num*2+1].lazy=t[num].lazy;
	t[num].lazy=2;
}

void Build(int l,int r,int num,int x)
{
	t[num].l=l;
	t[num].r=r;
	t[num].lazy=2;
	if(l==r)
	{
		t[num].cnt1=(a[l]>=x);
		return;
	}
	int mid=(l+r)/2;
	Build(l,mid,num*2,x);
	Build(mid+1,r,num*2+1,x);
	maintain(num);
}

void Change(int l,int r,int num,int c)
{
	if(t[num].l>r || t[num].r<l)
		return;
	if(l<=t[num].l && r>=t[num].r)
	{
		t[num].cnt1=c*(t[num].r-t[num].l+1);
		t[num].lazy=c;
		return;
	}
	pushdown(num);
	Change(l,r,num*2,c);
	Change(l,r,num*2+1,c);
	maintain(num);
}

int Query(int l,int r,int num)
{
	if(t[num].l>r || t[num].r<l)
		return 0;
	if(l<=t[num].l && r>=t[num].r)
		return t[num].cnt1;
	pushdown(num);
	return Query(l,r,num*2)+Query(l,r,num*2+1);
}

bool Check(int x)
{
	Build(1,n,1,x);
	for(register int i=1;i<=m;++i)
	{
		int k=Query(q[i].l,q[i].r,1);
		if(q[i].op==0)
		{
			Change(q[i].l,q[i].r-k,1,0);
			Change(q[i].r-k+1,q[i].r,1,1);
		}
		else
		{
			Change(q[i].l,q[i].l+k-1,1,1);
			Change(q[i].l+k,q[i].r,1,0);
		}
	}
	return Query(Q,Q,1);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for(register int i=1;i<=m;++i)
		scanf("%d%d%d",&q[i].op,&q[i].l,&q[i].r);
	scanf("%d",&Q);
	register int l=1,r=n;
	int ans;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(Check(mid))
			ans=mid,l=mid+1;
		else
			r=mid-1;
	}
	printf("%d",ans);
	return 0;
}