Rockdu's Blog

Input

Output

Sample Input

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5
2
2
1

样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

Hint

N<= 100000 M <=50000

二话不说上树套树。用树状数组套平衡树。顺着蓝书上的思路走，我们不妨可以用Splay代替普通平衡树来获得更方便的查询操作。事实证明用Splay的速度也是很可观的。值得注意的是，删除操作并不用将节点直接真正的删除，而可以做一个“假删除”——把节点留下，权值为0，可以减少代码量。

这里提供一个常数巨大的代码……

#include<cstdio>
#define lowbit(x) ((x) & (-x))
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
long long ans;
int org[maxn];
inline void read(int & x) {
	x = 0;char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
}

namespace Splay {
    struct node {
        int ch[2], num, sum, cnt, fa;
    }tree[maxn * 30];
    int cnt;
    void push_up(int rt) {
        if(rt == 0) return;
        int tl = tree[rt].ch[0];
        int tr = tree[rt].ch[1];
        tree[rt].sum = tree[rt].cnt + tree[tl].sum + tree[tr].sum;
    }
    void rotate(int rt) {
        int p = tree[rt].fa;
        int a = tree[p].fa;
        int l = tree[p].ch[1] == rt;
        int r = l ^ 1;
        if(a) tree[a].ch[tree[a].ch[1] == p] = rt;
        tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[r]].fa = tree[rt].ch[r] ? p : 0;
        tree[p].ch[l] = tree[rt].ch[r], tree[rt].ch[r] = p;
        push_up(p), push_up(rt);
    }
    void splay(int x, int y, int & root) {
        int des = tree[y].fa;
        while(tree[x].fa != des) {
            int p = tree[x].fa;
            int a = tree[p].fa;
            if(a)
                if((tree[p].ch[1] == x) ^ (tree[a].ch[1] == p)) rotate(x);
                else rotate(p);
            rotate(x);
        }
        if(y == root) root = x;
        push_up(x); // 如果没有伸展 
    }
    void insert(int & root, int & now, int x, int last) {
        if(now == 0) { now = ++cnt, tree[now] = (node) {0, 0, x, 1, 1, last};
            splay(now, root, root);return ;}
        if(tree[now].num == x) {++tree[now].cnt, ++tree[now].sum, splay(now, root, root); return;}
        insert(root, tree[now].ch[tree[now].num < x], x, now);
        push_up(now);
    }
    int find(int x, int root) {
        int rt = root, last = 0, lm = 0;
        while(tree[rt].num != x && rt != 0) {
            if(tree[rt].num <= x && tree[rt].num > lm)    
                lm = tree[rt].num, last = rt;
            rt = tree[rt].ch[x > tree[rt].num];
        }
        return rt == 0 ? last : rt;
    }
    void del(int x, int & root) {
        int rt = find(x, root);
        --tree[rt].sum, --tree[rt].cnt;
        splay(rt, root, root);
    }
    int query(int x, int & root, bool type) { // 0小 1大 
        int rt = find(x, root);
        if(rt == 0)	return type ? tree[root].sum : 0;
        splay(rt, root, root);
        int ret = tree[tree[root].ch[type]].sum;
        if(x != tree[rt].num && type == 0) 
			ret += tree[rt].cnt;
        return ret;
    }
}

namespace BIT{
    int root[maxn << 4], N;
    void init(int n){N = n;}
    int add(int pos, int num) {
        while(pos <= N) Splay::insert(root[pos], root[pos], num, 0), pos += lowbit(pos);
    }
    void del(int pos, int num) {
        while(pos <= N) Splay::del(num, root[pos]), pos += lowbit(pos);
    }
    int query(int pos, int num, bool type) {
        int ret = 0;
        while(pos) {
			ret += Splay::query(num, root[pos], type);
			pos -= lowbit(pos);
        }
		return ret;
    }
}

namespace WBIT{
    int tree[maxn << 4], N;
    void init(int n) {N = n;}
    void add(int pos) {while(pos <= N) ++tree[pos], pos += lowbit(pos);}
    int query(int pos) {int ret = 0;while(pos) ret += tree[pos], pos -= lowbit(pos);return ret;}
}

int main() {
    read(n), read(m);
    int a;
    BIT::init(n); 
    WBIT::init(n);
    for(register int i = 1; i <= n; ++i) {
        read(a), org[a] = i;
        BIT::add(i, a);
        ans += i - WBIT::query(a) - 1, WBIT::add(a);
    }
    for(register int i = 1; i <= m; ++i) {
        read(a);
        long long sol1 = BIT::query(org[a], a, 1);
        long long sol2 = BIT::query(n, a, 0) - BIT::query(org[a], a, 0);
        printf("%lld\n", ans);
        ans -= (sol1 + sol2);
        BIT::del(org[a], a);
    }  
    return 0;
}