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)。
题解:
这题一看上去就是个主席树板子题,但是数据范围可以暴力分块,我就当练习写了个分块,根据n=100000,开block=1000 分块,刚好符合内存和时间要求,我就乱搞了个block=1000,然后最多有100个块,每一个块单独开一个树状数组,然后就像平时求逆序对一样,直接在a[i]对应的位置+1,然后删除就是-1,对于同一个块内,直接暴力搞,不同块也直接枚举每一个块,分别查一次树状数组,然后ans减去这个数的贡献就是当前的答案 复杂度 O(msqrt(n)logn)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=100005,M=105;
int gi(){
int str=0;char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
int n,m,a[N],del[N],w[N],bol=1000,bel[N],tot,Tree[M][N],s[M],ed[M];
bool d[N];int sz[M];
il void add(int t,int sta,int to){
for(RG int i=sta;i<=n;i+=(i&(-i)))Tree[t][i]+=to;
}
il int query(int t,int sta){
RG int ret=0;
for(RG int i=sta;i>=1;i-=(i&(-i)))ret+=Tree[t][i];
return ret;
}
void work()
{
n=gi();m=gi();int cnt=0,tot=1;s[1]=1;
for(int i=1;i<=n;i++){
a[i]=gi(),w[a[i]]=i;
if(cnt==bol)cnt=0,tot++,s[tot]=i,ed[tot-1]=i-1;bel[i]=tot;cnt++;
sz[tot]++;
}
ed[tot]=n;
for(RG int i=1;i<=tot;i++)
for(RG int j=s[i];j<=ed[i];j++)
add(i,a[j],1);
for(int i=1;i<=m;i++)del[i]=gi();
ll ans=0;
for(RG int i=1;i<=n;i++){
ans+=i-1-query(tot+1,a[i]);
add(tot+1,a[i],1);
}
RG int t,bl;
for(int i=1;i<=m;i++){
t=w[del[i]];bl=bel[t];
printf("%lld
",ans);
for(int j=t-1;j>=s[bl];j--)
if(!d[j] && a[j]>del[i])ans--;
for(int j=t+1;j<=ed[bl];j++)
if(!d[j] && a[j]<del[i])ans--;
d[t]=true;
for(int j=1;j<bl;j++)
ans-=sz[j]-query(j,del[i]);
for(int j=bl+1;j<=tot;j++)
ans-=query(j,del[i]);
add(bl,del[i],-1);sz[bl]--;
}
}
int main()
{
freopen("inverse.in","r",stdin);
freopen("inverse.out","w",stdout);
work();
return 0;
}