[BZOJ 3295][操作分治] 動態逆序對

原題連結
這道題搞了我兩天左右....對於像我一樣沒有對操作分治感受深刻的人的確是比較難做的......
操作分治簡單的例子可以看這裡。
code有參考過中國的大神，所以看到很像的code不要驚訝(?
先說一下題目。

簡單的說，對於每一個刪除操作我們想要知道「當下」這個操作會刪除哪些逆序數對；顯然是那些在前面比他大的和在後面比他小的那些數字數量。

我們可以先算出原序列當中跟每個位置相關的逆序數對數量，然後要拔掉某位置的時候扣掉這個數量就可以了。不過很快就發現這樣是不對的，這些跟此位置相關的逆序數對可能在之前就被拔掉了，這樣就會多扣了一些，還需要再加回「已經被刪除並且和此數形成逆序數對的數量」。

有這個思考就比較好做了。我們先做第一個轉化：嘗試維護「被刪除的數」形成的數列。這樣子，每次的刪除操作對應到被刪除序列的插入操作；每次詢問在某位置前面並且比某數大還有在此位置後面比某數小的數字有幾個。有點經驗的童鞋大概看得出來，這其實就是一個帶修改動態區間k小問題(插入操作可以藉由一些技巧轉化為普通修改操作)，可以用持久化線段樹實現。

「不過真是不想寫持久化資結啊～～」

「那就做操作分治！！！」

一個詢問有三個維度：時間，值，位置。
我們先將所有詢問依照位置排序，這樣子我們獲得了位置的有序性。
可是還有兩個維度怎麼搞？用cdq分治把時間這個維度幹掉，這樣子成功變成了一維度的問題，我們就用BIT去做吧～～

上面是思想而非實做細節，細節可以參考註解～～

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100000+5;
const int maxm=50000+5;
int BIT_clock,n,m,c[maxn],BITvis[maxn];
inline int lowbit(int x) {return x&(-x);}
void add(int p,int x)
{
    for(;p<=n;p+=lowbit(p))
    {
        if(BITvis[p]!=BIT_clock) c[p]=0,BITvis[p]=BIT_clock;;
        c[p]+=x;
    }
}
int query(int p)
{
    int ret=0;
    for(;p;p-=lowbit(p)) if(BITvis[p]==BIT_clock) ret+=c[p];
    return ret;
}
struct Query
{
    int val,pos,qt;
    bool operator < (const Query& rhs) const {return pos<rhs.pos;}
}qu[maxm],tmp[maxm];
LL ans;
int a[maxn],cnt[maxn],f[maxm];
void cdq(int L,int R)
{
    if(L==R)
    {
        printf("%lld\n",ans);
        ans-=cnt[qu[L].pos];
        ans+=f[L];
        return;
    }
    int M=L+(R-L)/2;
    int lp=L,rp=M+1;
    // 時間<=M的到左邊遞迴，>M的到右邊遞迴
    for(int i=L;i<=R;i++)
        if(qu[i].qt<=M) tmp[lp++]=qu[i];
        else tmp[rp++]=qu[i];
    memcpy(qu+L,tmp+L,sizeof(qu[0])*(R-L+1));
    cdq(L,M);
    // Now , qu[L]~qu[M]的qt<=M , pos 遞增 , qu[M+1]~qu[R]的qt>M,pos遞增
    // 統計L~M對M+1~R的影響
    BIT_clock++;
    for(int i=M+1,j=L;i<=R;i++) // L ~ M 中在 M+1 ~ R 的前面比他大的數量
    {
        for(;j<=M && qu[j].pos<qu[i].pos;j++) add(qu[j].val,1);
        f[qu[i].qt]+=query(n)-query(qu[i].val);
    }
    BIT_clock++;
    for(int i=R,j=M;i>=M+1;i--) // L ~ M 中在 M+1 ~ R 的後面比他小的數量
    {
        for(;j>=L && qu[j].pos>qu[i].pos;j--) add(qu[j].val,1);
        f[qu[i].qt]+=query(qu[i].val);
    }
    cdq(M+1,R);
    // 把pos的有序性還回來
    lp=L;rp=M+1;
    for(int i=L;i<=R;i++)
        if((qu[lp].pos<qu[rp].pos || rp>R) && lp<=M) tmp[i]=qu[lp++];
        else tmp[i]=qu[rp++];
    memcpy(qu+L,tmp+L,sizeof(qu[0])*(R-L+1));
}
int pos[maxn];
int main()
{
    //freopen("in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {scanf("%d",a+i);pos[a[i]]=i;}
    
    ans=0;
    BIT_clock++;
    for(int i=1;i<=n;i++)
    {
        cnt[i]+=query(n)-query(a[i]);
        ans+=cnt[i];
        add(a[i],1);
    }

    BIT_clock++;
    for(int i=n;i>=1;i--)
    {
        cnt[i]+=query(a[i]-1);
        add(a[i],1);
    }
    
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&qu[i].val);
        qu[i].pos=pos[qu[i].val];
        qu[i].qt=i;
    }
    sort(qu+1,qu+1+m);
    cdq(1,m);
}