bzoj千题计划146:bzoj3295: [Cqoi2011]动态逆序对

时间:2022-04-22 06:18:05

http://www.lydsy.com/JudgeOnline/problem.php?id=3295

正着删除看做倒着添加

对答案有贡献的数对满足以下3个条件:

出现时间:i<=j

权值大小关系:x[i]>x[j]

位置关系:pos[i]<pos[j]

或者是

出现时间:i<=j

权值大小关系:x[i]<x[j]

位置关系:pos[i]>pos[j]

所以是三维偏序问题

排序时间,CDQ分治解决权值大小关系,树状数组解决位置关系

CDQ分治后,只要不重新sort,内部区间仍满足 第一维 排序的大小顺序

#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001
#define M 50001 #define lowbit(x) x&-x int n; struct node
{
int pos,val,tim;
}e[N],a[N]; int dy[N],cut[N]; int c[N]; long long ans[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
return p.tim<q.tim;
} void add(int x,int y)
{
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
} int query(int x)
{
int sum=;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
} void solve(int l,int r)
{
if(l==r) return;
int mid=l+r>>;
for(int i=l;i<=r;++i)
{
if(e[i].val<=mid) add(e[i].pos,);
else ans[e[i].tim]+=query(n)-query(e[i].pos);
}
for(int i=l;i<=r;++i)
if(e[i].val<=mid) add(e[i].pos,-);
for(int i=l;i<=r;++i)
{
if(e[i].val>mid) add(e[i].pos,);
else ans[e[i].tim]+=query(e[i].pos-);
}
for(int i=l;i<=r;++i)
if(e[i].val>mid) add(e[i].pos,-);
int i=l,j=mid+;
for(int k=l;k<=r;++k)
{
if(e[k].val<=mid) a[i++]=e[k];
else a[j++]=e[k];
}
for(int k=l;k<=r;++k) e[k]=a[k];
solve(l,mid);
solve(mid+,r);
} int main()
{
int m,x;
read(n); read(m);
for(int i=;i<=n;++i)
{
read(x);
dy[x]=i;
e[i].pos=i;
e[i].val=x;
}
int ti=n;
for(int i=;i<=m;++i)
{
read(x);
e[dy[x]].tim=ti--;
}
sort(e+,e+n+,cmp);
for(int i=;i<=n;++i) e[i].tim=i;
solve(,n);
for(int i=;i<=n;++i) ans[i]+=ans[i-];
for(int i=m;i;--i) cout<<ans[n-m+i]<<'\n';
}

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 5946  Solved: 2064
[Submit][Status][Discuss]

Description

对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。以下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

样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000