「Cqoi2011」动态逆序对

Source and Judge

Cqoi2011
bzoj3295
luogu3157

Record

1h

Analysis

请先思考后再展开

带修主席树:
时间倒流,变成求在前面的比它大的数和后面小的数
用前、后缀的带修主席树维护一下就好了

cdq分治:
我似乎和网上所有人的都不一样……
一开始还怀疑我的做法是错误的,后来发现是枚举顺序有一点问题,不单调了

就是给每个数打上时间戳,然后不删除的就是m+1、m+2……n
那么问题变成 $t_a>t_b,p_a<p_b,d_a>d_b$ 和 $t_c>t_b,p_c>p_b,d_c<d_b$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;

namespace mine
{
typedef long long ll;
#define int ll
const int INF=0x3f3f3f3f;

const int MAX_N=110000;
struct Nod{int t,d,p;Nod(){t=0;}}p[MAX_N];
bool cmp1(Nod a,Nod b) {return a.t<b.t;}
bool cmp2(Nod a,Nod b) {return a.p<b.p;}

int n;
int bit[MAX_N];
int lowbit(int x) {return x&-x;}
void change(int x,int c)
{
while(x<=n) bit[x]+=c,x+=lowbit(x);
}
int sum(int x)
{
int ans=0;
while(x>=1) ans+=bit[x],x-=lowbit(x);
return ans;
}

int ans[MAX_N];
void cdq(int fl,int fr)
{
if(fl>=fr) return;

int mid=(fl+fr)>>1;
cdq(fl,mid);cdq(mid+1,fr);

sort(p+fl,p+mid+1,cmp2);sort(p+mid+1,p+fr+1,cmp2);
int k1=fl-1;
for(int k2=mid+1;k2<=fr;k2++)
{
while(k1+1<=mid and p[k1+1].p<p[k2].p) change(p[++k1].d,1);
ans[p[k2].t]+=(k1-fl+1)-sum(p[k2].d);
}
for(int t=fl;t<=k1;t++) change(p[t].d,-1);

int k3=mid+1;
for(int k2=fr;k2>=mid+1;k2--)
{
while(k3-1>=fl and p[k3-1].p>p[k2].p) change(p[--k3].d,1);
ans[p[k2].t]+=sum(p[k2].d-1);
}
for(int t=k3;t<=mid;t++) change(p[t].d,-1);
}

int pos[MAX_N];//值的位置
void main()
{
int m;scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&p[i].d),p[i].p=i,pos[p[i].d]=i;
for(int i=1;i<=m;i++)
{
int t;scanf("%lld",&t);
p[pos[t]].t=i;
}
for(int now=m,i=1;i<=n;i++) if(p[i].t==0) p[i].t=++now;
sort(p+1,p+n+1,cmp1);reverse(p+1,p+n+1);
cdq(1,n);

sort(p+1,p+n+1,cmp2);
ll tot=0;for(int i=1;i<=n;i++) tot+=(i-1)-sum(p[i].d),change(p[i].d,1);
for(int i=1;i<=m;i++) printf("%lld\n",tot),tot-=ans[i];
}
}
signed main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/fea4.html
转载请注明出处,谢谢!