JZOJ-senior-5947. 【NOIP2018模拟11.02】初音未来（miku）

本文主要是介绍JZOJ-senior-5947. 【NOIP2018模拟11.02】初音未来（miku），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Time Limits: 1000 ms Memory Limits: 524288 KB

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

在这里插入图片描述

Solution

逆序对个数最多 $\frac{n(n-1)}{2}$
在 $n < = 1500$ 时有效的交换次数不会太多
一个序列每次交换相邻两个数排序直到顺序排列的最小次数就是逆序对个数
所以我们只需要记录下形成逆序对的位置
对于每次操作，在区间中找到有逆序对的地方暴力交换
再记录下新形成的逆序对，直到当前操作区间中不存在逆序对
这个只需要线段树上打上0/1标记，二分出逆序对的位置进行操作即可

Code

#include<algorithm>
#include<cstdio>#define fo(i,a,b) for(int i=a;i<=b;++i)using namespace std;const int N=1505;
int n,m,L,R,l,r,a[N],t[4*N];void ins(int x,int l,int r,int p,int k)
{if(l==r) {t[x]=k; return;}int mid=(l+r)>>1;if(p<=mid) ins(x+x,l,mid,p,k);else ins(x+x+1,mid+1,r,p,k);t[x]=t[x+x]+t[x+x+1];
}int get(int x,int st,int en,int l,int r)
{if(l>r) return 0;if(!t[x]) return 0;if(st==en) return st;int mid=(st+en)>>1;if(r<=mid){if(t[x+x]) return get(x+x,st,mid,l,r);}else if(l>mid){if(t[x+x+1]) return get(x+x+1,mid+1,en,l,r);}else{int p1=get(x+x,st,mid,l,mid);if(p1) return p1;int p2=get(x+x+1,mid+1,en,mid+1,r);return p2;}
}int main()
{freopen("miku.in","r",stdin);freopen("miku.out","w",stdout);scanf("%d%d%d%d",&n,&m,&L,&R);fo(i,1,n){scanf("%d",&a[i]);if(a[i]<a[i-1]) ins(1,1,n,i,1);}fo(i,1,m){scanf("%d%d",&l,&r);int pos=-1;while(pos){pos=get(1,1,n,l+1,r);if(!pos) break;swap(a[pos-1],a[pos]);ins(1,1,n,pos,0);if(pos-2>0&&a[pos-2]>a[pos-1]) ins(1,1,n,pos-1,1);if(pos+1<=n&&a[pos+1]<a[pos]) ins(1,1,n,pos+1,1);}}fo(i,L,R) printf("%d ",a[i]);
}