P9310 [EGOI2021] Luna likes Love / 卢娜爱磕 cp 题解

zxrL23 · 2023-08-07 20:08:36 · 题解

思路

首先提出策论。

从前往后枚举。我们每找到一个在之前出现过的数时，我们把前面的相同的数的位置后到当前数的位置前的所有未被删除的数移动到当前数的后面，这里需要中间未被删除的数的个数此操作，然后删掉两个相邻的数，需要一次操作。

证明这种策略的正确性。对于两个相同的数，显然他们中间的数要么配对删掉，要么移出去。对于需要配对删掉的数，由于我们是顺序枚举，所以区间内的相同数对已经被删除了，那我们只需要把剩下的数移走。在每次移动，删除了相同的数后，剩下的数的相对位置时没有变的。所以移动到前面还是后面都不影响，因为我们已经把相同的数对删掉，只剩下一定要移动的，显然是最优的。

由于相对位置不会改变，我们用线段树维护区间内未被删除的数的个数，计算每次需要操作时的操作数。时间复杂度 O(n\log n)。

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

i64 read() {
    i64 f = 0, k = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') { k = -1; }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        f = (f << 1) + (f << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f * k;
}

const int maxn = 1e6 + 10;

int a[maxn], t[maxn << 2], p[maxn];

void build(int p, int l, int r) {
    if (l == r) {
        t[p] = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

void update(int p, int l, int r, int x, int y) {
    if (l == r) {
        t[p] = y;
        return ;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
        update(p << 1, l, mid, x, y);
    } else {
        update(p << 1 | 1, mid + 1, r, x, y);
    }
    t[p] = t[p << 1] + t[p << 1 | 1];
}

int query(int p, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
        return t[p];
    }
    int mid = l + r >> 1, res = 0;
    if (L <= mid) {
        res += query(p << 1, l, mid, L, R);
    }
    if (R > mid) {
        res += query(p << 1 | 1, mid + 1, r, L, R);
    }
    return res;
}

int main() {
    int n = read();
    for (int i = 1; i <= (n << 1); i++) {
        a[i] = read();
    }
    build(1, 1, n << 1);
    i64 ans = 0;
    for (int i = 1; i <= (n << 1); i++) {
        if (p[a[i]] == 0) {
            p[a[i]] = i;
        } else {
            ans += query(1, 1, n << 1, p[a[i]], i) - 2 + 1;
            update(1, 1, n << 1, p[a[i]], 0);
            update(1, 1, n << 1, i, 0);
        }
    }
    printf("%lld\n", ans);
    return 0;
}