【刷题】BZOJ 3295 [Cqoi2011]动态逆序对

Description

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。

以下n行每行包含一个1到n之间的正整数，即初始排列。

以下m行每行一个正整数，依次为每次删除的元素。

N<=100000 M<=50000

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4

1

5

3

4

2

5

1

4

2

Sample Output

5

2

2

1

HINT

样例解释

(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

Solution

树套树，树状数组套主席树

首先看问题

我们预处理出\(A1[i]\)（\(i\) 之前的位置上的数比 \(i\) 位置上的数大的个数），\(A2[i]\)（\(i\) 之后的位置上的数比 \(i\) 位置上的数小的个数），顺便求一下最开始的逆序对

那么我们每次删除一个数 \(x\) ，它在数列中的位置是 \(i\) ，那么它对答案产生的影响就是使答案减小 \(A1[i]+A2[i]-Mquery(i)-Lquery(i)\)

其中 \(Mquery(i)\) 表示的是 \(i\) 位置之前的已经被删除了的权值比 \(i\) 位置上的权值大的个数，\(Lquery(i)\) 表示的就是后面的比它小的已经删除了的个数

既然 \(A1\) 和 \(A2\) 已经预处理好了

那么我们需要维护的就是两个查询了

我们想，假如没有修改，那么两个查询直接用主席树找就行了

那么有修改呢，我们需要为主席树提供的就是前缀和

所以就用树状数组去维护前缀和，类似于 BZOJ 1901 Zju2112 Dynamic Rankings 用一个树套树，这道题就搞定了

#include<bits/stdc++.h>

#define ll long long

#define db double

#define ld long double

#define left 0

#define right 1

#define Mid ((l+r)>>1)

#define lson l,Mid

#define rson Mid+1,r

const int MAXN=100000+10;

int n,m,A[MAXN],A1[MAXN],A2[MAXN],pos[MAXN];

ll ans=0;

struct BI_Tree{

	int C[MAXN];

	inline void init()

	{

		memset(C,0,sizeof(C));

	}

	inline int lowbit(int x)

	{

		return x&(-x);

	}

	inline int sum(int x)

	{

		int res=0;

		while(x>0)

		{

			res+=C[x];

			x-=lowbit(x);

		}

		return res;

	}

	inline void add(int x,int k)

	{

		while(x<=n)

		{

			C[x]+=k;

			x+=lowbit(x);

		}

	}

};

BI_Tree BIT;

struct ChairManTree_BIT{

	int cnt,lc[MAXN*50],rc[MAXN*50],root[MAXN],nt[2],need[2][MAXN];

	ll num[MAXN*50];

	inline void init()

	{

		cnt=0;

		memset(lc,0,sizeof(lc));

		memset(rc,0,sizeof(rc));

		memset(num,0,sizeof(num));

	}

	inline int lowbit(int x)

	{

		return x&(-x);

	}

	inline void Insert(int &rt,int l,int r,int pos)

	{

		if(!rt)rt=++cnt;

		num[rt]++;

		if(l==r)return ;

		else

		{

			if(pos<=Mid)Insert(lc[rt],lson,pos);

			else Insert(rc[rt],rson,pos);

		}

	}

	inline void add(int x,int k)

	{

		while(x<=n)

		{

			Insert(root[x],1,n,k);

			x+=lowbit(x);

		}

	}

	inline void Gneed(int nxt[])

	{

		for(register int i=1;i<=nt[left];++i)need[left][i]=nxt[need[left][i]];

		for(register int i=1;i<=nt[right];++i)need[right][i]=nxt[need[right][i]];

	}

	inline int Lquery(int l,int r,int k)

	{

		if(l==r)return 0;

		else

		{

			ll res=0;

			if(k>Mid)

			{

				for(register int i=1;i<=nt[right];++i)res+=num[lc[need[right][i]]];

				for(register int i=1;i<=nt[left];++i)res-=num[lc[need[left][i]]];

				Gneed(rc);

				res+=Lquery(rson,k);

			}

			else

			{

				Gneed(lc);

				res+=Lquery(lson,k);

			}

			return res;

		}

	}

	inline ll Mquery(int l,int r,int k)

	{

		if(l==r)return 0;

		else

		{

			ll res=0;

			if(k<=Mid)

			{

				for(register int i=1;i<=nt[right];++i)res+=num[rc[need[right][i]]];

				for(register int i=1;i<=nt[left];++i)res-=num[rc[need[left][i]]];

				Gneed(lc);

				res+=Mquery(lson,k);

			}

			else

			{

				Gneed(rc);

				res+=Mquery(rson,k);

			}

			return res;

		}

	}

	inline ll sum(int l,int r,int k,int opt)

	{

		nt[left]=nt[right]=0;

		l--;

		while(l>0)

		{

			need[left][++nt[left]]=root[l];

			l-=lowbit(l);

		}

		while(r>0)

		{

			need[right][++nt[right]]=root[r];

			r-=lowbit(r);

		}

		if(opt==0)return Lquery(1,n,k);

		else return Mquery(1,n,k);

	}

};

ChairManTree_BIT T;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

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

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

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char c='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(c!='\0')putchar(c);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline void init()

{

	BIT.init();

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

	{

		A1[i]=BIT.sum(n)-BIT.sum(A[i]);

		ans+=A1[i];

		BIT.add(A[i],1);

	}

	BIT.init();

	for(register int i=n;i>=1;--i)

	{

		A2[i]=BIT.sum(A[i]-1);

		BIT.add(A[i],1);

	}

}

int main()

{

	read(n);read(m);

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

	{

		read(A[i]);

		pos[A[i]]=i;

	}

	init();

	T.init();

	while(m--)

	{

		write(ans,'\n');

		int x;

		read(x);

		ans-=(A1[pos[x]]+A2[pos[x]]-T.sum(1,pos[x]-1,x,1)-T.sum(pos[x]+1,n,x,0));

		T.add(pos[x],x);

	}

	return 0;

}

巴特西