P1347 – [CQOI2011]动态逆序对
Description
对于序列A，它的逆序对数定义为满足i＜j，且Ai＞Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。
以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
Hint
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
数据规模：
N＜=100000 ， M＜=50000
Source
耒阳大视野，CQOI
主席树, 分治 ,可持久化, 分块 ,陈丹琦分治
@font-face { font-family: “Times New Roman” }
@font-face { font-family: “宋体” }
@font-face { font-family: “Calibri” }
p.MsoNormal { margin: 0 0 0.0001pt; text-align: justify; font-family: Calibri; font-size: 10.5pt }
span.msoIns { text-decoration: underline; color: rgba(0, 0, 255, 1) }
span.msoDel { text-decoration: line-through; color: rgba(255, 0, 0, 1) }
div.Section0 { }
这是个个三维偏序，有时间t,下标id,权值v,第一维排t,（只需左边的t全部小于右边的t就行）然后第二维CDQ,第三维树状数组维护.
1 #define ll long long 2 #define rep(i,a,b) for(int i=a;i<=b;i++) 3 #define erp(i,a,b) for(int i=a;i>=b;i--) 4 #include<algorithm> 5 #include<iostream> 6 #include<iomanip> 7 #include<cstring> 8 #include<cstdlib> 9 #include<cstdio> 10 #include<queue> 11 #include<ctime> 12 #include<cmath> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define lowbit(p) p&(-p) 17 using namespace std; 18 const int N=100000+10; 19 struct node{ 20 int t,id; 21 ll v; 22 }a[N],np[N]; 23 int pos[N],n,m; 24 ll Ans[N],ld[N],rx[N]; 25 ll C[N]; 26 inline void add(int p,int x) { 27 if(!p) return; 28 while(p<=n) C[p]+=x,p+=lowbit(p); 29 } 30 inline ll getsum(int p) { 31 ll sum=0; 32 while(p) sum+=C[p],p-=lowbit(p); 33 return sum; 34 } 35 inline int gi() { 36 int res=0,f=1; 37 char ch=getchar(); 38 while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); 39 if(ch=='-') ch=getchar(),f=-1; 40 while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); 41 return res*f; 42 } 43 44 void CDQ(int l,int r) { 45 if(l>=r) return; 46 int mid=(l+r)>>1; 47 48 int l1=l,l2=mid+1; 49 rep(i,l,r) if(a[i].t<=mid) np[l1++]=a[i];else np[l2++]=a[i];// qsort() depend t 50 rep(i,l,r) a[i]=np[i];// ? 51 l1=l; 52 53 rep(i,mid+1,r) { 54 for(;l1<=mid&&a[l1].id<a[i].id;l1++)// find left id<id_0 55 add(a[l1].v,1); 56 ld[ a[i].t ] += (l1-l) - getsum(a[i].v); 57 } 58 rep(i,l,l1-1) add(a[i].v,-1);// l1-1!! 59 l1=mid; 60 erp(i,r,mid+1) { 61 for(;l1>=l&&a[l1].id>a[i].id;l1--) add(a[l1].v,1); 62 rx[a[i].t] += getsum(a[i].v-1); 63 } 64 rep(i,l1+1,mid) add(a[i].v,-1);// memset(c) l+1-mid!!!x 65 CDQ(l,mid),CDQ(mid+1,r); 66 } 67 int main() { 68 n=gi();m=gi(); 69 int tim=n,x; 70 rep(i,1,n) a[i].v=gi(),a[i].id=i,pos[a[i].v]=i; 71 rep(i,1,m) x=gi(),a[pos[x]].t=tim--; 72 rep(i,1,n) if(!a[i].t) a[i].t=tim--; 73 CDQ(1,n); 74 Ans[0]=0; 75 rep(i,1,n) Ans[i]=Ans[i-1]+(ll)ld[i]+(ll)rx[i]; 76 erp(i,n,n-m+1) printf("%lld ",Ans[i]); 77 return 0; 78 }