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

rhn7 · 2025-06-07 10:27:31 · 题解

树套树板子题，不会树套树请右转 P2617。

我们发现交换 h_a 和 h_b 其实就是在 a 处删除 h_a，a 处添加 h_b，b 处删除 h_b，b 处添加 h_a。

考虑在 x 处添加 v 对答案的影响（删除同理）：

• 加上区间 [1,x-1] 中数值在 [v+1,10^9] 的个数
• 加上区间 [x+1,n] 中数值在 [1,v-1] 的个数

void up(int x,int v,int p){//p为-1表示删除,p为1表示添加
    add(x,v,p);
    ans+=p*cal(1,x-1,v+1,lg);
    ans+=p*cal(x+1,n,1,v-1);
}

直接上树套树实现这个 add 和 cal，时间复杂度为 O(n\log^2 n)。

关键是树套树自带大常数，咱们还把一次操作拆成四次修改，八次查询，时空都会被卡飞，所以要用一些小寄巧：

• 将 h 数组离散化，这样可以减少线段树递归层数。

• 最开始统计逆序对时不要偷懒树套树，再新开一个权值树状数组。

• 能不开 long long 就不开。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,a,b,g[N],lg,h[N],rt[N],tot;
long long ans;
struct Node{
    int ls,rs,sum;
} t[N<<5];
void update(int &id,int l,int r,int x,int v){
    if(!id) id=++tot;
    t[id].sum+=v;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) update(t[id].ls,l,mid,x,v);
    else update(t[id].rs,mid+1,r,x,v);
}
long long query(int id,int l,int r,int x,int y){
    if(x<=l&&r<=y) return t[id].sum;
    int mid=(l+r)>>1;
    long long res=0;
    if(x<=mid) res+=query(t[id].ls,l,mid,x,y);
    if(y>mid) res+=query(t[id].rs,mid+1,r,x,y);
    return res;
}
void add(int x,int y,int v){
    for(int i=x;i<=n;i+=i&(-i)) update(rt[i],1,lg,y,v);
}
inline int cal(int l,int r,int x,int y){
    if(l>r||x>y) return 0;
    int res=0;
    for(int i=r;i;i-=i&(-i)) res+=query(rt[i],1,lg,x,y);
    for(int i=l-1;i;i-=i&(-i)) res-=query(rt[i],1,lg,x,y);
    return res;
}
inline void up(int x,int v,int p){
    add(x,v,p);
    ans+=p*cal(1,x-1,v+1,lg);
    ans+=p*cal(x+1,n,1,v-1);
}
int c[N];
void add2(int x){
    for(int i=x;i<=lg;i+=i&(-i)) c[i]++;
}
inline int cal2(int x){
    int res=0;
    for(int i=x;i;i-=i&(-i)) res+=c[i];
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        g[++lg]=h[i];
    }
    sort(g+1,g+lg+1);lg=unique(g+1,g+lg+1)-g-1;
    for(int i=1;i<=n;i++){
        h[i]=lower_bound(g+1,g+lg+1,h[i])-g;
        add(i,h[i],1);add2(h[i]);
        ans+=cal2(lg)-cal2(h[i]);
    }
    printf("%lld\n",ans);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&a,&b);
        up(a,h[a],-1);up(a,h[b],1);
        up(b,h[b],-1);up(b,h[a],1);
        swap(h[a],h[b]);
        printf("%lld\n",ans);
    }
    return 0;
}