又一道坑了很久没有写题解的……

删除操作特别的棘手，但好在我们可以离线~时光倒流之后，删除就变成了添加。

每个点加进来之后，对答案的贡献可以分为两部分：

1. 加入比他早，位置在他前面，值比他大的点。
2. 加入比他早，位置在他后面，值比他小的点。

然后两者都可以用CDQ统计（我还偷懒用同一个CDQ做的）。

代码：

/**************************************************************
    Problem: 3295
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2332 ms
    Memory:5768 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using std::stack;
using std::sort;
const int maxn = 100005;
typedef long long ll;
struct Query {
    int id;
    int p, v;
};
 
int n;
ll C[maxn];
int lowbit(int x) {
    return x & (-x);
}
void add(int p, int v) {
    while(p <= n) {
        C[p] += v;
        p += lowbit(p);
    }
}
ll sum(int p) {
    ll ret = 0;
    while(p > 0) {
        ret += C[p];
        p -= lowbit(p);
    }
    return ret;
}
int query(int l, int r) {
    return sum(r) - sum(l - 1);
}
void clean(int p) {
    while(p <= n && C[p] != 0) {
        C[p] = 0;
        p += lowbit(p);
    }
}
 
Query A[maxn], tmp[maxn];
ll ans[maxn];
void CDQ(int L, int R, bool flag) {
    if(L == R) {
        return;
    }
    int M = L + (R - L) / 2;
    CDQ(L, M, flag); CDQ(M + 1, R, flag);
    for(int p = L, l = L, r = M + 1; p <= R; p ++) {
        if(r > R || (l <= M && (flag ? A[l].p < A[r].p : A[l].p > A[r].p))) {
            tmp[p] = A[l];
            add(A[l].v, 1);
            l ++;
        } else {
            tmp[p] = A[r];
            ans[A[r].id] += query(A[r].v + 1, n);
            r ++;
        }
    }
    for(int i = L; i <= M; i ++) {
        clean(A[i].v);
    }
    for(int i = L; i <= R; i ++) {
        A[i] = tmp[i];
    }
}
bool cmp_id(const Query& a, const Query& b) {
    return a.id < b.id;
}
 
int arr[maxn];
bool del[maxn];
int pos[maxn];
stack<int> delS;
int main() {
    int m;
    scanf("%d%d", &n, &m);
    int id_siz = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= m; i ++) {
        int a;
        scanf("%d", &a);
        delS.push(a);
        del[a] = true;
    }
    for(int i = 1; i <= n; i ++) {
        if(del[arr[i]]) {
            pos[arr[i]] = i;
        } else {
            id_siz ++;
            A[id_siz].id = id_siz;
            A[id_siz].p = i;
            A[id_siz].v = arr[i];
        }
    }
    while(!delS.empty()) {
        int a = delS.top(); delS.pop();
        id_siz ++;
        A[id_siz].id = id_siz;
        A[id_siz].p = pos[a];
        A[id_siz].v = a;
    }
    CDQ(1, n, true);
    sort(A + 1, A + 1 + n, cmp_id);
    for(int i = 1; i <= n; i ++) {
        A[i].v = n - A[i].v + 1;
    }
    CDQ(1, n, false);
    for(int i = 1; i <= n; i ++) {
        ans[i] += ans[i - 1];
    }
    for(int i = 0; i < m; i ++) {
        printf("%lld\n", ans[n - i]);
    }
    return 0;
}

• 相关文章
• 全局相关文章