P3157 [CQOI2011]動態逆序對(cdq分治)

題意

給定排列 1 ? n 1-n 1?n和 m m m次洗掉操作，求每次洗掉前序列的逆序對數，

思路

C D Q CDQ CDQ分治，我們可以定義一個時間戳，把原來的數看作插入操作，且時間為0，

洗掉操作的時間戳就是操作次數的下標，按照時間從小到大，這是第一維，

然后我們考慮分治解決逆序對數，對于區間 [ 1 , c n t ] [1,cnt] [1,cnt]的逆序對 ( c n t (cnt (cnt是總運算元 ) ) )，我們遞回解決掉 [ l , m i d ] , [ m i d + 1 , c n t ] [l,mid],[mid+1,cnt] [l,mid],[mid+1,cnt]，接下來我們只需考慮一個左區間，一個在右區間的貢獻，我們按照下標 p o s pos pos從小到大分別對兩個區間排序，

struct node{
	int x,v,p,t;//x(insert or delete) v(value) p(pos) t(time)
}e[N];
bool cmp(node a,node b){
	return a.p<b.p;
}
///
if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	sort(e+l,e+mid+1,cmp),sort(e+mid+1,e+r+1,cmp);

接下來我們只需列舉右區間的每個點 i i i，在左區間找到所有滿足 j j j的 p j < p i p_j<p_i pj?<pi?且 v j > v i v_j>v_i vj?>vi?u或者 ( p j > p i & & v j < v i ) (p_j>p_i\&\& v_j<v_i) (pj?>pi?&&vj?<vi?)的點，

這一步可以用 B I T BIT BIT解決，

記住每次統計完后，要還原影響，

時間復雜度： O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

代碼

// Problem: P3157 [CQOI2011]動態逆序對
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3157
// Memory Limit: 500 MB
// Time Limit: 1500 ms
// Date: 2021-03-04 14:17:02
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int n,m,a[N],pos[N];
ll ans[N];
int cnt;
struct node{
	int x,v,p,t;//x(insert or delete) v(value) p(pos) t(time)
}e[N];
bool cmp(node a,node b){
	return a.p<b.p;
}
#define lowbit(x) x&(-x)
ll s[N];
void upd(int x,int v){
	while(x<=n){
		s[x]+=v;x+=lowbit(x);
	}return;
}
ll que(int x){
	ll ans=0;
	while(x){
		ans+=s[x];x-=lowbit(x);
	}return ans;
}
void cdq(int l,int r){
	//printf("(%d,%d)\n",l,r);
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	sort(e+l,e+mid+1,cmp),sort(e+mid+1,e+r+1,cmp);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&e[j].p<=e[i].p) upd(e[j].v,e[j].x),j++;
		ans[e[i].t]+=1LL*e[i].x*(que(n)-que(e[i].v));
	}
	for(int i=l;i<j;i++) upd(e[i].v,-e[i].x);
	j=mid;
	for(int i=r;i>mid;i--){
		while(j>=l&&e[j].p>=e[i].p) upd(e[j].v,e[j].x),j--;
		ans[e[i].t]+=1LL*e[i].x*que(e[i].v-1);
	}
	for(int i=mid;i>j;i--) upd(e[i].v,-e[i].x);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i,e[++cnt]={1,a[i],i,0};
	for(int i=1;i<=m;i++){
		int x;scanf("%d",&x);e[++cnt]={-1,x,pos[x],i};
	}
	/*printf("cnt=%d\n",cnt);
	return 0;*/
	cdq(1,cnt);
	for(int i=1;i<=m;i++) ans[i]+=ans[i-1];
	for(int i=0;i<m;i++) printf("%lld\n",ans[i]);
	return 0;
}