记录编号	347125	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	shallwe	是否通过	通过
代码语言	C++	运行时间	4.821 s
提交时间	2016-11-12 20:49:13	内存使用	100.52 MiB

// #include <bits/stdc++.h>
/*
5 4
1
5
3
4
2
5
1
4
2
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 100010;
const int B = 320;
struct block {
    int mir[N], pre[B];
} b[B];
int bit[N], n, m, a[N], del[N], pla[N], bel[N], blen, tot;
bool exi[N], away[N];
long long ans[N], rev;
// bit - 权值树状数组；
inline void in(int &x) {
    char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (x=0; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - 48;
}
inline void add(int x, int val) {
    for (; x <= n; x += x & (-x) ) bit[x] += val;
}
inline int query(int x, int sum = 0) {
    for (; x ; x -= x & (-x) ) sum += bit[x];
    return sum ;
}
inline void blockquery(int &nm, int &sm, int val) {
    // cout << val << ": " ;
    int p = pla[val], blo = bel[p], i; nm = sm = 0;
    // cout << p << ' ' << blo << endl;
    for (i = 1; i < blo; ++i) {
        // cout <<i << ", " << b[i].pre[blen] << " " << b[i].pre[b[i].mir[val]] << endl;
        nm += b[i].pre[blen], sm += b[i].pre[b[i].mir[val]];
    }
    if (p % blen == 0)
        nm += b[blo].pre[blen], sm += b[blo].pre[b[blo].mir[val]];
    else
        for (i = (blo - 1) * blen + 1; i < p ; ++i)
            if (!away[a[i]]) ++nm , sm += (a[i] < val);
}
inline void blockadd(int x) {
    away[x] = 0; int p = pla[x], blo = bel[p], i;
    for (i = b[blo].mir[x]; i <= blen; ++i)
        ++b[blo].pre[i] ;
}
int main() {
    freopen("inverse.in", "r", stdin);
    freopen("inverse.out", "w", stdout); 
    in(n), in(m); int i, j, x, totnm, small, k;
    for (blen = 1; blen * blen <= n; ++blen); -- blen; if (!blen) blen = 1;
    // cout << blen << endl;
    for (i = 1; i <= n; ++i) in(a[i]), pla[a[i]] = i; // pla[x] 权值x的位置
    for (i = 1; i <= m; ++i) in(del[i]), away[del[i]] = 1; //删除标记
    // for (i = 1; i <= n; ++i) cout << away[a[i]] << ' '; cout << endl;
    for (i = 1, j = 1; i * blen <= n; ++i, j+=blen) {
        for (k = 1; k <= blen; ++k)
            x = j + k - 1, exi[a[x]] = 1, bel[x] = i; //bel 所属的块
        for (tot = 0, k = 1; k <= n; ++k )
            if (exi[k]) b[i].mir[k] = ++tot;
            else b[i].mir[k] = b[i].mir[k-1]; // mir -> 权值 映射
        // for (k = 1; k <= n; ++k)
        // cout << b[i]. mir[k] << ' '; cout << endl;
        for (k = 1; k <= blen; ++k) {
            x = j + k - 1, exi[a[x]] = 0;
            if (!away[a[x]])  {
                // cout << x << endl;
                ++b[i].pre[b[i].mir[a[x]] ];
            }
        }
        for (k = 1; k <= tot; ++k)
            b[i]. pre[k] += b[i].pre[k-1]; //块内前缀
        // for (k = 1; k <= tot; ++k)
        //     cout << b[i].pre[k] <<' '; cout << endl;
    }
    for (; j <= n; ++j) bel[j] = i;
    // for (i = 1; i <= n; ++i) cout << bel[i] << ' '; cout << endl;
    for (i = 1, tot = 0; i <= n; ++i)
        if (!away[a[i]])
            rev += tot - query(a[i]), add(a[i], 1), ++tot;
    // cout << rev << endl;
    // 剩余数的逆序对数；
    for (i = m; i ; --i) {
        x = del[i];
        tot = query(x), blockquery(totnm, small, x);
        // cout << tot << ' ' << small << ' ' << totnm << endl;
        rev += tot - small + totnm - small;
        ans[i] = rev; add(x, 1), blockadd(x);
    }
    for (i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}