BZOJ 3295 「CQOI2011」动态逆序对

md 空间卡死窝了……

首先用常规方法求出这个序列的逆序对个数，然后每次删除就从答案中减去它对答案的贡献。
问题在于贡献怎么求。

显然，ai 对答案的贡献就是 i−1∑j=1[aj>ai]+n∑j=i+1[aj<ai]， 其中 [X] 的意义是若 X 成立则为 1 否则为 0。

那么这个东西就用树套树就好啦！ 然后一开始的逆序对个数我也顺便用了树套树。

这里是树状数组套权值线段树。

代码：

#include <cstdio>
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
#define lowbit(x) ((x) & -(x))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
int n,m;
int a[N + 10],pos[N + 10];
int rt[N + 10];
long long ans;
struct node
{
    int sz;
    int lson,rson;
} seg[N * 100 + 10];
inline int new_node()
{
    static int tot = 0;
    return ++tot;
}
void insert(int x,int k,int &p,int tl,int tr)
{
    if(!p)
        p = new_node();
    if(tl == tr)
    {
        seg[p].sz += k;
        return ;
    }
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,ls(p),tl,mid);
    else
        insert(x,k,rs(p),mid + 1,tr);
    seg[p].sz = seg[ls(p)].sz + seg[rs(p)].sz;
}
int ask(int l,int r,int p,int tl,int tr)
{
    if(!p || l > r)
        return 0;
    if(l <= tl && tr <= r)
        return seg[p].sz;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += ask(l,r,ls(p),tl,mid);
    if(r > mid)
        ret += ask(l,r,rs(p),mid + 1,tr);
    return ret;
}
inline void update(int x,int v,int k)
{
    for(;x <= n;x += lowbit(x))
        insert(v,k,rt[x],1,n);
}
inline int query(int x,int v)
{
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret += ask(1,v,rt[x],1,n);
    return ret;
}
int main()
{
    read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(a[i]),update(i,a[i],1),pos[a[i]] = i;
    for(register int i = 1;i <= n;++i)
        ans += query(i - 1,n) - query(i - 1,a[i]);
    int x;
    while(m--)
    {
        read(x);
        printf("%lld\n",ans);
        ans -= (query(pos[x] - 1,n) - query(pos[x] - 1,x)) + (query(n,x - 1) - query(pos[x],x - 1));
        update(pos[x],x,-1);
    }
}