Problem

有一个长度为n的1~n的排列,现在进行m次删除操作,每次给定删除的元素,要求在每次删除之前输出序列里的逆序对个数。


Solution

考虑最普通的静态逆序对,显然可以用树状数组来维护,那么每次删除一个数p,逆序对个数减少的就是(p前面大于p的数)和(p后面小于p的数),立马就有一个朴素的想法:在树状数组里修改删除,但是马上也就能把这个想法切掉,因为删除操作开始后,所有数字已经加入进去了,此时的统计是没有意义的。

那么我们就要考虑如何完成这个维护这个顺序的问题,另一个想法就是用主席树套树状数组,但是我不会,所以让我们来想想其他的办法。

然后就考虑分块。前面的块里的元素无论如何,一定在后面块里元素的前面。所以我们就考虑在删除的元素的块内暴力,其他的块内直接利用前后关系来计算对答案的贡献。

经过实践,发现分100块左右是最优的,就算卡满时间复杂度也只有O(1000*m),大概5e7的时间复杂度,显然是能过去的。

具体操作就是对每一块需要查询比某个元素x大或小的个数,那么每一块开两个树状数组就可以实现了,第一个在1处插1,a[i]处插-1,这样我们ask(x)得到的就是大于它的元素个数,第二个在a[i]处插1,ask(x)得到是小于它的元素个数。

至于上面说的暴力是怎么暴力呢?真就枚举原数列判断p前面比它大的,p后面比它小的,这个操作是O(块长)的,上面那个整块的操作是O(块数logn)的,logn大致是17,整体是差不多在O(1000)这样一个级别,所以时间复杂度是正确的。

代码实现也挺简单的。。至少比机房那个打主席树套树状数组还没调出来的简单。

#include<bits/stdc++.h>
#define reg register
#define int long long
#define len 1000
#define L(x) ((x)*len-len+1)
#define R(x) ((x)*len)
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e5+10,SN=110;
int a[N],num[N],c[SN][N][2];
int to[N],wz[N],vis[N],n,m;
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
inline void add(int u,int v,int pos,int p){
    for(reg int i=u;i<=n;i+=lowbit(i))
        c[pos][i][p]+=v;
}
inline int ask(int u,int pos,int p){
    int cnt(0);
    for(reg int i=u;i;i-=lowbit(i))
        cnt+=c[pos][i][p];
    return cnt;
}
inline void radd(int u,int v,int pos){
    add(u,v,pos,0),add(1,v,pos,1),add(u,-v,pos,1);
}
signed main(){
    cerr<<"len:"<<len<<endl;
    n=read(),m=read();
    int ans=0;
    for(reg int i=1;i<=n;i++){
        a[i]=read();
        ans+=ask(a[i],0,1);radd(a[i],1,0);
    }
    for(reg int i=1;i<=n;i++)
        num[i]=(i-1)/len+1,to[a[i]]=num[i],wz[a[i]]=i,radd(a[i],1,num[i]);
    while(m--){
        reg int p(read()),b=to[p],w=wz[p];
        printf("%lld\n",ans);
        radd(p,-1,b);vis[p]=1;
        for(reg int i=L(b),e=R(b);i<=e&&i<=n;i++)
            if(((i<w&&a[i]>a[w])||(i>w&&a[i]<a[w]))&&!vis[a[i]])ans--;
        for(reg int i=num[1],e=num[n];i<=e;i++){
            if(i<b)ans-=ask(p,i,1);
            if(i>b)ans-=ask(p,i,0);
        }
    }
    return 0;
}
最后修改:2020 年 11 月 05 日 08 : 45 PM