JZOJ5947. 【NOIP2018模拟11.02】初音未来（miku）

题意：

$Hercier$Hercier作为一位喜爱$Hatsune Miku$HatsuneMiku的$OIer$OIer，痛下决心，将$Vocaloid$Vocaloid买回了家。打开之后，你发现界面是一个长为$n$n的序列，代表音调，并形成了全排列。你看不懂日语，经过多次尝试，你只会用一个按钮：将一段区间按升序排序。不理解音乐的$Hercier$Hercier决定写一个脚本，进行$m$m次操作，每次对一段区间进行操作。可惜$Hercier$Hercier不会写脚本，他找到了在机房里的你，请你模拟出最后的结果。

数据范围：

Analysis：

看这数据范围就知道复杂度跟$n$n有很大关系。
每一次对区间排序，实际上不管怎么样排，总的排序次数是不变的。考虑这样的排序，每次交换一对相邻的数，其满足$a_i>a_{i+1}$ai​>ai+1​。不难发现这样的排序次数是$n^2$n2级别的，因为逆序对个数最多为$n*(n-1)/2$n∗(n−1)/2个。因为每一次对区间排序实际上就是对区间内每一个数执行这个操作，和对整个序列排序没有本质区别，我们只要维护$a_i>a_{i+1}$ai​>ai+1​的位置即可，用$set$set去维护，每一次找到最靠近$l$l的地方暴力修改，复杂度$O((n^2+m)\log{n})$O((n2+m)logn)

Code：

# include<cstdio>
# include<cstring>
# include<algorithm>
# include<set>
using namespace std;
# define ins insert
const int N = 2e3 + 5;
set <int> q;
set <int>::iterator it;
int a[N];
int n,m,L,R;
int main()
{
	freopen("miku.in","r",stdin);
	freopen("miku.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&L,&R);
	for (int i = 1 ; i <= n ; ++i) { scanf("%d",&a[i]); if (a[i - 1] > a[i]) q.ins(i - 1); }
	while (m--)
	{
		int l,r; scanf("%d%d",&l,&r);
		it = q.lower_bound(l);
		while (it != q.end() && (*it) < r)
		{
			it = q.lower_bound(l); int p = *it;
			q.erase(it); swap(a[p],a[p + 1]);
			if (a[p + 1] > a[p + 2]) q.ins(p + 1);
			if (a[p - 1] < a[p + 1] && a[p - 1] > a[p]) q.ins(p - 1);
			it = q.lower_bound(l);
		}
	}
	for (int i = L ; i <= R ; ++i) printf("%d ",a[i]);
	return 0;
}