BZOJ 3295 [Cqoi2011]动态逆序对

CDQ分治。

CDQ分治的步骤：

1. 首先按time排序，之后进行处理的时候一定有time[i]>time[j]（右i左j）
2. 之后使用CDQ分治一维，对[l,mid]和[mid+1,r]进行以id排序。
3. 对于已经左右分别排好序的[l,mid]以及[mid+1,r]，一定有time[i]>time[j],id[i]>id[j] (i在[mid+1,r]中,j在[l,mid]中)，之后对于每一个需要被更新的i使用横坐标为val构成的树状数组进行维护就好了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,inx;
long long sum,ans[100010],f[100010];
struct node
{
	int val,id,tm;
}a[100010],b[100010];
bool cmp(node tx,node ty)
{
	if(tx.tm==ty.tm) return tx.id<ty.id;
	return tx.tm<ty.tm;
}
long long query(int tx)
{
    long long ret=0;
    for(;tx;tx-=tx&-tx) ret+=f[tx];
    return ret;
}
int add(int tx,int ty)
{
    for(;tx<=n;tx+=tx&-tx) f[tx]+=ty;
}
long long queryb(int tx)
{
    long long ret=0;
    for(;tx<=n;tx+=tx&-tx) ret+=f[tx];
    return ret;
}
int addb(int tx,int ty)
{
    for(;tx;tx-=tx&-tx) f[tx]+=ty;
}
void cdq(int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)>>1,p1,p2;
	cdq(l,mid),cdq(mid+1,r);
	p1=mid,p2=r;
	for(int i=l;i<=r;++i)
	{
		if(p1==l-1||(p2!=mid&&a[p1].id<a[p2].id)) ans[a[p2].tm]+=query(a[p2].val),p2--; 
		else add(a[p1].val,1),p1--;
	}
	for(int i=l;i<=mid;++i) add(a[i].val,-1);
	p1=l,p2=mid+1;
	for(int i=l;i<=r;++i)
	{
		if(p1==mid+1||(p2!=r+1&&a[p1].id>a[p2].id)) ans[a[p2].tm]+=queryb(a[p2].val),b[i]=a[p2],p2++;
		else addb(a[p1].val,1),b[i]=a[p1],p1++;
	}
	for(int i=l;i<=mid;++i) addb(a[i].val,-1);
	for(int i=l;i<=r;++i) a[i]=b[i];
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i].val),a[i].id=i;
	for(int i=m;i;i--)
	{
		scanf("%d",&inx);
		a[inx].tm=i;
	}
	sort(a+1,a+n+1,cmp);
	cdq(1,n);
	for(int i=1;i<=m;++i) sum+=ans[i];
	for(int i=m;i;i--)
	{
		printf("%lld\n",sum);
		sum-=ans[i];
	}
	return 0;
}