题解：P7629 [COCI 2011/2012 #1] SORT

· · 题解

题目跳楼机

正文开始

阅读理解

有 n 个数，从前往后扫，将每一个最长单调下降连续子序列翻转，扫到头后再从头开始扫，求翻转次数。

思路

这道题卡了我挺久的，原因就出在这一句话上：“保证在第一次划分时每个 slope 的长度都为偶数” 这一句话很关键，但我当时没看到。

那么这么一句不起眼的话有什么用呢？稍微模拟一下我们可以发现，有了这个条件的限制，那么在第一次翻转后，剩下的所有单调下降的连续子序列的长度要么为 2，要么为 1，这也就说明每一次翻转都是在交换相邻的两个数，那么就转化为了经典的求冒泡排序的交换次数，就可以直接用树状数组或者归并排序求逆序对的个数了。

代码

由于本蒟蒻不会树状数组，于是用的线段树代替。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[1000005],ans;
int t[1000005];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
inline void push_up(int p){t[p]=t[ls(p)]+t[rs(p)];}
inline void update(int id,int p,int pl,int pr){
    if(pl==pr&&pl==id){t[p]++;return ;}
    int mid=pl+pr>>1;
    if(id<=mid)update(id,ls(p),pl,mid);
    else update(id,rs(p),mid+1,pr);
    push_up(p);
}
inline int query(int L,int R,int p,int pl,int pr){
    if(L>R)return 0;
    if(L<=pl&&pr<=R)return t[p];
    int mid=pl+pr>>1,res=0;
    if(L<=mid)res+=query(L,R,ls(p),pl,mid);
    if(R>mid)res+=query(L,R,rs(p),mid+1,pr);
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    a[n+1]=INT_MAX;
    int cnt=1;
    for(int i=2;i<=n+1;i++){//先按照题意模拟一次 
        if(a[i]>=a[i-1]){
            if(cnt>1){
                for(int j=i-cnt,k=i-1;j<k;j++,k--)swap(a[j],a[k]);
                ans++;
            }
            cnt=1;
        }
        else cnt++;
    }
    update(a[n],1,1,n);//预处理最后一个数 
    for(int i=n-1;i;i--){
        ans+=query(1,a[i]-1,1,1,n);//查找在  i 之后有多少个小于 a[i] 的数，计入贡献 
        update(a[i],1,1,n);
    }
    cout<<ans;
    return 0;
}