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

· · 题解

哈哈哈是 cdq 分治板子。

就是当成三元组 (t,p,k)，表示操作时间，位置，值，树状数组就可以 O(n\log^2 n) 咯。

感觉其它高级数据结构都没有 cdq 分治直接明了，清晰简单。

交换就是删除再加入，很无脑。

这题还是太经典了，不想写得太水。

虽然随便写都是 2s 以内，但还是可以提供卡常小技巧。

由于树状数组带点常数，我开的分界点是 100。

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define OK y^fa&&!vis[y]
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
using namespace std;
const int N=1e6+5;
int n,m,a[N],lsh[N],b[N],ln,g;
ll out[N];
struct node{
    int ty,p,k,id;
}q[N];
inline bool cmp(node a,node b){
    return a.p<b.p;
}
int t[N];
inline void ad(int x,int k){
    while(x<=ln)t[x]+=k,x+=x&-x;
}
inline int query(int x){
    int ans=0;
    while(x)ans+=t[x],x-=x&-x;
    return ans;
}
inline void clear(int x){
    while(x<=ln)t[x]=0,x+=x&-x;
}
inline void cdq(int l,int r){
    if(l>=r)return;
    cdq(l,mid),cdq(mid+1,r);
    if(r-l+1<=100){
        rep(i,l,mid)rep(j,mid+1,r){
            if(q[i].p<q[j].p)out[q[j].id]+=(q[i].k>q[j].k)*q[i].ty*q[j].ty;
            if(q[i].p>q[j].p)out[q[j].id]+=(q[i].k<q[j].k)*q[i].ty*q[j].ty;
        }
        return;
    }

    sort(q+l,q+mid+1,cmp),sort(q+mid+1,q+r+1,cmp);
    int Ll=l;
    rep(Rr,mid+1,r){
        while(Ll<=mid&&q[Ll].p<q[Rr].p)ad(q[Ll].k,q[Ll].ty),Ll++;
        out[q[Rr].id]+=q[Rr].ty*(query(ln)-query(q[Rr].k));
    }
    rep(i,l,Ll-1)clear(q[i].k);
    Ll=mid;
    per(Rr,r,mid+1){
        while(Ll>=l&&q[Ll].p>q[Rr].p)ad(q[Ll].k,q[Ll].ty),Ll--;
        out[q[Rr].id]+=q[Rr].ty*query(q[Rr].k-1);
    }
    rep(i,Ll+1,mid)clear(q[i].k);
}
inline void Main(){
    n=read();
    repn(i)lsh[i]=a[i]=read();
    sort(lsh+1,lsh+n+1);
    repn(i)if(lsh[i]^lsh[i+1])b[++ln]=lsh[i];
    repn(i)a[i]=lower_bound(b+1,b+ln+1,a[i])-b;
    m=read();
    repn(i)q[++g]={1,i,a[i],0};
    repm(i){
        int x=read(),y=read();
        q[++g]={-1,x,a[x],i},q[++g]={-1,y,a[y],i},q[++g]={1,x,a[y],i},q[++g]={1,y,a[x],i},swap(a[x],a[y]);
    }
    cdq(1,g);
    repm(i)out[i]+=out[i-1];
    rep(i,0,m)printf("%lld\n",out[i]);
}
signed main(){
    int T=1;
    while(T--)Main();
    return 0;
}