【BZOJ3295】[Cqoi2011]动态逆序对 cdq分治

时间：2024-09-21 14:37:14

【BZOJ3295】[Cqoi2011]动态逆序对

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

样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

题解：cdq分治裸题。

我们将区间按下标分成两半，在每一半内按删除时间排序，对于每个数，我们希望找到所有删除时间大于等于它的数与他形成的逆序对，用树状数组搞定即可，注意：既要找i<j且vi>vj的也要找j>i且vj<vi的。并且当删除时间相同时（即都没被删除时）不要计算重复。

给这题用树套树过的大佬跪了。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

int n,m,now;

const int maxn=100010;

struct node

{

	int tim,pos,v,ans;

}p[maxn];

int s[maxn],vis[maxn],q[maxn];

ll ans[maxn];

bool cmpp(node a,node b)

{

	return a.pos<b.pos;

}

bool cmpt(node a,node b)

{

	return (a.tim==b.tim)?(a.pos>b.pos):(a.tim>b.tim);

}

void updata(int x)

{

	for(int i=x;i<=n;i+=i&-i)

	{

		if(vis[i]<now)	vis[i]=now,s[i]=0;

		s[i]++;

	}

}

int query(int x)

{

	int i,ret=0;

	for(i=x;i;i-=i&-i)

	{

		if(vis[i]<now)	vis[i]=now,s[i]=0;

		ret+=s[i];

	}

	return ret;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void solve(int l,int r)

{

	if(l==r)	return ;

	int mid=l+r>>1,h1=l,h2=mid+1;

	sort(p+l,p+mid+1,cmpt),sort(p+mid+1,p+r+1,cmpt);

	now++;

	while(h1<=mid||h2<=r)

	{

		if(h2<=r&&(h1>mid||p[h2].tim>=p[h1].tim))	updata(p[h2].v),h2++;

		else	p[h1].ans+=query(p[h1].v-1),h1++;

	}

	now++,h1=l,h2=mid+1;

	while(h1<=mid||h2<=r)

	{

		if(h2<=r&&(h1>mid||p[h2].tim>=p[h1].tim))	p[h2].ans+=h1-l-query(p[h2].v),h2++;

		else	updata(p[h1].v),h1++;

	}

	sort(p+l,p+mid+1,cmpp),sort(p+mid+1,p+r+1,cmpp);

	solve(l,mid),solve(mid+1,r);

}

int main()

{

	n=rd(),m=rd();

	int i,a;

	for(i=1;i<=n;i++)	p[i].pos=i,p[i].v=rd(),p[i].tim=m+1,q[p[i].v]=i;

	for(i=1;i<=m;i++)	a=rd(),p[q[a]].tim=i;

	solve(1,n);

	sort(p+1,p+n+1,cmpp);

	for(i=1;i<=n;i++)	ans[p[i].tim]+=p[i].ans;

	for(i=m;i>=1;i--)	ans[i]+=ans[i+1];

	for(i=1;i<=m;i++)	printf("%lld\n",ans[i]);

	return 0;

}

相关文章