Vijos 1893. 簽到題

Brief description:

給定一個數組,你必須交換其中的兩個數,最小化逆序對數。。

https://vijos.org/p/1893

Analysis:

題目來源:http://www.ioi-jp.org/joi/2012/2013-ho/
問題 5:http://www.ioi-jp.org/joi/2012/2013-ho/2013-ho-t5-review.pdf

離線 + 線段樹。
要點是數形結合。。一圖流:

。。。交換兩個數(前者比後者大)所獲得的收益。。是 2*矩形中的面積)+ 1*邊界的面積 + 1。。。(先不考慮邊界)。。

問題現在便轉化為檢查這些極大子矩形。。。

什麼是極大子矩形呢?再來一張圖:

極大子矩形一定是某個赤點和右下角的某個青點所組成的圖形。。。
於是我們將點集(事件)分成三類。。赤點和藍點都單調遞增。。因此從左到右掃描線。、、記錄每個事件離散化後的縱坐標。。

  • 赤點(左上角):。。。在線段樹中激活這個坐標。。
  • 黑點(其他):。。加入這個事件。。將線段樹中這個點坐標到最近激活赤點 += 2.。。
  • 青點(右下角):。。。彈出所有縱坐標小於它的黑點(優先隊列維護)。。區間求最值。。。

只需要區間加減,區間求最值。。線段樹即可。。。
最後還要討論各種邊界的情況。。。
假設所有數都一樣。。返回 0 。。。否則求出初始的逆序對 init_ans。。如果存在兩個數相等。那麼初始答案是 init_ans。。否則是 init_ans – 1。。

再討論矩形的邊界問題:
對於上邊界:
。。當插入一個黑點時。。實際和這個黑點相等的那個坐標只能 += 1。。。
對於下邊界:
。。當出現青點時。不僅要彈出所有小於它的黑點。。還要【消弱】等於它的黑點 -= 1。。。


//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
int a[N]; VI P; bool red[N], blue[N];
int n;

namespace ST{
#define lx (x<<1)
#define rx (lx|1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
#define rt 1, 1, P.size()


    int T[4*N], D[4*N], a, b, d, ll, rr;

    void upd(int x){
        T[x] = max(T[lx], T[rx]);
    }

    void inc(int x, int d){
        D[x] += d;
        T[x] += d;
    }

    void rls(int x){
        if (D[x]){
            inc(lx, D[x]), inc(rx, D[x]);
            D[x] = 0;
        }
    }

    void add(int x, int l, int r){
        if (b < l || r < a) return;
        if (a <= l && r <= b){
            inc(x, d);
        }
        else{
            rls(x);
            add(lc); add(rc);
            upd(x);
        }
    }

    void Add(int _a, int _b, int _d){
        a = _a, b = _b, d = _d; add(rt);
    }

    int query(int x, int l, int r){
        if (b < l || r < a) return 0;
        if (a <= l && r <= b){
            return T[x];
        }
        else{
            rls(x);
            return max(query(lc), query(rc));
        }
    }

    int query(){
        a = ll+1, b = rr; int z = a <= b ? query(rt) : 0; ++z;
        return z;
    }
}

namespace BIT{
    int C[N], n;
    int Sum(int x){
        int z=0; for (;x;x^=low_bit(x)) z += C[x];
        return z;
    }
    void Add(int x, int d){
        for(;x<=n;x+=low_bit(x)) C[x] += d;
    }
    int Sum(int l, int r){
        return Sum(r) - Sum(l-1);
    }
} //using namespace BIT;


struct black{
    int l, r;
    black(int _l, int _r):l(_l),r(_r){
    }
    bool operator <(const black& rhs) const{
        return l < rhs.l;
    }
    bool operator >(const black& rhs) const{
        return l > rhs.l;
    }
    void add() const{
        ST::Add(l, r, 2);
        ST::Add(l, l, -1);
    }
    void del() const{
        ST::Add(l, r, -2);
    }
    void weak() const{
        ST::Add(l, r, -1);
    }
};

priority_queue<black, vector<black>, greater<black> > Q;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP_C(i, RD(n)) P.PB(RD(a[i])); UNQ(P);

    BIT::n = P.size();

    LL init_ans = 0; bool same = 0, all_same = 1; REP(i, n){
        a[i] = LBD(P, a[i])+1;
        init_ans += i - BIT::Sum(a[i]);
        same |= (BIT::Sum(a[i]) - BIT::Sum(a[i]-1));
        all_same &= (!i || a[i] == a[i-1]);
        BIT::Add(a[i], 1);
    }

    if (all_same){
        puts("0");
        exit(0);
    }

    LL ans = init_ans + 1; if (same) --ans;

    int t = 0; REP(i, n){
        red[i] = checkMax(t, a[i]);
    }

    t = INF; DWN(i, n, 0){
        blue[i] = checkMin(t, a[i]);
    }

    ST::ll = 0, ST::rr = -1;

    REP(i, n){
        if (red[i]){
            ST::rr = a[i];
        }
        else if (blue[i]){

            while (!Q.empty() && Q.top().l < a[i]){
                Q.top().del();
                Q.pop();
            }

            vector<black> QQ;

            while (!Q.empty() && Q.top().l == a[i]){
                Q.top().weak(); QQ.PB(Q.top()); Q.pop();
            }
            ST::ll = a[i];
            checkMin(ans, init_ans - (ST::query()));
            ECH(it, QQ) it->weak();
        }
        else{
            black t = black(a[i], ST::rr);
            Q.push(t); t.add();
        }
    }

    OT(ans);
}