【BZOJ3295】动态逆序对(线段树,树状数组)

时间:2022-04-22 06:17:59

【BZOJ3295】动态逆序对(线段树,树状数组)

题面

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

题解

显然可以CDQ分治做(我等下就写)

这题神似Dynamic Ranking

其实,有些人说这个叫做带修改的主席树

可是,我怎么看都觉得这是线段树动态开点呀。。。

无所谓了

智商不够数据结构来补就好啦

空间大概是\(nlog^2\)的????

玄学空间

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 150000
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Node
{
int ls,rs;
int v;
}t[MAX<<6];
int tot,rt[MAX],sum;
long long ans;
int n,m;
int c[MAX],a[MAX],b[MAX];
int lowbit(int x){return x&(-x);}
void Add(int x,int w){while(x<=n)c[x]+=w,x+=lowbit(x);}
int getsum(int x){int ret=0;while(x)ret+=c[x],x-=lowbit(x);return ret;}
void Modify(int &now,int l,int r,int pos,int w)
{
if(!now)now=++tot;
t[now].v+=w;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)Modify(t[now].ls,l,mid,pos,w);
else Modify(t[now].rs,mid+1,r,pos,w);
}
int L,R;
int Query(int now,int l,int r)
{
if(!now)return 0;
if(L<=l&&r<=R)return t[now].v;
int mid=(l+r)>>1,ret=0;
if(L<=mid)ret+=Query(t[now].ls,l,mid);
if(R>mid)ret+=Query(t[now].rs,mid+1,r);
return ret;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)
{
a[i]=read(),b[a[i]]=i;
ans+=getsum(n)-getsum(a[i]);
Add(a[i],1);
}
for(int i=1;i<=n;++i)
for(int x=i;x<=n;x+=lowbit(x))
Modify(rt[x],1,n,a[i],1);
while(m--)
{
printf("%lld\n",ans);
int p=b[read()];
for(int i=p-1;i;i-=lowbit(i))
L=a[p]+1,R=n,ans-=Query(rt[i],1,n);
for(int i=n;i;i-=lowbit(i))
L=1,R=a[p]-1,ans-=Query(rt[i],1,n);
for(int i=p;i;i-=lowbit(i))
L=1,R=a[p]-1,ans+=Query(rt[i],1,n);
for(int i=p;i<=n;i+=lowbit(i))
Modify(rt[i],1,n,a[p],-1);
}
return 0;
}