首先反個順序，把刪除當做從末尾插入。
計算每個數剛被插入的時候原數列對其逆序對的貢獻，使用cdq分治，先把[l,r]序列按在原數組中的位置pos排序，然后使用權值BIT維護，就能維護出左半邊的數對右半邊的數的貢獻(正反兩遍)。
最后輸出答案的時候累加一遍即可
對于初始沒被刪除的，只需要預先計算一遍他們對所有被刪除了的數的逆序對的貢獻就可以了，順便統計出執行完刪除操作之后的逆序對數。
//QWsin#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=100000+10;typedef long long ll;int n,m,num[maxn],pos[maxn];int C[maxn];inline void clearbit(){memset(C,0,sizeof C);}#define lowbit(i) ((i)&-(i))inline void updata(int pos,int val){ for(int i=pos;i<=n;i+=lowbit(i)) C[i]+=val; }inline int query(int pos){ int ret=0; for(int i=pos;i;i-=lowbit(i)) ret+=C[i]; return ret;}int vis[maxn],op[maxn];//vis=1 表示在某個刪除操作中 //op[i] 表示i這個數字最開始對應的OP編號 struct OP{ int x,id,ans,t; inline void input(int i){ scanf("%d",&x);id=i;vis[x]=1;ans=0;op[x]=i; } inline bool Operator < (const OP &rhs)const{ return pos[x]<pos[rhs.x]; }}a[maxn],t[maxn];ll ans[maxn];void solve(int l,int r){ if(l==r) return ; int mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); for(int i=l;i<=r;++i) t[i]=a[i],t[i].t=(i>mid); sort(t+l,t+r+1); for(int i=l;i<=r;++i) if(t[i].t==0) updata(t[i].x,1); else ans[t[i].id]+=query(n)-query(t[i].x); for(int i=l;i<=r;++i) if(t[i].t==0) updata(t[i].x,-1); for(int i=r;i>=l;--i) if(t[i].t==0) updata(t[i].x,1); else ans[t[i].id]+=query(t[i].x); for(int i=r;i>=l;--i) if(t[i].t==0) updata(t[i].x,-1);}int main(){ freopen("std.in","r",stdin); cin>>n>>m; for(int i=1;i<=n;++i) scanf("%d",num+i),pos[num[i]]=i; for(int i=1;i<=m;++i) a[m+1-i].input(m+1-i); ll sum=0; for(int i=1;i<=n;++i) if(!vis[num[i]]) { sum+=query(n)-query(num[i]); updata(num[i],1); } else { int t=query(n)-query(num[i]); ans[a[op[num[i]]].id]+=t; } clearbit(); for(int i=n;i>=1;--i) if(!vis[num[i]]) {// sum+=query(num[i]);//一開始你還把原序列的逆序對算成了二倍（扶額） updata(num[i],1); } else { int t=query(num[i]); ans[a[op[num[i]]].id]+=t; } clearbit(); solve(1,m); ans[0]=sum; for(int i=1;i<=m;++i) ans[i]+=ans[i-1]; for(int i=m;i>=1;--i)新聞熱點
疑難解答
