3295: [Cqoi2011]动态逆序对
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2280 Solved: 725
[Submit][Status][Discuss]
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
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
HINT
N<=
树状数组包线段树。。。
我们令删除的数为x，位置在loc。
首先容易想到的就是找到1~（loc-1）大于x的个数，和（loc+1）~n小于x的个数。这就是裸的主席树上加树状数组。但是这样内存是Nlog2N，是会炸的。于是我们换一种维护方式，我们先预处理出每个位置的front和back，front是指位置在其之前且值大于其值的个数，back是指位置在其之后且值小于其值的个数。
那么我们需要在主席树上维护就是删去的数。这样的内存是Mlog2N的，就可以解决这道题了。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m,x,loc,cnt;
int L[35],R[35],front[100010],back[100010],b[100010],root[100010],pos[100010],a[100010];
ll ans;
struct node{int l,r;ll sum;}tr[8000010];
int ask(int x){int ans=0;for (;x;x-=x&-x) ans+=b[x];return ans;}
void add(int x){for (;x<=n;x+=x&-x) b[x]++;}
ll ask2(int l,int r,int x)
{
if (l>r) return 0;
l--;
L[0]=R[0]=0;
for (int i=l;i;i-=i&-i)
L[++L[0]]=root[i];
for (int i=r;i;i-=i&-i)
R[++R[0]]=root[i];
l=1;r=n;
ll sum=0;
while (l<r)
{
int mid=(l+r)>>1;
if (x<=mid)
{
for (int i=1;i<=R[0];i++) sum+=tr[tr[R[i]].r].sum;
for (int i=1;i<=L[0];i++) sum-=tr[tr[L[i]].r].sum;
for (int i=1;i<=R[0];i++) R[i]=tr[R[i]].l;
for (int i=1;i<=L[0];i++) L[i]=tr[L[i]].l;
r=mid;
}else
{
for (int i=1;i<=L[0];i++) L[i]=tr[L[i]].r;
for (int i=1;i<=R[0];i++) R[i]=tr[R[i]].r;
l=mid+1;
}
}
return sum;
}
ll ask1(int l,int r,int x)
{
if (l>r) return 0;
l--;
L[0]=R[0]=0;
for (int i=l;i;i-=i&-i)
L[++L[0]]=root[i];
for (int i=r;i;i-=i&-i)
R[++R[0]]=root[i];
l=1;r=n;
ll sum=0;
while (l<r)
{
int mid=(l+r)>>1;
if (x>mid)
{
for (int i=1;i<=R[0];i++) sum+=tr[tr[R[i]].l].sum;
for (int i=1;i<=L[0];i++) sum-=tr[tr[L[i]].l].sum;
for (int i=1;i<=R[0];i++) R[i]=tr[R[i]].r;
for (int i=1;i<=L[0];i++) L[i]=tr[L[i]].r;
l=mid+1;
}else
{
for (int i=1;i<=L[0];i++) L[i]=tr[L[i]].l;
for (int i=1;i<=R[0];i++) R[i]=tr[R[i]].l;
r=mid;
}
}
return sum;
}
void change(int &p,int l,int r,int x)
{
tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) change(tr[p].l,l,mid,x);else change(tr[p].r,mid+1,r,x);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[a[i]]=i;
front[i]=i-1-ask(a[i]);
ans+=front[i];
add(a[i]);
}
memset(b,0,sizeof(b));
for (int i=n;i>=1;i--)
{
back[i]=ask(a[i]);
add(a[i]);
}
while (m--)
{
printf("%lld\n",ans);
scanf("%d",&x);
loc=pos[x];
ans-=front[loc]-ask2(1,loc-1,x);
ans-=back[loc]-ask1(loc+1,n,x);
for (;loc<=n;loc+=loc&-loc) change(root[loc],1,n,x);
}
}
评论 (0)
