「Bzoj 3295」「CQOI2011」动态逆序对 (带修主席树 / CDQ分治)

发表于 | 分类于 | | + s

BZOJ 3295
题意：给定一个排列，每次删一个数，求整个序列逆序对。

先求出原序列逆序对
维护一个数前面比他大的数的个数$a_1$, 后面比他小的数的个数$a_2$
本题删除一个数，那么当前答案减去$a_1[i-1], a_2[i+1]​$
但是考虑删掉的数不会贡献答案，用一个带修主席树维护被删的数的个数，在主席树上二分找比某数小某数大即可。

本题也可以CDQ分治，显然是个三维偏序

我们把删除反过来看作添加新数字，然后考虑$(T_i, x_i, y_i)$，$T_i$为插入时间，$x_i$为位置，$y_i$为值

将第一维排序，第二维 CDQ，第三维树状数组维护

带修主席树

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 100000 + 5;

    LL n, m, a[MAXN], pos[MAXN], a1[MAXN], a2[MAXN], ans;

    LL c[MAXN];
    LL lowbit(LL x) {return x & (-x);}
    void add(LL x, LL v) {for (LL i = x; i <= n; i += lowbit(i)) c[i] += v;}
    LL query(LL x) {LL ret = 0; for (LL i = x; i > 0; i -= lowbit(i)) ret += c[i]; return ret;}

    #define M ((l + r) >> 1)
    LL lc[MAXN * 50], rc[MAXN * 50], sumv[MAXN * 50], rt[MAXN], xx[MAXN], yy[MAXN], sz;
    void update(LL &now, LL l, LL r, LL x, LL v) {
        if (!now) now = ++sz;
        sumv[now] += v;
        if (l == r) return ;
        if (x <= M) update(lc[now], l, M, x, v); else update(rc[now], M + 1, r, x, v);
    }
    LL queryLarger(LL x, LL y, LL v) {
        for (LL i = x; i; i -= lowbit(i)) xx[i] = rt[i];
        for (LL i = y; i; i -= lowbit(i)) yy[i] = rt[i];
        LL l = 1, r = n, ans = 0;
        while (l < r) {
            if (v <= M) {
                for (LL i = x; i; i -= lowbit(i)) ans -= sumv[rc[xx[i]]];
                for (LL i = y; i; i -= lowbit(i)) ans += sumv[rc[yy[i]]];
                for (LL i = x; i; i -= lowbit(i)) xx[i] = lc[xx[i]];
                for (LL i = y; i; i -= lowbit(i)) yy[i] = lc[yy[i]];
                r = M;
            } else {
                for (LL i = x; i; i -= lowbit(i)) xx[i] = rc[xx[i]];
                for (LL i = y; i; i -= lowbit(i)) yy[i] = rc[yy[i]];
                l = M + 1;
            }
        }
        return ans;
    }
    LL querySmaller(LL x, LL y, LL v) {
        for (LL i = x; i; i -= lowbit(i)) xx[i] = rt[i];
        for (LL i = y; i; i -= lowbit(i)) yy[i] = rt[i];
        LL l = 1, r = n, ans = 0;
        while (l < r) {
            if (v <= M) {
                for (LL i = x; i; i -= lowbit(i)) xx[i] = lc[xx[i]];
                for (LL i = y; i; i -= lowbit(i)) yy[i] = lc[yy[i]];
                r = M;
            } else {
                for (LL i = x; i; i -= lowbit(i)) ans -= sumv[lc[xx[i]]];
                for (LL i = y; i; i -= lowbit(i)) ans += sumv[lc[yy[i]]];
                for (LL i = x; i; i -= lowbit(i)) xx[i] = rc[xx[i]];
                for (LL i = y; i; i -= lowbit(i)) yy[i] = rc[yy[i]];
                l = M + 1;
            }
        }
        return ans;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), pos[a[i]] = i;
        for (LL i = 1; i <= n; ++i) ans += (a1[i] = i - 1 - query(a[i])), add(a[i], 1);
        ms(c, 0);
        for (LL i = n; i; --i) a2[i] = query(a[i] - 1), add(a[i], 1);

        while (m--) {
            LL x; scanf("%lld", &x), printf("%lld\n", ans);
            x = pos[x];
            ans -= (a1[x] + a2[x] - queryLarger(1 - 1, x - 1, a[x]) - querySmaller(x + 1 - 1, n, a[x]));
            for (int i = x; i <= n; i += lowbit(i)) update(rt[i], 1, n, a[x], 1);
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

CDQ分治：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 100000 + 5;

    LL n, m, a[MAXN], pos[MAXN], ans[MAXN];

    struct data {
        LL t, x, y;
        bool operator < (const data &rhs) const {
            if (x == rhs.x) return y < rhs.y;
            return x < rhs.x;
        }
    } xw[MAXN], b[MAXN];

    bool cmp(data u, data v) {return u.t < v.t;}

    LL c[MAXN], stp[MAXN];
    LL lowbit(LL x) {return x & (-x);}
    void add(LL x, LL v) {for (LL i = x; i <= n; i += lowbit(i)) c[i] += v;}
    LL query(LL x) {LL ret = 0; for (LL i = x; i > 0; i -= lowbit(i)) ret += c[i]; return ret;}

    void CDQ(LL l, LL r) {
        if (l >= r) return ; 
        LL mid = (l + r) >> 1;
        CDQ(l, mid), CDQ(mid + 1, r);
        int t1 = l, t2 = mid + 1, tot = 0, totstp = 0;
        while (t1 <= mid || t2 <= r) {
            if (t2 > r || (t1 <= mid && xw[t1] < xw[t2])) {
                add(xw[t1].y, 1), stp[++totstp] = xw[t1].y;
                b[++tot] = xw[t1++];
            } else {
                ans[xw[t2].t] += query(n) - query(xw[t2].y - 1);
                b[++tot] = xw[t2++];
            }
        }
        for (int i = l; i <= r; ++i) xw[i] = b[i - l + 1];
        for (int i = 1; i <= totstp; ++i) add(stp[i], -1); // clear

        totstp = 0;
        for (int i = r; i >= l; --i) {
            if (xw[i].t <= mid) add(xw[i].y, 1), stp[++totstp] = xw[i].y;
            else ans[xw[i].t] += query(xw[i].y);
        }
        for (int i = 1; i <= totstp; ++i) add(stp[i], -1); // clear

    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), pos[a[i]] = i, xw[i] = (data){0, i, a[i]};
        LL tmp = n;
        for (LL x, i = 1; i <= m; ++i) scanf("%lld", &x), xw[pos[x]].t = tmp--;
        for (LL i = 1; i <= n; ++i) if (!xw[i].t) xw[i].t = tmp--;
        sort(xw + 1, xw + 1 + n, cmp);

        CDQ(1, n);

        for (LL i = 1; i <= n; ++i) ans[i] += ans[i - 1];

        for (LL i = n; i >= n - m + 1; --i) printf("%lld\n", ans[i]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------