并不对劲的bzoj3295:[CQOI2011]动态逆序对

题目大意

(n)个数的排列(a_1,...,a_n)。
有(m)次操作，每次删一个数，问删完数后逆序对的个数。
(nleq10^5;mleq50000;)

题解

先算出一开始有多少逆序对。
分块，每删掉一个数，减去和它有关的逆序对。块里暴力扫，块外对每个块算。

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define re register
#define block 1000
#define maxn 100010
#define maxm 110
#define LL long long
using namespace std;
inline LL read()
{
    LL x=0,f=1;
    char ch=getchar();
    while(isdigit(ch)==0 && ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(LL x)
{
    LL f=0;char ch[20];
    if(!x){puts("0");return;}
    if(x<0){putchar('-');x=-x;}
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('
');
}
int a[maxn],pla[maxn],ab[maxn],bs[maxm],be[maxm],siz[maxm],tr[maxm][maxn],del[maxn],sum=1,n,m;
LL cnt;
inline int lt(re int x){return x&(-x);}
inline void add(re int blo,re int x,re int k){for(;x<=n;x+=lt(x))tr[blo][x]+=k;}
inline int ask(re int blo,re int x){LL ans=0;for(;x;x-=lt(x))ans+=tr[blo][x];return ans;} 
int main()
{
    n=read(),m=read();
    rep(i,1,n)a[i]=read(),pla[a[i]]=i;
    rep(i,1,n)
    {
    	if(cnt==block)be[sum]=i-1,siz[sum]=cnt,cnt=0,sum++,bs[sum]=i;
    	ab[i]=sum;cnt++;add(sum,a[i],1);
    }
    if(cnt)be[sum]=n,siz[sum]=cnt;
    else sum--;cnt=0;
    rep(i,1,n)cnt+=i-1-ask(sum+1,a[i]),add(sum+1,a[i],1);
    while(m--)
    {
    	LL x=read(),y=pla[x];write(cnt);
		rep(i,bs[ab[y]],y-1)if(a[i]>x&&!del[i])cnt--;
		rep(i,y+1,be[ab[y]])if(a[i]<x&&!del[i])cnt--;
		rep(i,1,ab[y]-1)cnt-=siz[i]-ask(i,x);
		rep(i,ab[y]+1,sum)cnt-=ask(i,x);
		add(ab[y],x,-1);del[y]=1;siz[ab[y]]--;
    }
    return 0;
}

一些感想

我当初为啥会挖这个坑？