【Fortuna OJ 5947】初音未来 / 题解

题目描述

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]);
}
Show Comments