3295: [Cqoi2011]动态逆序对
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2886 Solved: 924
[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
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
HINT
N<=100000 M<=50000
Source
题解：
分块＋树状数组＋逆序对
好像正解是CDQ分治 QAQ
然而不会。。。
胡搞了一个分块，记录一下每个数出现的位置。然后，考虑到每次删除，对答案有影响的只有当前这个数前头比它大的个数，和后头比他小的个数。所以就分块统计有多少个。但是，如何删除呢？
我是在更新完答案后，把当前的这个数放成－1。然后对于统计这个数前头比它大的数的个数没有影响(因为－1比任何数都小，不会被统计上)。但对于后头比它小的个数就不一样了。但，－1比任何数都小，所以它一定在每个排好序的块的最前端的一段。我们只需要二分去找第一个不是－1的位置，然后就可以统计了。（各种二分。。。）
至于速度嘛，rank榜上倒数。。。QAQ赶快去学CDQ分治。。。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define LL long long
int pos[MAXN],BIT[MAXN],a[MAXN],b[MAXN],wz[MAXN],block,n;
LL ans;
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
int Lowbit(int o){return o&(-o);}
void Update(int o,int o1)
{
while(o<=n)
{
BIT[o]+=o1;
o+=Lowbit(o);
}
}
int Sum(int o)
{
int sum=;
while(o>)
{
sum+=BIT[o];
o-=Lowbit(o);
}
return sum;
}
void cl(int k)
{
int l=(k-)*block+,r=min(k*block,n),i;
for(i=l;i<=r;i++)b[i]=a[i];
sort(b+l,b+r+);
}
int ef(int k,int k1)//在第k块中寻找大于k1的第一个位置.
{
int l=(k-)*block+,r=min(k*block,n),ans1;
ans1=-;
while(l<=r)
{
int mid=(l+r)/;
if(b[mid]>k1){ans1=mid;r=mid-;}
else l=mid+;
}
return ans1;
}
int ef1(int k,int k1)
{
int l=(k-)*block+,r=min(k*block,n),ans1;
ans1=-;
while(l<=r)
{
int mid=(l+r)/;
if(b[mid]<k1){ans1=mid;l=mid+;}
else r=mid-;
}
return ans1;
}
void calc1(int l,int r,int D)
{
if(l>r)return;
int L=pos[l],R=pos[r],i,pd;
if(L==R)
{
for(i=l;i<=r;i++)if(a[i]>D&&a[i]!=-)ans--;
return;
}
for(i=l;i<=L*block;i++)if(a[i]>D&&a[i]!=-)ans--;
for(i=L+;i<=R-;i++)
{
pd=ef(i,D);
if(pd!=-)ans-=(LL)(min(i*block,n)-pd+);
}
//ans-=(ef(i,D)-ef(i,0)+1);
for(i=(R-)*block+;i<=r;i++)if(a[i]>D&&a[i]!=-)ans--;
}
void calc2(int l,int r,int D)
{
if(l>r)return;
int L=pos[l],R=pos[r],i,pd,pd1;
if(L==R)
{
for(i=l;i<=r;i++)if(a[i]<D&&a[i]!=-)ans--;
return;
}
for(i=l;i<=L*block;i++)if(a[i]<D&&a[i]!=-)ans--;
for(i=L+;i<=R-;i++)
{
//ans-=(ef1(i,D)-ef(i,0)+1);
pd=ef1(i,D);
if(b[pd]!=-)
{
pd1=ef(i,);
if(pd!=-)
{
if(pd1==-)pd1=;
ans-=(LL)(pd-pd1+);
}
}
}
for(i=(R-)*block+;i<=r;i++)if(a[i]<D&&a[i]!=-)ans--;
}
int main()
{
freopen("inverse.in","r",stdin);
freopen("inverse.out","w",stdout);
int m,i,M,del;
n=read();m=read();
for(i=;i<=n;i++)a[i]=read(),wz[a[i]]=i;
block=(int)sqrt(n);
for(i=;i<=n;i++)pos[i]=(int)(i-)/block+;
if(n%block==)M=n/block;
else M=n/block+;
memset(BIT,,sizeof(BIT));ans=;
for(i=n;i>=;i--)
{
ans+=Sum(a[i]-);
Update(a[i],);
}
for(i=;i<=M;i++)cl(i);
for(i=;i<=m;i++)
{
del=read();
printf("%lld\n",ans);
calc1(,wz[del]-,del);//去寻找 从位置1到要删除的数前一个位置 中有多少个数大于要删除的数,并把个数减去.
calc2(wz[del]+,n,del);//去寻找 从要删除的数后一个位置到位置n 中有多少个数小于要删除的数,并把个数减去.
a[wz[del]]=-;
cl(pos[wz[del]]);
//printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return ;
}