【bzoj3295】動态逆序對 CDQ分治

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3295

【題解】

這題很神。

我用的是popoqqq大爺的做法。

具體見http://blog.csdn.net/popoqqq/article/details/38761287

感覺這種做法似乎應該稱為整體二分？

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long ll;
#define FILE "read"
#define MAXN 100010
#define up(i,j,n) for(int i=j;i<=n;++i)
#define dn(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
struct node{
	int x,y,pos;
	bool operator < (const node &b) const {return y<b.y;}
}q[MAXN],stack[MAXN];
int n,m,tot,a[MAXN],b[MAXN],cnt[MAXN],tr[MAXN],f[MAXN],tim[MAXN];
ll ans;
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getchar();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
		return x*f;
	}
}using namespace INIT;
bool cmp(node a,node b) {return a.pos<b.pos;}
void updata(int x,int f) {for(;x&&x<=n;x+=(x&-x)*f){if(tim[x]!=tot)tr[x]=0,tim[x]=tot;tr[x]++;}}
int get(int x,int f){int sum(0);for(;x&&x<=n;x+=(x&-x)*f)if(tim[x]==tot)sum+=tr[x];return sum;}
void CDQ(int l,int r){
	if(l>=r)  return;
	int mid=(l+r)>>1,ta(l),tb(mid+1),j(l);
	up(i,l,r) stack[(q[i].pos<=mid?ta:tb)++]=q[i];
	up(i,l,r) q[i]=stack[i];
	CDQ(l,mid);  tot++;
	up(i,mid+1,r){
		for(;j<=mid&&q[j].y<q[i].y;++j) updata(q[j].x,-1);
		f[q[i].pos]+=get(q[i].x,1);
	}
	tot++; j=mid;
	dn(i,r,mid+1){
		for(;j>=l&&q[j].y>q[i].y;--j) updata(q[j].x,1);
		f[q[i].pos]+=get(q[i].x,-1);
	}
	CDQ(mid+1,r);
	ta=l;tb=mid+1;  
    up(i,l,r) if((q[ta]<q[tb]||tb>r)&&ta<=mid) stack[i]=q[ta++];  
	else stack[i]=q[tb++];  
	up(i,l,r)  q[i]=stack[i];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();
	up(i,1,n)  a[i]=read(),b[a[i]]=i;
	up(i,1,n){
		cnt[i]=get(a[i],1);
		updata(a[i],-1);
		ans+=cnt[i];
	}
	tot++;
	dn(i,n,1){
		cnt[i]+=get(a[i],-1);
		updata(a[i],1);
	}
	up(i,1,m)q[i].x=read(),q[i].y=b[q[i].x],q[i].pos=i;
	sort(q+1,q+m+1);  CDQ(1,m);
	sort(q+1,q+m+1,cmp);
	up(i,1,m){
		printf("%lld\n",ans);
		ans-=cnt[q[i].y];
		ans+=f[i];
	}
	return 0;
}