【JZOJ A组】初音未来

Description

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

Input

Output

Sample Input

5 2 1 5
5 1 4 2 3
1 3
2 4

样例2
见下发文件

Sample Output

1 2 4 5 3

样例解释：

Data Constraint

思路

一个序列的逆序对最多总共有O(n²)个，每次交换一个逆序对个数一定会减少一个。

所以我们可以考虑不停地交换相邻的逆序对，每次交换看一下相邻的是否会在相邻的位置产生逆序对，然后加入队列

逆序对的位置随便拿一个数据结构即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
set<int> s;
int n,m,L,R,a[1577];
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]);
	for(int i=1; i<=n-1; i++)
	{
		if(a[i]>a[i+1]) s.insert(i);
	}
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		set<int>::iterator t=s.lower_bound(l);
		while(*t<r)
		{
			int p=*t;
			swap(a[p],a[p+1]); s.erase(p);
			if(a[p-1]>a[p]) s.insert(p-1);
			if(a[p+1]>a[p+2]) s.insert(p+1);
			t=s.lower_bound(l);
		}
	}
	for(int i=L; i<=R; i++) printf("%d ",a[i]);
}