• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

动态逆序对

admin

11月 28, 2021

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
主席树, 分治 ,可持久化, 分块 ,陈丹琦分治

Accepted entrance

@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 }

发表回复

您的电子邮箱地址不会被公开。