lg3157[动态逆序对]

发表于 | 阅读数 次

链接:lg3157[动态逆序对]

题解

  • 蒟蒻不会cdq分治…写的树状数套权值线段树,据说线段树套平衡树也可以卡过虽然听说很多巨佬被卡树上下不来…
  • 如果数x被删掉了,那么他对答案的影响是在x前面比他大的数+在x后面比他小的数
  • 具体来讲预处理出原数组的这两个关系,每次删掉一个数减掉相应的值就好,但是删掉的数之间会构成逆序对,这样就会导致多减了
  • .于是再求一次这次删掉的数x和之前删掉的数组成的逆序对就好了
  • 参考了巨佬hzwer的写法
  • 查询两次,每次直接二分权值.
  • 例如往前查询的时候,如果x<=mid 那么tmp加上右区间的数 往后也是一样的
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rint register 
#define rep(i,x,y) for(rint int i=x;i<=y;++i)
#define repd(i,x,y) for(rint int i=x;i>=y;--i)
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;
const int N=5e4+7;
const int M=N*400;
ll tr[M],a1[N<<1],a2[N<<1],ans;
int ls[M],rs[M],root[N<<1],nm[N<<1],t[N<<1],pos[N<<1];
int L[30],R[30],llen,rlen,n,m,cnt;
template <typename T>inline void read(T &x){
	char c;x=0;int sign=1;
	do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
	do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
	x*=sign;
}
inline void add(int &x){for(rint int i=x;i<=n;i+=lowbit(i))t[i]++;}
inline int query(int &x){int ans=0;for(rint int i=x;i;i-=lowbit(i))ans+=t[i];return ans;}
inline void update(int &o,int l,int r,int x){
	if(!o)o=++cnt;tr[o]++;
	if(l==r)return ;
	int mid=l+r>>1;
	if(x<=mid)update(ls[o],l,mid,x);
	else update(rs[o],mid+1,r,x);
}
inline ll queryl(int a,int b,int k){
	int l=1,r=n;ll tmp=0;a--;llen=rlen=0;
	for(rint int i=a;i;i-=lowbit(i))L[++llen]=root[i];
	for(rint int i=b;i;i-=lowbit(i))R[++rlen]=root[i];
	while(l<r){
		int mid=l+r>>1;
		if(k<=mid){
			rep(i,1,llen)tmp-=tr[rs[L[i]]],L[i]=ls[L[i]];
			rep(i,1,rlen)tmp+=tr[rs[R[i]]],R[i]=ls[R[i]];
			r=mid;
		}
		else {rep(i,1,llen)L[i]=rs[L[i]];rep(i,1,rlen)R[i]=rs[R[i]];l=mid+1;}
	}
	return tmp;
}
inline ll queryr(int a,int b,int k){
	int l=1,r=n;ll tmp=0;a--;llen=rlen=0;
	for(rint int i=a;i;i-=lowbit(i))L[++llen]=root[i];
	for(rint int i=b;i;i-=lowbit(i))R[++rlen]=root[i];
	while(l<r){
		int mid=l+r>>1;
		if(k>mid){
			rep(i,1,llen)tmp-=tr[ls[L[i]]],L[i]=rs[L[i]];
			rep(i,1,rlen)tmp+=tr[ls[R[i]]],R[i]=rs[R[i]];
			l=mid+1;
		}
		else {rep(i,1,llen)L[i]=ls[L[i]];rep(i,1,rlen)R[i]=ls[R[i]];r=mid;}
	}
	return tmp;
}
inline void init(){
	read(n);read(m);
	rep(i,1,n){
		read(nm[i]);pos[nm[i]]=i;add(nm[i]);
		a1[i]=i-query(nm[i]);
		ans+=a1[i];
	}
	memset(t,0,sizeof(t));
	repd(i,n,1){add(nm[i]);a2[i]=query(nm[i])-1;}
}
inline void solve(){
	while(m--){
		int x;read(x);x=pos[x];
		printf("%lld\n",ans);
		ans-=a1[x]+a2[x]-queryl(1,x-1,nm[x])-queryr(x+1,n,nm[x]);
		for(rint int i=x;i<=n;i+=lowbit(i))update(root[i],1,n,nm[x]);
	}
}
int main(){
	init();
	solve();
	return 0;
}