[Uva 11990] Dynamic Inversion （CDQ分治入门）

本文主要是介绍[Uva 11990] Dynamic Inversion （CDQ分治入门），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Uva - 11990

动态逆序对，求删除一个点之前序列中逆序对的个数

首先倒过来看这个问题，把点先全部删掉
然后从最后一个点开始倒着往数列中加点
求加完这个点逆序对的变化

CDQ分治做法

把删除时间看作 t，下标看作 x，值看作 y
然后对 x排序，对 t偏序，用树状数组维护 y
具体来说就是对于每个点 $(t_0, x_0, y_0)$
先统计 $t < t_0,x < x_0,y > y_0$ 的 $(t,x,y)$ 的个数
再统计 $t < t_0,x > x_0,y < y_0$ 的 $(t,x,y)$ 的个数
做法参考了这个 http://blog.csdn.net/u011542204/article/details/50571409

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) (a*a)const int maxn=2e5+10;
struct BIT
{int bit[maxn], siz;int lowbit(int x){return x&-x;}void add(int x,int v) { while(x<=siz) bit[x]+=v,x+=lowbit(x);}int sum(int x) { int res=0; while(x>0) res+=bit[x],x-=lowbit(x); return res;}void init(){CLR(bit);}
} tree;
int N,M;
int inpt[maxn], posi[maxn];
bool ban[maxn];
struct piii{int t,x,y;} data[maxn], temp[maxn];LL ans[maxn];
void CDQ(int,int);int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);#endifwhile(~scanf("%d%d", &N, &M)){CLR(ban); CLR(ans);tree.siz=N;tree.init();for(int i=1; i<=N; i++){scanf("%d", &inpt[i]);posi[ inpt[i] ] = i;}int nt=N;for(int i=1; i<=M; i++){int x;scanf("%d", &x);ban[ posi[x] ] = 1;data[nt].t = nt;data[nt].x = posi[ x ];data[nt].y = x;nt--;}for(int i=1; i<=N; i++){if(!ban[i]){data[nt].t = nt;data[nt].x = i;data[nt].y = inpt[i];nt--;}}CDQ(1,N);for(int i=1; i<=N; i++) ans[i]+=ans[i-1];for(int i=N; i>N-M; i--) printf("%lld\n", ans[i]);}return 0;
}void CDQ(int L, int R)
{if(L>=R) return;int mid=(L+R)>>1;CDQ(L,mid); CDQ(mid+1, R);// 统计 t < t_0，x < x_0，y > y_0int tl=L;for(int i=mid+1; i<=R; i++){while(tl<=mid && data[tl].x < data[i].x) tree.add(data[tl++].y,1);ans[data[i].t] += tree.sum(N)-tree.sum(data[i].y);}
//  tree.init(); 不要用memset，这样是 N^2的for(int i=L; i<tl; i++) tree.add(data[i].y,-1);// 统计 t < t_0，x > x_0，y < y_0tl=mid;for(int i=R; i>mid; i--){while(tl>=L && data[tl].x > data[i].x) tree.add(data[tl--].y,1);ans[data[i].t] += tree.sum(data[i].y-1);}
//  tree.init();for(int i=mid; i>tl; i--) tree.add(data[i].y,-1);// 归并排序tl=L;int np=L;for(int i=mid+1; i<=R; i++){while(tl<=mid && data[tl].x < data[i].x) temp[np++] = data[tl++];temp[np++] = data[i];}while(tl<=mid) temp[np++] = data[tl++];for(int i=L; i<=R; i++) data[i] = temp[i];
}