记录编号	358093	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	3.811 s
提交时间	2016-12-14 08:57:19	内存使用	127.32 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
using namespace std;
#define MAXN 100002
struct node
{
    node *ls, *rs;
    int cnt;
};
inline node *new_node()
{
    static node pool[MAXN*110], *pp =  pool;
    return pp++;
}
void insert(node *&x, int l, int r, int p, int d)
{
    //node *k;
    //if(!x)k = new_node();
    //else {
     //   k = new_node();
     //   *k = *x;
   // }
    if(!x)x = new_node();
    x -> cnt += d;
    if(l < r)
    {
        int m = (l+r)>>1;
        if(p <= m)insert(x->ls, l, m, p, d);
        if(p > m)insert(x->rs, m+1, r, p, d);        
    }
}
                       //好吧= =主席树还是这样写跑得快...
int query(node *x, int l, int r, int L, int R)
{
    if(!x)return 0;
    if(L <= l && r <= R)return x->cnt;
    int m = (l+r)>>1, ret= 0;
    if(L <= m)ret += query(x->ls, l, m, L, R);
    if(m < R)ret += query(x->rs, m+1, r, L, R);
    return ret;
}
int n, m, pos[MAXN], a[MAXN];
node *C[MAXN];
inline void add(int x, int v, int d)
{
    for(; x <= n; x += x&-x)
        insert(C[x], 1, n, v, d);
}
typedef long long LL;
inline LL ask(int l, int r, int L, int R)
{
    LL ret = 0;
    for(int i = r; i; i -= i&-i)ret += query(C[i], 1, n, L, R);
    for(int i = l-1; i; i -= i&-i)ret -= query(C[i], 1, n, L, R);
    return ret;
}
int main()
{
   // freopen("test_data.txt", "r", stdin);
    freopen("inverse.in", "r", stdin);
    freopen("inverse.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", a+i);pos[a[i]] = i;
        add(i, a[i], 1);
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++)
        ans += ask(1, i-1, a[i]+1, n)+ask(i+1, n, 1, a[i]-1);
    ans >>= 1;
    while(m--)
    {
        int v;
        printf("%lld\n", ans);
        scanf("%d", &v); v = pos[v];
        ans -= ask(1, v-1, a[v]+1, n)+ask(v+1, n, 1, a[v]-1);
        add(v, a[v], -1);
    }
    return 0;
}