【BZOJ2141】排队（树套树）

题面

BZOJ

洛谷

题解

傻逼题啊。。。

裸的树套树

树状数组套线段树，每次交换的时候，考虑一下前后的贡献，先删掉贡献，再重新算一遍就好了。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 22222

#define lb(x) (x&(-x))

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int len,S[MAX],a[MAX],n,Q;

struct Node{int ls,rs,v;}t[MAX<<8];

int rt[MAX],tot;

void Modify(int &x,int l,int r,int p,int w)

{

	if(!x)x=++tot;t[x].v+=w;

	if(l==r)return;

	int mid=(l+r)>>1;

	if(p<=mid)Modify(t[x].ls,l,mid,p,w);

	else Modify(t[x].rs,mid+1,r,p,w);

}

void PreModify(int x,int p,int w)

{

	for(int i=x;i<=n;i+=lb(i))

		Modify(rt[i],1,len,p,w);

}

int Query(int x,int l,int r,int L,int R)

{

	if(L<=l&&r<=R)return t[x].v;

	int mid=(l+r)>>1,ret=0;

	if(L<=mid)ret+=Query(t[x].ls,l,mid,L,R);

	if(R>mid)ret+=Query(t[x].rs,mid+1,r,L,R);

	return ret;

}

int PreQuery(int x,int L,int R)

{

	int ret=0;

	if(L>R)return 0;

	for(int i=x;i;i-=lb(i))ret+=Query(rt[i],1,len,L,R);

	return ret;

}

int ans;

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=S[i]=read();

	sort(&S[1],&S[n+1]);len=unique(&S[1],&S[n+1])-S-1;

	for(int i=1;i<=n;++i)a[i]=lower_bound(&S[1],&S[len+1],a[i])-S;

	for(int i=1;i<=n;++i)

	{

		ans+=PreQuery(i,a[i]+1,len);

		PreModify(i,a[i],1);

	}

	printf("%d\n",ans);

	Q=read();

	while(Q--)

	{

		int x=read(),y=read();

		if(x<y)swap(x,y);

		PreModify(x,a[x],-1);

		ans-=PreQuery(x,a[x]+1,len);

		ans-=PreQuery(n,1,a[x]-1)-PreQuery(x,1,a[x]-1);

		PreModify(y,a[y],-1);

		ans-=PreQuery(y,a[y]+1,len);

		ans-=PreQuery(n,1,a[y]-1)-PreQuery(y,1,a[y]-1);

		swap(a[x],a[y]);

		ans+=PreQuery(y,a[y]+1,len);

		ans+=PreQuery(n,1,a[y]-1)-PreQuery(y,1,a[y]-1);

		PreModify(y,a[y],1);

		ans+=PreQuery(x,a[x]+1,len);

		ans+=PreQuery(n,1,a[x]-1)-PreQuery(x,1,a[x]-1);

		PreModify(x,a[x],1);

		printf("%d\n",ans);

	}

	return 0;

}