[HOJ 329] Construct?!

作法：

假設我們交換的兩數分別為$x,y$，那麼對於那些數值不是落在$x,y$之間的數，交換之後並不會影響這些數和$x,y$之間的逆序數對數，不管這些數落在交換的兩位置的左右還是中間。對於那些數值落在$x,y$之間的數，只有當他的位子落在交換的兩數字位置之間才會影響逆序數對的數量。由此就可以推出，我們交換的兩個數一定是左邊大右邊小的，才可以讓交換後逆序數對減少越多。假設交換的兩數位置分別為$i,j$，數字則為$x,y$，那麼逆序數對的變化就會等於$2\times $位子落在$i,j$之間的介於$x,y$之間數的個數$+1$（還要加上交換的兩數形成的逆序數對）。這樣就可以轉化為平面上點集的問題了：把$(i,a[i])$看成座標平面上的點，那麼我們要的就是一個矩形的左上角和右下角，使得這個矩形內包含最多的點。考慮所有「左上方沒有點」的點，那麼不難知道所求矩形的左上角一定是取其中的某個點是最好的。同理所求的右下角是取「右下方沒有點」的點是最好的。我們可以$O(n)$找出所有的這樣的點（之後分別叫他們$X$陣列和$Y$陣列），所以現在我們得到了一個樸素的算法：在這些點之間枚舉左上角和右下角，計算其中包含了多少點。但這樣太慢了，我們反過來考慮一個點對哪些矩形有貢獻，對於某個點$P$，考慮所有落在$P$左上方的$X$陣列中的點，和落在$P$右下方的$Y$陣列中的點，那麼任取前者中的一個點和後者中的一個點形成的矩形都可以包住這個點，因此如果我們幫$X$陣列中的數編號$1,...,n_x$，$Y$陣列則編號$1,...,n_y$，那麼一個矩形就可以表示成一個平面上的點，以左上角的編號和右下角的編號來表示。並且我們把每個矩形內的點數寫在他對應的點上，那麼就可以用以下方式來得到所有點的數值：枚舉每個原題中的點，找出他對哪些矩形有貢獻，而被貢獻的這些矩形們的集合對應到的點就會形成一個矩形區域，並且我們需要把這個矩形區域中的點值都$+1$。於是這樣就轉換為新的問題了：平面上有好幾個矩形，問被最多矩形覆蓋的點被覆蓋了幾次，而這可以用個掃描線來做，只需要維護一個最大值線段樹，並支援區間加值操作就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
struct node
{
    node *l,*r ;
    int val,tag ;
    node(){l=r=NULL ; val=tag=0;}
};
 
node *build(int l,int r)
{
    if(l==r) return new node ;
    node *u=new node() ;
    int mid=(l+r)/2 ;
    u->l=build(l,mid) ;
    u->r=build(mid+1,r) ;
    return u ;
}
 
void push(node *u)
{
    if(!u || !u->tag) return ;
    u->l->val+=u->tag ; u->l->tag+=u->tag ;
    u->r->val+=u->tag ; u->r->tag+=u->tag ;
    u->tag=0 ;
}
void pull(node *u)
{
    u->val=max(u->l->val,u->r->val) ;
}
 
void modify(int l,int r,int L,int R,node *u,int add)
{
    if(l==L && r==R){u->tag+=add ; u->val+=add ; return ;}
    push(u) ;
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,u->l,add) ;
    else if(l>mid) modify(l,r,mid+1,R,u->r,add) ;
    else modify(l,mid,L,mid,u->l,add) ,
        modify(mid+1,r,mid+1,R,u->r,add) ;
    pull(u) ;
}
 
struct event
{
    int t,l,r,add ;
    bool operator < (const event &rhs) const
    {
        return t<rhs.t ;
    }
};
 
int a[maxn] ;
int x[maxn],idx[maxn],y[maxn],idy[maxn] ;
int used[maxn] ;
vector<event> ev ;
main()
{
    int n ;
    while(scanf("%d",&n)!=EOF)
    {
        ev.clear() ;
        fill(used,used+n+1,0) ;
        int cntx=0 , cnty=0 ;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]) ;
            while(cntx && x[cntx-1]>a[i]) cntx-- ;
            x[cntx]=a[i] ; idx[cntx++]=i ;
            if(!cntx || y[cnty-1]<a[i])
                y[cnty]=a[i] , idy[cnty++]=i ;
        }
        if(cnty==n){printf("-1\n") ; continue ;}
        for(int i=0;i<cntx;i++) used[x[i]]=1 ;
        for(int i=0;i<cnty;i++) used[y[i]]=1 ;
        for(int i=1;i<=n;i++) if(!used[a[i]])
        {
            int l1=lower_bound(y,y+cnty,a[i])-y ;
            int r1=lower_bound(idy,idy+cnty,i)-idy-1 ;
            int l2=lower_bound(idx,idx+cntx,i)-idx ;
            int r2=lower_bound(x,x+cntx,a[i])-x-1 ;
            assert(r1>=l1 && r2>=l2) ;
            ev.push_back((event){l1,l2,r2,1}) ;
            ev.push_back((event){r1+1,l2,r2,-1}) ;
        }
        sort(ev.begin(),ev.end()) ;
        node *root=build(0,n-1) ;
        int ans=0 ;
        for(int i=0,j=0;i<n;i++)
        {
            for(;j<ev.size() && ev[j].t<=i;j++)
                modify(ev[j].l,ev[j].r,0,n-1,root,ev[j].add) ;
            ans=max(ans,root->val) ;
        }
        printf("%d\n",2*ans+1) ;
    }
}