第 19 届 浙江省赛 补题 F

F. Easy Fix

先通过树状数组计算出初始的 $a,b,c$，对于查询 $l,r$ 。我们显然可以发现这样的操作对 $[1,l-1] \land [r+1,r]$ 无影响的。而对于区间 $[l + 1, r - 1]$ 如果 $i \in [l + 1, r - 1]$ ，呢么$max(p[l], p[r]) < p[i]\ \land\ min(p[l], p[r]) > p[i]$ 也显然是没有影响的，因为交换并不会影响 $a[i]$ 和 $b[i]$ 的值。

对于其他情况，我们只要维护每一个位置的三种状态就可以了

• $min(a[i] , b[i] )$ 这是对于移动没有影响的情况
• $min(a[i] - 1, b[i] + 1)$ 这是对于 $p[l] < p[r]$ ，把区间 $[l + 1, r - 1]$ 中 $p[i]$ 处于 $[p[l] + 1,p[r] - 1]$ 的 $c$ 值重新计算，相当于把左侧的一个合法数移动到了右侧，但是移动到左侧的新数并不合法，所以 $a[i] - 1,b[i] + 1$ 。
• $min(a[i] + 1, b[i]-1)$ 同理，这个是在 $p[l] > p[r]$ 的情况

查询历史状态用主席树维护即可

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define endl '\n'
#define lc(x) tr[x].ch[0] 
#define rc(x) tr[x].ch[1] 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) 
using namespace std ;
const int N = 1e6 + 10 ;
typedef array <int,4> Q;
int T = 1 ;
int ans = 0 ;
int p[N] ;
int n, q ;
int a[N], b[N], c[N] ;
int pre[N] ;
struct quer
{
    int u, v ;
    int id ;
};

struct node
{
    int ch[2] ;
    int val[4] ;
}tr[N*2];
int idx ;
int root[N] ;
void build(int & u,int l ,int r){//初始化主席树
    u = idx ++ ;
    tr[u] = {l,r,0} ;
    if(l == r) return ; 
    int mid = l + r >> 1 ;
    build(lc(u), l, mid) ;
    build(rc(u), mid + 1, r) ;
}

void insert2(int x ,int &y,int l, int r,int val, const Q & arr){//创建新的主席树
    y = ++ idx ;
    tr[y] = tr[x] ;
    for(int i = 0 ; i < 4 ; ++ i){
        tr[y].val[i] += arr[i] ; 
    }
    if(l == r) return ;
    int mid = l + r >> 1 ;
    if(val <= mid) insert2(lc(x), lc(y), l , mid , val, arr) ;
    else insert2(rc(x),rc(y), mid + 1, r, val, arr) ;
}
int querry2(int y, int x,int l,int r, int ll,int rr ,int tp){//求此时val的前缀和
    if(l >= ll && r <= rr){
        return tr[x].val[tp] - tr[y].val[tp] ;
    }
    int mid = l + r >> 1 ;
    int sum = 0 ;
    // cout << l << " " << r << " " << ll << " " << rr << endl ;
    if(ll <= mid) sum += querry2(lc(y), lc(x), l, mid, ll, rr, tp) ;
    if(rr > mid)  sum += querry2(rc(y), rc(x), mid + 1, r, ll, rr, tp) ;
    return sum ;
}
//树状数组
int tree[N] ;
int lowbit(int x){
    return x & -x ;
}
void insert(int x,int val){
    while(x <= n){
        tree[x] += val ;
        x += lowbit(x) ;
    }
}
int querry(int x){
    int res = 0 ;
    while(x){
        res += tree[x] ;
        x -= lowbit(x) ;
    }
    return res ;
}
void solve(){   
    cin >> n ;
    for(int i = 1; i <= n ; ++ i) cin >> p[i] ;
    for(int i = 1; i <= n ; ++ i){
        int num1 = querry(p[i]) ;
        a[i] = num1 ;
        int num2 = i - 1  - num1 ; //在这个位置之前比当前书大的数的数量
        b[i] = p[i] - 1 - num1 ;
        insert(p[i],1) ;
    }
    int sum = 0 ;
    for(int i = 1; i <= n ; ++ i){
        c[i] = min(a[i], b[i]) ;
        pre[i] = pre[i-1] + c[i] ;
        sum += c[i] ;
    }
    build(root[0], 1, n) ;
    for(int i = 1 ; i <= n ; ++ i){
        insert2(root[i-1], root[i],1,n,p[i],{1,min(a[i], b[i]), min(a[i] - 1, b[i] + 1), min(a[i] + 1, b[i] - 1)}) ;
    }
    cin >> q ;
    int u, v ;
    int id = 0 ;
    while(q --){
        cin >> u >> v ;
        if(u == v){
            cout << sum << endl ;
            continue ; 
        }
        if(u > v) swap(u, v) ;
        int res = sum - (pre[v] - pre[u-1]) ; 
        int res1 = 0 ;
        if(1 <= p[u]-1)res1 = querry2(root[0], root[v], 1, n, 1, p[u]-1,0) ;//u交换位置之后
        int uvc = min(res1, p[u] - 1 - res1) ;
        int res2 = 0 ;
        if(1 <= p[v]-1)res2 = querry2(root[0], root[u-1], 1, n, 1, p[v]-1,0) ;//v交换位置之后
        int vuc = min(res2, p[v] - 1 - res2) ;
        res += uvc + vuc ;
        if(p[u] < p[v]){
            if( 1 <= p[u]-1 ) res += querry2(root[u] , root[v-1], 1, n, 1, p[u]-1,1) ;//p[l]和 p[r] 都比 x 大
            if(p[v]+1 <= n) res += querry2(root[u] , root[v-1], 1, n, p[v]+1, n,1) ;//p[l]和 p[r] 都比 x 小
            if(p[u]+1 <= p[v]-1) res += querry2(root[u] , root[v-1], 1, n, p[u]+1, p[v]-1,2) ;

        }else{
            if( 1 <= p[v]-1 )res += querry2(root[u] , root[v-1], 1, n, 1, p[v]-1,1) ;
            if( p[u]+1 <= n )res += querry2(root[u] , root[v-1], 1, n, p[u]+1, n,1) ;
            if( p[v]+1 <= p[u]-1 )res += querry2(root[u] , root[v-1], 1, n, p[v]+1, p[u]-1,3) ;
        }
        cout << res << endl ;
    }
}
signed main(){
    IOS ;
    // cin >> T ;
    while(T--){
        solve() ;
    }

}