[CQOI2011]动态逆序对

description

洛谷

data range

[nle 10^5,mle 5 imes 10^4 ]

solution

(CDQ)分治。

只是要写很多个修改和查询。

把自己搞晕了。调了半节晚自习。

(CDQ)的部分倒是没有出什么问题。

code

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define Cpy(x,y) memcpy(x,y,sizeof(x))
#define Set(x,y) memset(x,y,sizeof(x))
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-6;
const int mod=1e9+7;
const int N=1e6+10;
const int M=1e6+10;
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
il ll read(){
	RG ll data=0,w=1;RG char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
	return data*w;
}
il void file(){
	srand(time(NULL)+rand());
	freopen("2.in","r",stdin);
	freopen(FILE".out","w",stdout);
}

int n,m,k,a[N],p[N],da[N],d[N];ll ans[N];
struct node{int tp,t,p,v,id,w;}Q[N],tmp[N];
bool cmp1(node a,node b){if(a.t!=b.t)return a.t<b.t;return a.tp<b.tp;}
bool cmp2(node a,node b){if(a.p!=b.p)return a.p<b.p;return a.tp<b.tp;}

int t[N];
il void insert(int i,int v){for(;i<=n;i+=(i&-i))t[i]+=v;}
il void clear(int i){for(;i<=n;i+=(i&-i))t[i]=0;}
il int query(int i){int r=0;for(;i;i-=(i&-i))r+=t[i];return r;}
void cdq(int l,int r){
	if(l==r)return;RG int mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);
	for(RG int i=l,p1=l,p2=mid+1;i<=r;i++)
		if(p2>r||(p1<=mid&&cmp2(Q[p1],Q[p2]))){
			if(Q[p1].tp==1)insert(Q[p1].v,Q[p1].w);
			tmp[i]=Q[p1++];
		}
		else{
			if(Q[p2].tp==2)ans[Q[p2].id]+=query(Q[p2].v)*Q[p2].w;
			tmp[i]=Q[p2++];
		}
	for(RG int i=l;i<=r;i++){if(Q[i].v)clear(Q[i].v);Q[i]=tmp[i];}
}

int main()
{
	n=read();m=read();
	for(RG int i=1;i<=n;i++)a[i]=read(),p[a[i]]=i;
	for(RG int i=1;i<=m;i++)da[i]=read(),d[i]=p[da[i]];
	for(RG int i=1;i<=n;i++){
		Q[++k]=(node){1,0,i,a[i],0,1};
		Q[++k]=(node){2,0,i,n,0,1};
		Q[++k]=(node){2,0,i,a[i],0,-1};
	}
	for(RG int i=1;i<m;i++){
		Q[++k]=(node){1,i,d[i],da[i],0,-1};
		Q[++k]=(node){2,i,d[i],n,i,1};
		Q[++k]=(node){2,i,d[i],da[i],i,-1};
		Q[++k]=(node){2,i,n,da[i]-1,i,1};
		Q[++k]=(node){2,i,d[i],da[i]-1,i,-1};
	}
	sort(Q+1,Q+k+1,cmp1);cdq(1,k);
	for(RG int i=2;i<m;i++)ans[i]+=ans[i-1];
	for(RG int i=1;i<m;i++)ans[i]=ans[0]-ans[i];
	for(RG int i=0;i<m;i++)printf("%lld
",ans[i]);
	return 0;
}