The 19th Zhejiang Provincial College Programming Contest 2022 f.easyfix chairman tree

F.Easy Fix

Topic analysis

Given the permutation $p_1,p_2,p_3,\dots ,p_n$, Definition $A_i$ It means that $p_i$ Left side parallel $p_i$ The number of small numbers ,$B_i$ It means that $p_i$ The right side is not bigger than $p_i$ The number of small numbers ,$C_i=\min (A_i,B_i)$. Now, given multiple operations $(l,r)$, Ask for each operation , In exchange for $(p_i,p_j)$ After $\sum C_i$.

First consider how to deal with the initial $C_i$ value , The following properties were observed ：

• about $A_i$ The solution process of value is similar to the idea of finding reverse order pairs , You can maintain the tree array directly ,$O(n\log n)$ Get all $A_i$
• Because it's permutation ,$B_i=p_i-1-A_i$ Sure $O(1)$ Get
• that $C_i=\min (A_i,B_i)$ It's also $O(1)$ Got

Because each inquiry is independent , Then consider exchanging $(p_l,p_r)$ Operation of $C_i$ Influence ：

• about $[1,l),(r,n]$ Number of ranges ,$C_i$ Value must not affect . Because the switching operation is carried out on one side

• about $p_l$, Exchange to $r$ After the position ,$A_l\to A_l+Districtbetween[l,r]SmallOn{p}_{l}OfCountwordindividualCount$,$B_l’$ You can still ask directly

  about $p_r$, Exchange to $l$ After the position ,$A_r\to A_r-Districtbetween[l,r]SmallOn{p}_{r}OfCountwordindividualCount$,$B_r’$ You can still ask directly

  If we ask online ( Chairman tree maintenance ), So for $p_l,p_r$, In fact, it can be directly two $O(logn)$ Ask again .

• So the point is for $[l+1,r-1]$ The number in the interval $C_i$ Value change , How to maintain ？

• about $p_l\le p_i\le p_r$, If $A_i\le B_i$, After exchange $A_i-1,B_i+1$, thus $C_i-1$

  about $p_l\ge p_i\ge p_r$, If $A_i\ge B_i$, After exchange $A_i+1,B_i-1$, thus $C_i-1$

• about $p_l\le p_i\le p_r$, If $A_i-1\ge B_i+1,A_i\ge B_i$, After exchange $C_i+1$

  about $p_l\ge p_i\ge p_r$, If $A_i-1\le B_i+1,A_i\le B_i$, After exchange $C_i+1$

So for the above four cases , We can use four chairman trees for maintenance . meanwhile , about $p_l,p_r$ The contribution calculation of also needs to support the interval $<K$ Number of numbers query , Therefore, a total of five chairman trees are required for maintenance , Complexity $O(m\times 4\log n)$.

Code

#include <bits/stdc++.h>
#define int long long 
#define endl '\n'


const int N = 1e5 + 10;
int p[N], a[N], b[N], c[N], d[N];

using bset5 = std::bitset<5>;

namespace Fenwick{
    
    int tree[N], len;
    #define lowbit(x) ((x) & (-x))

    inline void init(int ln){
     len = ln; }
    inline void update(int i, int x){
     for(int pos = i; pos <= len; pos += lowbit(pos)) tree[pos] += x; }
    inline int getsum(int i, int ans = 0){
     for(int pos = i; pos; pos -= lowbit(pos)) ans += tree[pos]; return ans; }
}

namespace PresidentTree{
    
    int root[N], sum[N << 5][5], lc[N << 5], rc[N << 5], cnt;
    #define ls l, mid
    #define rs mid + 1, r

    void update(int &rt, int pre, int l, int r, int x, bset5 inc){
    
        rt = ++cnt, lc[rt] = lc[pre], rc[rt] = rc[pre];
        for(int i = 0; i <= 5; i++) sum[rt][i] = sum[pre][i] + (inc[i] ? 1 : 0);
        if(l == r) return;
        int mid = l + r >> 1;
        if(x <= mid) update(lc[rt], lc[rt], l, mid, x, inc);
        else update(rc[rt], rc[rt], mid + 1, r, x, inc);
    }

    int query(int st, int ed, int l, int r, int L, int R, int id){
    
        if(l == L && r == R) return sum[ed][id] - sum[st][id];
        int mid = l + r >> 1;
        if(mid >= R) return query(lc[st], lc[ed], l, mid, L, R, id);
        else if(mid >= L) return query(lc[st], lc[ed], l, mid, L, mid, id) + query(rc[st], rc[ed], mid + 1, r, mid + 1, R, id);
        else return query(rc[st], rc[ed], mid + 1, r, L, R, id);
    }

}

#define Pdt PresidentTree

inline void solve(){
    
    int n = 0; std::cin >> n;
    Fenwick::init(n);
    for(int i = 1; i <= n; i++) std::cin >> p[i];
    for(int i = 1; i <= n; i++){
    
        a[i] = Fenwick::getsum(p[i]);
        b[i]= p[i] - 1 - a[i];
        Fenwick::update(p[i], 1);
        c[i] = std::min(a[i], b[i]);
        d[i] = d[i - 1] + c[i];
    }
    for(int i = 1; i <= n; i++){
    
        bset5 flag; flag.reset();
        if(a[i] <= b[i]) flag[1] = true;
        if(a[i] >= b[i]) flag[3] = true;
        if(a[i] - 1 >= b[i] + 1 && a[i] >= b[i]) flag[2] = true;
        if(a[i] + 1 <= b[i] - 1 && a[i] <= b[i]) flag[4] = true;
        flag[0] = true;
        Pdt::update(Pdt::root[i], Pdt::root[i - 1], 1, n + 1, p[i], flag);
    }
    int m = 0; std::cin >> m;
    while(m--){
    
        int l, r; std::cin >> l >> r;
        if(l == r){
     std::cout << d[n] << endl; continue; }
        else if(l > r) std::swap(l, r);
        int ans = d[n] - c[l] - c[r];
        if(p[l] < p[r]){
    
            ans -= Pdt::query(Pdt::root[l], Pdt::root[r - 1], 1, n + 1, p[l], p[r], 1) 
                 - Pdt::query(Pdt::root[l], Pdt::root[r - 1], 1, n + 1, p[l], p[r], 2);
        } else {
    
            ans -= Pdt::query(Pdt::root[l], Pdt::root[r - 1], 1, n + 1, p[r], p[l], 3) 
                 - Pdt::query(Pdt::root[l], Pdt::root[r - 1], 1, n + 1, p[r], p[l], 4);
        }
        int nowa = Pdt::query(Pdt::root[0], Pdt::root[l - 1], 1, n + 1, 1, p[r], 0), 
            nowb = p[r] - 1 - nowa;
        ans += std::min(nowa, nowb);
        nowa = Pdt::query(Pdt::root[r], Pdt::root[n], 1, n + 1, 1, p[l], 0), 
        nowb = p[l] - 1 - nowa;
        ans += std::min(nowa, nowb);
        std::cout << ans << endl;
    }
}

signed main(){
    
    std::ios_base::sync_with_stdio(false), std::cin.tie(0);
    solve();
    return 0;
}