【BZOJ3295】动态逆序对（线段树，树状数组）

题面

Description

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

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

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

Sample Input

5 4

1

5

3

4

2

5

1

4

2

Sample Output

5

2

2

1

题解

显然可以CDQ分治做（我等下就写）

这题神似Dynamic Ranking

其实，有些人说这个叫做带修改的主席树

可是，我怎么看都觉得这是线段树动态开点呀。。。

无所谓了

智商不够数据结构来补就好啦

空间大概是\(nlog^2\)的？？？？

玄学空间

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 150000

inline int read()

{

	int x=0,t=1;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;

}

struct Node

{

	int ls,rs;

	int v;

}t[MAX<<6];

int tot,rt[MAX],sum;

long long ans;

int n,m;

int c[MAX],a[MAX],b[MAX];

int lowbit(int x){return x&(-x);}

void Add(int x,int w){while(x<=n)c[x]+=w,x+=lowbit(x);}

int getsum(int x){int ret=0;while(x)ret+=c[x],x-=lowbit(x);return ret;}

void Modify(int &now,int l,int r,int pos,int w)

{

	if(!now)now=++tot;

	t[now].v+=w;

	if(l==r)return;

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

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

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

}

int L,R;

int Query(int now,int l,int r)

{

	if(!now)return 0;

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

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

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

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

	return ret;

}

int main()

{

	n=read();m=read();

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

	{

		a[i]=read(),b[a[i]]=i;

		ans+=getsum(n)-getsum(a[i]);

		Add(a[i],1);

	}

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

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

			Modify(rt[x],1,n,a[i],1);

	while(m--)

	{

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

		int p=b[read()];

		for(int i=p-1;i;i-=lowbit(i))

			L=a[p]+1,R=n,ans-=Query(rt[i],1,n);

		for(int i=n;i;i-=lowbit(i))

			L=1,R=a[p]-1,ans-=Query(rt[i],1,n);

		for(int i=p;i;i-=lowbit(i))

			L=1,R=a[p]-1,ans+=Query(rt[i],1,n);

		for(int i=p;i<=n;i+=lowbit(i))

			Modify(rt[i],1,n,a[p],-1);

	}

	return 0;

}