洛谷P3157 [CQOI2011]动态逆序对

zrzring 2020-10-22 PM 82℃ 0条

逆序对加一个时间轴,三维偏序问题,考虑cdq解决

如果我们要维护每一对逆序对对每个时间的贡献的话,计算答案时时间一维会影响每一组逆序对的计算贡献

具体来说,如果一对数分别在$t_1 + 1$时刻和$t_2 + 1$时刻被删除,这对逆序对会在$1$到$min(t_1, t_2)$时间有贡献,于是每一对逆序对都受较小的时间影响,所以我们把时间放在第一维限制

逆序对的定义为$pos_i < pos_j, val_i > val_j$或$pos_i < pos_j, val_i > val_j$

分别在cdq中正反各跑一边计算贡献,最后再归并排序,快排也可以,但复杂度多一个$log$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define lowbit(x) (x & -x)

using namespace std;

const int N = 1e5 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct NODE {
    int pos, x, t;
} dat[N], _dat[N];

int n, m, cnt, pos[N];

struct TREE {
    long long sum[N];
    void add(int x, int t) {for (int i = x; i <= n; i += lowbit(i)) sum[i] += t;}
    long long query(int x) {long long res = 0; for (int i = x; i; i -= lowbit(i)) res += sum[i]; return res;}
} Ta, Tb;

bool cmp(NODE a, NODE b) {return a.t == b.t ? a.pos == b.pos ? a.x < b.x : a.pos < b.pos : a.t < b.t;}

void cdq(int l, int r) {
    if (l >= r) return; int mid = l + r >> 1;
    cdq(l, mid); cdq(mid + 1, r); int p = l, p1 = mid, p2 = r;
    while (p1 >= l) {
        while (p2 >= mid + 1 && dat[p1].pos < dat[p2].pos) Ta.add(dat[p2--].x, 1);
        int t = Ta.query(dat[p1].x); Tb.add(1, t); Tb.add(dat[p1--].t + 1, -t);
    }
    for (int i = r; i > p2; i--) Ta.add(dat[i].x, -1); p1 = l, p2 = mid + 1;
    while (p1 <= mid) {
        while (p2 <= r && dat[p1].pos > dat[p2].pos) Ta.add(dat[p2].x, 1), _dat[p++] = dat[p2++];
        int t = Ta.query(n) - Ta.query(dat[p1].x); Tb.add(1, t); Tb.add(dat[p1].t + 1, -t); _dat[p++] = dat[p1++];
    }
    for (int i = mid + 1; i < p2; i++) Ta.add(dat[i].x, -1);
    for (int i = l; i < p2; i++) dat[i] = _dat[i];
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) {dat[i].x = read(); dat[i].pos = pos[dat[i].x] = i;}
    for (int i = 1; i <= m; i++) {int t = read(); dat[pos[t]].t = i;}
    for (int i = 1; i <= n; i++) if (!dat[i].t) dat[i].t = m + 1; sort(dat + 1, dat + n + 1, cmp);
    cdq(1, n);
    for (int i = 1; i <= m; i++) printf("%lld\n", Tb.query(i));
    return 0;
}
Title - Artist
0:00