loj_535 花火

题目:

   「Hanabi, hanabi……」
   一听说祭典上没有烟火,Karen 一脸沮丧。
   「有的哦…… 虽然比不上大型烟花就是了。」
   还好 Shinobu 早有准备,Alice、Ayaya、Karen、Shinobu、Yoko 五人又能继续愉快地玩耍啦!
   「噢……!不是有放上天的烟花嘛!」Karen 兴奋地喊道。
   「啊等等……」Yoko 惊呼。Karen 手持点燃引信的烟花,「嗯??」
   Yoko 最希望见到的是排列优美的烟火,当然不会放过这个机会…… 不过时间似乎已经不多了。

   个烟火排成一排,从左到右高度分别为 ,这些高度两两不同。
   每次 Yoko 可以选择两个相邻的烟火交换,这样的交换可以进行任意多次。
   每次 Yoko 还可以选择两个不相邻的烟火交换,但这样的交换至多进行一次。
   你的任务是帮助 Yoko 用最少次数的交换,使这些烟火从左到右的高度递增。

思路:

   如果没有不相邻的交换,那么答案就是逆序对的个数。那么考虑枚举不相邻交换的两个数。显然交换的两个点 要满足 ,不然逆序对个数只会变大。那么逆序对减少的个数就是满足 个数的两倍加一(加一来自 )。如果把 看做点对,那么这就是一个二维数点问题,只要预处理一个前缀就能 查询了。
   既然可以看做点对,那么考虑把这些点画在坐标轴上,那么问题就变成了选择两个点,使这两个点组成的矩形能框住的点最多(不包括边线上的点,如下图就是 个)。
     
   试着在这个模型中发现性质,显然被选为最优解的左上角的点左上方一定没有其他点(不然那个点更优),同理右下方的点也是同样的。所以可以处理出这两个点集,显然它们分别组成了一条始终向右上方的曲线。
   观察发现在这条曲线选取点是单调的,设 为左上方第 个点选中的点,那么
   假设它不单调,那么就会出现下图的情况:
     
   而因为黑色点没有选中左侧的点,也就是说下图中紫色面积大于粉色面积。
     
   因为每个区域的值都是非负的,这就和上图冲突了。 是单调的。那么可以分治找最大值,主席树实现二维数点。复杂度

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int N=300005;

void read(int &a){
    char c;
    for(c=getchar();!isdigit(c);c=getchar());
    for(a=0;isdigit(c);c=getchar())
        a=(a<<1)+(a<<3)+c-'0';
}

ll merge(int l,int r,int a[]){
    static int t[N];
    if(l==r)return 0;
    int mid=l+r>>1;
    ll ans=merge(l,mid,a)+merge(mid+1,r,a);
    int i=l,j=mid+1,tot=l;
    while(i<=mid&&j<=r)
        if(a[i]<a[j])t[tot++]=a[i++];
        else t[tot++]=a[j++],ans+=(mid-i+1);
    while(i<=mid)t[tot++]=a[i++];
    while(j<=r)t[tot++]=a[j++];
    rep(i,l,r)a[i]=t[i];
    return ans;
}

int sum[N*20],ls[N*20],rs[N*20],tot;
#define mid (L+R>>1)
#define lson ls[o],L,mid
#define rson rs[o],mid+1,R
void upd(int x,int &o,int L,int R){
    ls[++tot]=ls[o];rs[tot]=rs[o];
    sum[tot]=sum[o]+1;o=tot;
    if(L==R)return;
    if(x<=mid)upd(x,lson);
    else upd(x,rson);
}
int qry(int l,int r,int o,int L,int R){
    if(!o)return 0;
    if(l==L&&r==R)return sum[o];
    if(r<=mid)return qry(l,r,lson);
    else if(l>mid)return qry(l,r,rson);
    else return qry(l,mid,lson)+qry(mid+1,r,rson);
}
#undef mid
#undef lson
#undef rson

int a[N],t[N],rt[N],n;
struct Point{
    int x,y;
}p[N],u[N],d[N];

int calc(Point a,Point b){
    if(a.x==b.x&&a.y==b.y)return 0;
    return qry(b.y,a.y,rt[b.x],1,n)-qry(b.y,a.y,rt[a.x-1],1,n)-2;
}
int val[N];
void solve(int l,int r,int lc,int rc){
    int mid=l+r>>1,id;
    val[mid]=-1;
    rep(i,lc,rc)
        if(tomax(val[mid],calc(u[mid],d[i])*2+1))
            id=i;
    if(mid>l)solve(l,mid-1,lc,id);
    if(r>mid)solve(mid+1,r,id,rc);
}

int main(){
    read(n);
    rep(i,1,n){
        read(a[i]);
        upd(a[i],rt[i]=rt[i-1],1,n);
        t[i]=a[i];p[i]=(Point){i,a[i]};
    }
    ll ans=merge(1,n,t);
    int cntu=0,cntd=0;
    u[++cntu]=p[1];
    rep(i,2,n)
        if(p[i].y>u[cntu].y)
            u[++cntu]=p[i];
    d[++cntd]=p[n];
    drep(i,n-1,1)
        if(p[i].y<d[cntd].y)
            d[++cntd]=p[i];
    rep(i,1,cntd/2)
        std::swap(d[i],d[cntd-i+1]);
    solve(1,cntu,1,cntd);
    ll tmp=ans;
    rep(i,1,cntu)
        tomin(ans,tmp-val[i]+1);
    printf("%lld\n",ans);
    return 0;
}