The 19th Zhejiang Provincial Collegiate Programming Contest 2022浙江省赛 F.EasyFix 主席树

F.Easy Fix

题目分析

给定排列$p_1,p_2,p_3,\dots ,p_n$，定义$A_i$表示在$p_i$左侧并比$p_i$小的数字个数，$B_i$表示在$p_i$右侧并比$p_i$小的数字个数，$C_i=\min (A_i,B_i)$。现在给定多个操作$(l,r)$，求每个操作，交换$(p_i,p_j)$后的$\sum C_i$。

首先考虑如何处理初始时的$C_i$值，观察到以下性质：

• 对于$A_i$值的求解过程类似求逆序对的思想，可以直接上树状数组维护，$O(n\log n)$求得全部的$A_i$
• 由于是排列，$B_i=p_i-1-A_i$可以$O(1)$求得
• 那么$C_i=\min (A_i,B_i)$也是$O(1)$得到的

由于每个询问相互独立，那么考虑交换$(p_l,p_r)$操作对$C_i$的影响：

• 对于$[1,l),(r,n]$范围的数字，$C_i$值一定不影响。因为交换操作均在单侧进行

• 对于$p_l$，交换到$r$位置后，$A_l\to A_l+区间[l,r]小于p_l的数字个数$，$B_l’$仍然可以直接求

  对于$p_r$，交换到$l$位置后，$A_r\to A_r-区间[l,r]小于p_r的数字个数$，$B_r’$仍然可以直接求

  如果我们在线询问(主席树维护)，那么对于$p_l,p_r$，实际上可以直接两个$O(logn)$重新求。

• 那么重点是对于$[l+1,r-1]$区间内的数字的$C_i$值变化，如何维护？

• 对于$p_l\le p_i\le p_r$，如果$A_i\le B_i$，则交换后$A_i-1,B_i+1$，从而$C_i-1$

  对于$p_l\ge p_i\ge p_r$，如果$A_i\ge B_i$，则交换后$A_i+1,B_i-1$，从而$C_i-1$

• 对于$p_l\le p_i\le p_r$，如果$A_i-1\ge B_i+1,A_i\ge B_i$，则交换后$C_i+1$

  对于$p_l\ge p_i\ge p_r$，如果$A_i-1\le B_i+1,A_i\le B_i$，则交换后$C_i+1$

那么对于以上四种情况，我们可以分别用四棵主席树进行维护。同时，对于$p_l,p_r$的贡献计算还需要支持区间$<K$的数字个数查询，因此共需五棵主席树进行维护，复杂度$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;
}