题解：P12685 [国家集训队] 排队 加强版

vanueber · 2025-06-20 13:12:54 · 题解

题目分析

有 m 次操作，每次交换两个数，求出交换后的逆序对数。

先离散化，然后考虑在线地维护这个过程。假设我们交换了 l,r(l<r) 两个位置，那么它对答案的影响就是：

发现这是求区间排名问题。

同时交换操作需要我们支持单点修改。

这是一个经典的树套树问题，可以采用树状数组套线段树或者线段树套平衡树，这里采用简洁的分块套树状数组。

时间复杂度 \Theta(n \sqrt n \log n)。

Code

#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=2e5+10,T=ceil(sqrt(N));
int n,h[N],tmp[N],cnt,m;
int len,tot,st[T],ed[T],bel[N];
struct bit{
    int tr[N];
    int lowbit(int x){
        return x&-x;
    }
    void add(int x,int k){
        for(;x<=cnt+1;x+=lowbit(x)) tr[x]+=k;
    }
    int query(int x){
        int res=0;
        for(;x>0;x-=lowbit(x)) res+=tr[x];
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
    void change(int x,int k){
        add(x,-query(x,x));
        add(x,k);
    }
}t[T];
ll ans;
int query(int l,int r,int x,int y){
    int res=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;++i) res+=(h[i]>=x&&h[i]<=y);
    }
    else{
        for(int i=l;i<=ed[bel[l]];++i) res+=(h[i]>=x&&h[i]<=y);
        for(int i=st[bel[r]];i<=r;++i) res+=(h[i]>=x&&h[i]<=y);
        for(int i=bel[l]+1;i<bel[r];++i) res+=t[i].query(x,y);
    }
    return res;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    n=read();
    rep(i,1,n) tmp[++cnt]=h[i]=read();
    sort(tmp+1,tmp+cnt+1);
    cnt=unique(tmp+1,tmp+cnt+1)-tmp-1;
    rep(i,1,n) h[i]=lower_bound(tmp+1,tmp+cnt+1,h[i])-tmp;
    rep(i,1,n){
        ans+=t[0].query(h[i]+1,cnt);
        t[0].add(h[i],1);
    }
    cout<<ans<<endl;
    len=sqrt(n),tot=(n+len-1)/len;
    rep(i,1,n) bel[i]=(i-1)/len+1;
    rep(i,1,tot){
        st[i]=(i-1)*len+1,ed[i]=min(n,i*len);
        for(int j=st[i];j<=ed[i];++j) t[i].add(h[j],1);
    }
    cin>>m;
    for(int i=1,l,r;i<=m;++i){
        // print();
        l=read(),r=read();
        if(r<l) swap(l,r);
        if(r!=l+1){
            ans-=query(l+1,r-1,1,h[l]-1);
            ans-=query(l+1,r-1,h[r]+1,cnt);
        }
        if(h[l]<h[r]) ++ans;
        else if(h[l]>h[r]) --ans;
        t[bel[l]].add(h[l],-1),t[bel[l]].add(h[r],1);
        t[bel[r]].add(h[r],-1),t[bel[r]].add(h[l],1);
        swap(h[l],h[r]);
        if(r!=l+1){
            ans+=query(l+1,r-1,1,h[l]-1);
            ans+=query(l+1,r-1,h[r]+1,cnt);
        }
        // print();
        cout<<ans<<endl;
    }
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

本题坑点

1. 题目不保证询问的 l < r。
2. 注意到交换的影响的式子中，必须要将 l,r 两个单点的贡献分开算，直接算可能会算重。