P1975 [国家集训队]排队 树套树

题意：

戳这里

分析：

• 暴力

每次交换之后，(nlog) 的求逆序对，复杂度 (O(mnlog))

• 正解

我们发现每次交换 (l) 和 (r) 的时候，影响的区间只有 ([l,r])

具体来说 (Delta = sum_{i=l+1}^{r-1} [a_i>a_l]+sum_{i=l+1}^{r-1} [a_i>a_r]-sum_{i=l+1}^{r-1}[a_i<a_l]-sum_{i=l+1}^{r-1}[a_i>a_r])

也就是是说我们需要一个数据结构支持，区间查询一个区间内元素的个数，并单点修改

对于这种区间套区间的问题，我们可以用树套树解决

第一层的区间查询可以用树状数组来实现，第二层上动态开点值域线段树

tip:

1. 需要特判 (l) 和 (r) 两个点的大小是否会带来新的逆序对

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	int read()
	{
		int x=0,f=1;char ch=getchar();
		while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
		while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 2e4+5;
	int cnt,n,m,len,ans;
	int a[maxn],root[maxn],b[maxn];
	
	struct tree
	{
		int lc,rc,w;
	}t[maxn<<7];
	
	int lowbit(int x)
	{
		return x&(-x);
	}
	
	int build()
	{
		int now=++cnt;
		t[now].lc=t[now].rc=t[now].w=0;
		return now;
	}
	
	void pushup(int rt)
	{
		t[rt].w=t[t[rt].lc].w+t[t[rt].rc].w;
	}
	
	void update(int &rt,int l,int r,int pos,int val)
	{
		if(!rt) rt=build();
		if(l==r)
		{
			t[rt].w+=val;
			return ;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) update(t[rt].lc,l,mid,pos,val);
		else update(t[rt].rc,mid+1,r,pos,val);
		pushup(rt);
	}
	
	int query(int rt,int l,int r,int ql,int qr)
	{
		if(!rt||ql>r||qr<l) return 0;
		if(ql<=l&&r<=qr) return t[rt].w;
		int mid=(l+r)>>1;
		return query(t[rt].lc,l,mid,ql,qr)+query(t[rt].rc,mid+1,r,ql,qr);
	}
	
	void tree_update(int rt,int pos,int val)
	{
		for(;rt<=n;rt+=lowbit(rt)) update(root[rt],1,len,pos,val);
	}
	
	int tree_query(int l,int r,int ql,int qr)
	{
		int res=0;
		for(;r;r-=lowbit(r)) res+=query(root[r],1,len,ql,qr);
		for(l--;l;l-=lowbit(l)) res-=query(root[l],1,len,ql,qr);
		return res;
	}
	
	void work()
	{
		int l,r;
		n=read();
		for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
		sort(b+1,b+n+1);
		len=unique(b+1,b+n+1)-b-1;
		for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b,tree_update(i,a[i],1);
		for(int i=2;i<=n;i++) ans+=tree_query(1,i-1,a[i]+1,len);
		printf("%d
",ans);
		m=read();
		while(m--)
		{
			l=read();r=read();
			if(l>r) swap(l,r);
			ans-=tree_query(l+1,r-1,1,a[l]-1);
			ans+=tree_query(l+1,r-1,1,a[r]-1);
			ans-=tree_query(l+1,r-1,a[r]+1,len);
			ans+=tree_query(l+1,r-1,a[l]+1,len);
			if(a[l]<a[r]) ans++;
			if(a[l]>a[r]) ans--;
			tree_update(l,a[l],-1);
			tree_update(l,a[r],1);
			tree_update(r,a[r],-1);
			tree_update(r,a[l],1);
			swap(a[l],a[r]);
			printf("%d
",ans);
		}
	}
	
}

int main()
{
	zzc::work();
	return 0;
}