题目描述
Hercier 作为一位喜爱 Hatsune Miku 的 OIer，痛下决心，将 Vocaloid 买回了家。打开之后，你发现界面是一个长为 n 的序列，代表音调，并形成了全排列。你看不懂日语，经过多次尝试，你只会用一个按钮：将一段区间按升序排序。不理解音乐的 Hercier 决定写一个脚本，进行 m 次操作，每次对一段区间进行操作。可惜 Hercier 不会写脚本，他找到了在机房里的你，请你模拟出最后的结果。
输入格式
第一行两个整数 $n, m, L, R$，$n\leq 1500, m\leq 1 \times 10^6$。
接下来一行 $n$ 个数，表示每个位置的音调 $a_i$。然后 $m$ 行，每行两个数 $l_i, r_i$,表示操作的区间为 $[l_i, r_i]$。
输出格式
一行 $R-L+1$ 个数，表示最终序列的 $a_L, a_{L+1}, \cdots, a_R$。
思路
这道题前 20% 数据可以直接暴力模拟；
另有 50% 数据 $L=R$，可以二分答案，线段树对 01序列排序，直接求出这个点的数值；
对于 100% 的数据：
我们发现对于一个全排列，排序的一个优秀的方法是交换相邻的逆序对。因为逆序对个数的上限是 $\Theta(n^2)$，我们对于每次操作在区间内暴力交换相邻的逆序对即可，每一次交换最多产生两个新的逆序对。用 $std::set$ 维护所有相邻逆序对的位置，每次操作不断在区间内二分查找逆序对，交换对应的 $a$，然后插入新增的逆序对即可。
时间复杂度 $\Theta((n^2+m)\log n)$。
代码
（感觉不需要放代码啊 233）
（这道题作为本场模拟赛的 T3，代码量小的惊人，倒是前 $70%$ 更加难打 233）
前 70%
#include <bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define len (r-l+1)
#define maxn 1000000
#define maxm 1000000
using namespace std;
int t[maxn<<2],lazy[maxn<<2];
int a[maxn],n;
void Pushup(int p){t[p]=t[ls]+t[rs];}
void Pushdown(int l,int r,int p){
int lp=lazy[p];lazy[p]=-1;
lazy[ls]=lazy[rs]=lp;
t[ls]=lp*(mid-l+1);
t[rs]=lp*(r-mid);
}
void Build(int l,int r,int v,int p){
lazy[p]=-1;
if (l==r){t[p]=(a[l]>=v?1:0);return;}
Build(l,mid,v,ls),Build(mid+1,r,v,rs);
Pushup(p);
}
void Update(int l,int r,int L,int R,int v,int p){
if (l>R||r<L) return;
if (l>=L&&r<=R){t[p]=len*v;lazy[p]=v;return;}
if (lazy[p]!=-1) Pushdown(l,r,p);
Update(l,mid,L,R,v,ls),Update(mid+1,r,L,R,v,rs);
Pushup(p);
}
int Query(int l,int r,int L,int R,int p){
if (l>R||r<L) return 0;
if (l>=L&&r<=R) return t[p];
if (lazy[p]!=-1) Pushdown(l,r,p);
return Query(l,mid,L,R,ls)+Query(mid+1,r,L,R,rs);
}
int opl[maxn],opr[maxn],m,L,R,pos;
void Rough(){
for (register int i=1;i<=m;++i)
std::sort(a+opl[i],a+opr[i]+1);
for (register int i=L;i<=R;++i)
printf("%d ",a[i]);
}
int main(){
freopen("miku.in","r",stdin);
freopen("miku.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&L,&R);
for (register int i=1;i<=n;++i)
scanf("%d",a+i);
for (register int i=1;i<=m;++i)
scanf("%d%d",opl+i,opr+i);
if (L!=R&&m<6000) {Rough();return 0;}
else if (L==R) pos=L;
int l=1,r=n,ans;
while(l<=r){
int val=mid;
memset(t,0,sizeof(t));
Build(1,n,val,1);
for (register int i=1;i<=m;i++){
int c=Query(1,n,opl[i],opr[i],1);
if (!c||opr[i]-opl[i]+1==c) continue;
Update(1,n,opl[i],opr[i]-c,0,1);
Update(1,n,opr[i]-c+1,opr[i],1,1);
}
if (Query(1,n,pos,pos,1)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d ",ans);
}
正解
#include <bits/stdc++.h>
#define maxn 2010
int n,m,l,r,L,R,a[maxn];
std::set<int>s;
int main(){
scanf("%d%d%d%d",&n,&m,&L,&R);
for (register int i=1;i<=n;++i)
scanf("%d",a+i);
for (register int i=1;i<n;++i)
if (a[i+1]<a[i]) s.insert(i);
for (register int i=1;i<=m;++i){
scanf("%d%d",&l,&r);
int t=*s.lower_bound(l);
while(t>=l&&t<r){
a[t]^=a[t+1]^=a[t]^=a[t+1];
if (a[t-1]>a[t]) s.insert(t-1);
if (a[t+1]>a[t+2]) s.insert(t+1);
s.erase(t);
t=*s.lower_bound(l);
}
}
for (register int i=L;i<=R;++i)
printf("%d ",a[i]);
}