#树状数组套线段树#洛谷 1975 [国家集训队]排队

题目

有(n)个数，(m)次询问每次交换其中两个数问逆序对个数
(nleq 2*10^4,mleq 2*10^3)

---

分析

若交换的两个数位置为(l,r(l<r))，则([1,l))和((r,n])是不受影响的
那么只需要求((l,r))内(>a[l],<a[l],>a[r],<a[r])的个数就可以了，
因为带修，所以用树套树去做

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=20011;
int n,ans,w[N<<7],ls[N<<7],m,cnt,rs[N<<7],rt[N],a[N],b[N];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
inline void update(int &k,int l,int r,int x,int y){
	if (!k) k=++cnt; w[k]+=y;
	if (l==r) return;
	rr int mid=(l+r)>>1;
	if (x<=mid) update(ls[k],l,mid,x,y);
	    else update(rs[k],mid+1,r,x,y);
}
inline signed query(int k,int l,int r,int x,int y){
	if (!k) return 0;
	if (l==x&&r==y) return w[k];
	rr int mid=(l+r)>>1;
	if (y<=mid) return query(ls[k],l,mid,x,y);
	else if (x>mid) return query(rs[k],mid+1,r,x,y);
	else return query(ls[k],l,mid,x,mid)+query(rs[k],mid+1,r,mid+1,y);
}
inline signed QQuery(int x){
	rr int ans=0;
	for (;x;x-=-x&x) ans+=rt[x];
	return ans;
}
inline void UUpdate(int x){
	for (;x<=m;x+=-x&x) ++rt[x];
}
inline void Update(int x,int y,int z){
	for (;x<=n;x+=-x&x) update(rt[x],1,m,y,z);
}
inline signed Query(int l,int r,int x,int y){
	rr int ans=0;
	for (;r;r-=-r&r) ans+=query(rt[r],1,m,x,y);
	for (;l;l-=-l&l) ans-=query(rt[l],1,m,x,y);
	return ans;
}
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i) b[i]=a[i]=iut();
	sort(b+1,b+1+n),m=unique(b+1,b+1+n)-b-1;
	for (rr int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	for (rr int i=n;i;--i) ans+=QQuery(a[i]-1),UUpdate(a[i]);
	for (rr int i=1;i<=m;++i) rt[i]=0; print(ans),putchar(10);
	for (rr int i=1;i<=n;++i) Update(i,a[i],1);
	for (rr int Q=iut();Q;--Q,putchar(10)){
		rr int l=iut(),r=iut();
		if (l>r) l^=r,r^=l,l^=r;
		if (l+1<r){
			if (a[l]>1) ans-=Query(l,r-1,1,a[l]-1);
			if (a[r]>1) ans+=Query(l,r-1,1,a[r]-1);
			if (a[l]<m) ans+=Query(l,r-1,a[l]+1,m);
			if (a[r]<m) ans-=Query(l,r-1,a[r]+1,m);
		}
		Update(l,a[l],-1),Update(l,a[r],1);
		Update(r,a[r],-1),Update(r,a[l],1);
		ans+=(a[l]<a[r])-(a[l]>a[r]),
		print(ans),swap(a[l],a[r]);
	}
	return 0;
}