交换两个数的位置，只有位于两个数之间的部分会受到影响，因此只需要考虑两个数之间有多少数对a[l]和a[r]产生的贡献发生了变化即可。
感觉像是个带修改的二维偏序问题。(修改点$(x,y)$的值，维护和查询位于$(x_1,y_1)$与$(x_2,y_2)$之间的点的个数)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+,inf=0x3f3f3f3f;
int n,m,n2,rt[N<<],ls[N*],rs[N*],sum[N*],tot,a[N],b[N],ans;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
void upd2(int p,int x,int& u,int l=,int r=n2) {
if(!u)u=++tot;
sum[u]+=x;
if(l==r)return;
p<=mid?upd2(p,x,ls[u],l,mid):upd2(p,x,rs[u],mid+,r);
}
int qry2(int L,int R,int& u,int l=,int r=n2) {
if(l>=L&&r<=R)return sum[u];
if(l>R||r<L)return ;
return qry2(L,R,ls[u],l,mid)+qry2(L,R,rs[u],mid+,r);
}
void upd(int p,int x,int dx,int u=,int l=,int r=n) {
upd2(x,dx,rt[u]);
if(l==r)return;
p<=mid?upd(p,x,dx,lson,l,mid):upd(p,x,dx,rson,mid+,r);
}
int qry(int L,int R,int L2,int R2,int u=,int l=,int r=n) {
if(l>=L&&r<=R)return qry2(L2,R2,rt[u]);
if(l>R||r<L)return ;
return qry(L,R,L2,R2,lson,l,mid)+qry(L,R,L2,R2,rson,mid+,r);
}
int main() {
scanf("%d",&n);
for(int i=; i<=n; ++i)scanf("%d",&a[i]);
for(int i=; i<=n; ++i)b[i]=a[i];
sort(b+,b++n),n2=unique(b+,b++n)-(b+);
for(int i=; i<=n; ++i)a[i]=lower_bound(b+,b++n2,a[i])-b;
for(int i=; i<=n; ++i)ans+=qry(,n,a[i]+,n2),upd(i,a[i],);
printf("%d\n",ans);
scanf("%d",&m);
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
if(l>r)swap(l,r);
if(l==r||a[l]==a[r]);
else {
if(a[l]<a[r])ans+=qry(l+,r-,a[l]+,a[r])+qry(l+,r-,a[l],a[r]-)+;
else ans-=qry(l+,r-,a[r]+,a[l])+qry(l+,r-,a[r],a[l]-)+;
upd(l,a[l],-),upd(l,a[r],);
upd(r,a[r],-),upd(r,a[l],);
swap(a[l],a[r]);
}
printf("%d\n",ans);
}
return ;
}
还有理论上能够AC的线段树套treap的版本，可惜常数太大TLE了~QAQ~
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+,inf=0x3f3f3f3f;
int n,m,n2,rt[N<<],ch[N*][],val[N*],siz[N*],rd[N*],tot,a[N],b[N],ans;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}
int newnode(int x) {int u=++tot; ch[u][]=ch[u][]=,siz[u]=,val[u]=x,rd[u]=rand(); return u;}
void rot(int& u,int f) {
int v=ch[u][f];
ch[u][f]=ch[v][f^],ch[v][f^]=u;
pu(u),pu(v),u=v;
}
void ins(int& u,int x) {
if(!u) {u=newnode(x); return;}
int f=x>val[u];
ins(ch[u][f],x);
if(rd[ch[u][f]]>rd[u])rot(u,f);
if(u)pu(u);
}
void del(int& u,int x) {
if(!u)return;
if(val[u]==x) {
if(!ch[u][]||!ch[u][])u=ch[u][]|ch[u][];
else {
int f=rd[ch[u][]]>rd[ch[u][]];
rot(u,f),del(ch[u][f^],x);
}
} else del(ch[u][x>val[u]],x);
if(u)pu(u);
}
int lb(int u,int x) {
int ret=;
for(; u; u=ch[u][x>val[u]])if(val[u]>=x)ret=val[u];
return ret;
}
int ub(int u,int x) {
int ret=;
for(; u; u=ch[u][x>=val[u]])if(val[u]>x)ret=val[u];
return ret;
}
int rnk(int u,int x) {
int ret=;
for(; u; u=ch[u][x>val[u]])if(x>val[u])ret+=siz[ch[u][]]+;
return ret+;
}
int sum(int u,int l,int r) {return l>r?:rnk(u,ub(u,r))-rnk(u,lb(u,l));}
void upd(int p,int x,int dx,int u=,int l=,int r=n) {
dx==?ins(rt[u],x):del(rt[u],x);
if(l==r)return;
p<=mid?upd(p,x,dx,lson,l,mid):upd(p,x,dx,rson,mid+,r);
}
int qry(int L,int R,int L2,int R2,int u=,int l=,int r=n) {
if(l>=L&&r<=R)return sum(rt[u],L2,R2);
if(l>R||r<L)return ;
return qry(L,R,L2,R2,lson,l,mid)+qry(L,R,L2,R2,rson,mid+,r);
}
void build(int u=,int l=,int r=n) {
ins(rt[u],~inf),ins(rt[u],inf);
if(l==r)return;
build(lson,l,mid),build(rson,mid+,r);
}
int main() {
srand(time());
scanf("%d",&n);
for(int i=; i<=n; ++i)scanf("%d",&a[i]);
for(int i=; i<=n; ++i)b[i]=a[i];
sort(b+,b++n),n2=unique(b+,b++n)-(b+);
for(int i=; i<=n; ++i)a[i]=lower_bound(b+,b++n2,a[i])-b;
build();
for(int i=; i<=n; ++i)ans+=qry(,n,a[i]+,n2),upd(i,a[i],);
printf("%d\n",ans);
scanf("%d",&m);
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
if(l>r)swap(l,r);
if(l==r||a[l]==a[r]);
else {
if(a[l]<a[r])ans+=qry(l+,r-,a[l]+,a[r])+qry(l+,r-,a[l],a[r]-)+;
else ans-=qry(l+,r-,a[r]+,a[l])+qry(l+,r-,a[r],a[l]-)+;
upd(l,a[l],-),upd(l,a[r],);
upd(r,a[r],-),upd(r,a[l],);
swap(a[l],a[r]);
}
printf("%d\n",ans);
}
return ;
}
后续：我把treap的区间求和方式改了稍微改了一下，卡时过掉了~~
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+,inf=0x3f3f3f3f;
int n,m,n2,rt[N<<],ch[N*][],val[N*],siz[N*],rd[N*],tot,a[N],b[N],ans;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}
int newnode(int x) {int u=++tot; ch[u][]=ch[u][]=,siz[u]=,val[u]=x,rd[u]=rand(); return u;}
void rot(int& u,int f) {
int v=ch[u][f];
ch[u][f]=ch[v][f^],ch[v][f^]=u;
pu(u),pu(v),u=v;
}
void ins(int& u,int x) {
if(!u) {u=newnode(x); return;}
int f=x>val[u];
ins(ch[u][f],x);
if(rd[ch[u][f]]>rd[u])rot(u,f);
if(u)pu(u);
}
void del(int& u,int x) {
if(!u)return;
if(val[u]==x) {
if(!ch[u][]||!ch[u][])u=ch[u][]|ch[u][];
else {
int f=rd[ch[u][]]>rd[ch[u][]];
rot(u,f),del(ch[u][f^],x);
}
} else del(ch[u][x>val[u]],x);
if(u)pu(u);
}
int lb(int u,int x) {
int ret=;
for(; u; u=ch[u][x>val[u]])if(x>val[u])ret+=siz[ch[u][]]+;
return ret;
}
int ub(int u,int x) {
int ret=;
for(; u; u=ch[u][x>=val[u]])if(x>=val[u])ret+=siz[ch[u][]]+;
return ret;
}
int sum(int u,int l,int r) {return ub(u,r)-lb(u,l);}
void upd(int p,int x,int dx,int u=,int l=,int r=n) {
dx==?ins(rt[u],x):del(rt[u],x);
if(l==r)return;
p<=mid?upd(p,x,dx,lson,l,mid):upd(p,x,dx,rson,mid+,r);
}
int qry(int L,int R,int L2,int R2,int u=,int l=,int r=n) {
if(l>=L&&r<=R)return sum(rt[u],L2,R2);
if(l>R||r<L)return ;
return qry(L,R,L2,R2,lson,l,mid)+qry(L,R,L2,R2,rson,mid+,r);
}
int main() {
srand(time());
scanf("%d",&n);
for(int i=; i<=n; ++i)scanf("%d",&a[i]);
for(int i=; i<=n; ++i)b[i]=a[i];
sort(b+,b++n),n2=unique(b+,b++n)-(b+);
for(int i=; i<=n; ++i)a[i]=lower_bound(b+,b++n2,a[i])-b;
for(int i=; i<=n; ++i)ans+=qry(,n,a[i]+,n2),upd(i,a[i],);
printf("%d\n",ans);
scanf("%d",&m);
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
if(l>r)swap(l,r);
if(l==r||a[l]==a[r]);
else {
if(a[l]<a[r])ans+=qry(l+,r-,a[l]+,a[r])+qry(l+,r-,a[l],a[r]-)+;
else ans-=qry(l+,r-,a[r]+,a[l])+qry(l+,r-,a[r],a[l]-)+;
upd(l,a[l],-),upd(l,a[r],);
upd(r,a[r],-),upd(r,a[l],);
swap(a[l],a[r]);
}
printf("%d\n",ans);
}
return ;
}