P1393 动态逆序对

题目

P1393 动态逆序对

做题前写篇博客是个好方法

做法

题目规定仅有删除，给每个位置标个号，逆序对+时间轴，显然这是个三维偏序

很久没做过\(cdq\)了，就当模板题讲一下：

按删除的先后顺序为关键字排序分治，然后在\(cdq\)中按位置排序，同时前部分删除的时间<=后部分删除时间

此时前部分删除的一个点会影响到的贡献在后部分处理：1.位置大值小查询-值大数量；2.位置小值大查询-值小数量

My complete code

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long LL;

const LL maxn=1e5;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-')f=-1; c=getchar();

	}

	while(c>='0'&&c<='9')

	    x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*f;

}

LL n,m,ans;

LL tree[maxn],a[maxn],tmp[maxn],D[maxn],low[maxn];

inline LL Lowbit(LL x){

	return x&(-x);

}

inline void Add(LL x,LL val){

	for(;x<=n;x+=Lowbit(x))

	    tree[x]+=val;

}

inline LL Query(LL x){

	LL ret(0);

	for(;x;x-=Lowbit(x))

	    ret+=tree[x];

	return ret;

}

struct node{

	LL del,val,id,ans;

}q[maxn];

inline bool cmp1(node x,node y){

	return x.del<y.del;

}

inline bool cmp2(node x,node y){

	return x.id<y.id;

}

void Cdq(LL l,LL r){

	if(l==r)

	    return;

	LL mid(l+r>>1);

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

	sort(q+l,q+mid+1,cmp2),sort(q+mid+1,q+r+1,cmp2);

	LL j=mid;

	for(LL i=l;i<=mid;++i){//big

		while(j<r&&q[j+1].id<q[i].id)

		    Add(q[++j].val,1);

		q[i].ans+=Query(n)-Query(q[i].val);

	}

	for(LL i=mid+1;i<=j;++i)

	    Add(q[i].val,-1);

	j=r+1;

	for(LL i=mid;i>=l;--i){

		while(j>mid+1&&q[j-1].id>q[i].id)

		    Add(q[--j].val,1);

		q[i].ans+=Query(q[i].val-1);

	}

	for(LL i=j;i<=r;++i)

	    Add(q[i].val,-1);

}

int main(){

	n=Read(),m=Read();

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

	    tmp[i]=a[i]=Read();

	sort(tmp+1,tmp+1+n);

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

	    a[i]=lower_bound(tmp+1,tmp+1+n,a[i])-tmp;

	for(LL i=n;i>=1;--i){

		ans+=Query(a[i]-1);

		Add(a[i],1);

	}

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

		q[i]=(node){n+1,a[i],i,0};

	for(LL i=1;i<=m;++i){

		D[i]=Read();

		q[D[i]].del=i;

	}

	memset(tree,0,sizeof(tree));

	sort(q+1,q+1+n,cmp1);

	Cdq(1,n);

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

	    low[q[i].id]=q[i].ans;

	printf("%lld ",ans);

	for(LL i=1;i<=m;++i){

		ans-=low[D[i]];

		printf("%lld ",ans);

	}

	return 0;

}/*

6 3

5 4 2 6 3 1

2 1 4

11 7 4 2

*/

巴特西

P1393 动态逆序对

题目

做法

My complete code

最新文章

热门文章