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

Pig_Eat_Earth · 2025-01-11 20:08:29 · 题解

P9310题解

题目大意

给定一个长度为 2n 的正整数序列，保证所有 1\le i\le n 恰好出现两次，有以下两种操作，求清空序列的最小操作数：

• 交换相邻两个元素
• 删除两个相邻且相等的元素（让情侣去约会）

  解法 A

  思路

  明显地，删除操作的次数恒为 n，因此只需要找出一个操作序列使得交换次数最少。
  观察发现通过交换让一对情侣排在一起的操作次数等于他们之间间隔的人数。
  考虑贪心。按照间隔人数升序依次操作，每次答案加上他们之间还剩余的人数。
  维护剩余人数需要进行单点修改、区间查询操作（即对于一次约会操作，需要查询区间内剩余人数，然后删除一对情侣）。于是考虑采用树状数组。

  时间复杂度

  树状数组初始化：O(n)。
  贪心排序：O(n)。
  “约会”操作：每对情侣约会一次，树状数组 O(\log n)，共 O(n\log n)。
  总时间复杂度：O(n\log n)。
  注：树状数组初始化可以在输入时完成，具体见代码

  对于贪心正确性的证明

  假设有两对情侣，位置分别为 a_1/a_2 以及 b_1/b_2，满足 a_1<a_2 且 b_1<b_2 且 a_2-a_1<b_2-b_1。由上述贪心策略可以得知，情侣 a 应在情侣 b 前约会。下证 b 在 a 前约会，答案不会变好（有可能变差）。

• • - 分类讨论 a 与 b 的位置关系。
    注：证明过程中所求两次操作答案均不考虑其他情侣的影响，因为其他情侣对顺序交换与否的答案的影响相等
    1. a_1<a_2<b_1<b_2$ 或 $b_1<b_2<a_1<a_2

       无影响。

    2. a_1<b_1<a_2<b_2$ 或 $b_1<a_1<b_2<a_2

       顺序不交换，则 a 的交换次数为 a_2-a_1，b 的交换次数为 b_2-b_1-1。
       顺序交换，则 b 的交换次数为 b_2-b_1，a 的交换次数为 a_2-a_1-1。
       可得，无论顺序交换与否，两次操作总交换次数均为 (a_2-a_1)+(b_2-b_1)-1。

    3. b_1<a_1<a_2<b_2

       顺序不交换，则 a 的交换次数为 a_2-a_1，b 的交换次数为 b_2-b_1-2。
       顺序交换，则 b 的交换次数为 b_2-b_1，但 \because b_1,b_2\notin [a_1,a_2]，\therefore a 的交换次数仍为 a_2-a_1。
       在此情况中，顺序不交换比交换更优。

综上，顺序不交换比交换更优或一样。一般地，操作顺序应按情侣间隔人数多少升序排列。

证毕。

AC Code

#include <bits/stdc++.h>
#define int long long //记得开long long 
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 5e5, A = N << 1;
int n, a[A + 5], tr[A + 5], ans;
struct CP{
    int n, f, s;
} cp[N + 5];

bool cmp(CP a, CP b){
    return a.s - a.f < b.s - b.f;
}

void mns(int x){ for(; x <= (n << 1); x += lowbit(x)) -- tr[x]; }

int get(int x){
    int res = 0;
    for(; x; x -= lowbit(x)) res += tr[x];
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    ans = n;
    for(register int i = 1; i <= (n << 1); ++ i){
        cin >> a[i];
        (cp[a[i]].f ? cp[a[i]].s : cp[a[i]].f) = i;
        tr[i] = lowbit(i); // 树状数组全部置1 
    }
    for(register int i = 1; i <= n; ++ i) cp[i].n = i;
    sort(cp + 1, cp + n + 1, cmp);
    for(register int i = 1; i <= n; ++ i){
        ans += get(cp[i].s - 1) - get(cp[i].f);
        mns(cp[i].f);
        mns(cp[i].s);
    }
    cout << ans;
    return 0;
}

解法 B

思路

准备好一个“栈”。
遍历 a 数组，如果该元素不在栈中（第一次出现），则入栈；否则（第二次出现），将答案加上栈内该元素到栈顶的距离，并弹出栈内该元素。
考虑到一般的栈无法实现任意查询与弹出，使用树状数组模拟“栈”。

时间复杂度

对于 a 数组中的每一个元素，都要使用树状数组进行查改，故时间复杂度为 O(n\log n)。

AC Code

考试代码，没开 long long 拿了 84。

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
using namespace std;
int n, a[1000006], tim[500005], tot, tr[500005];

void add(int x){
    tim[x] = ++ tot;
    for(register int i = tot; i <= n; i += lowbit(i)) ++ tr[i];
}

void del(int x){
    for(register int i = tim[x]; i <= n; i += lowbit(i)) -- tr[i];
    tim[x] = 0;
}

int get(int x){
    int res = 0;
    for(; x; x -= lowbit(x)) res += tr[x];
    return res;
}

void solve(){ //一开始想暴力骗分，题解中删掉了
    long long ans = n; // 只需要这里开long long
    for(register int i = 1; i <= (n << 1); ++ i){
        if(tim[a[i]]){
            ans += get(tot) - get(tim[a[i]]);
            del(a[i]);
        }
        else add(a[i]);
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(register int i = 1; i <= (n << 1); ++ i) cin >> a[i];
    solve();
    return 0;
}

注意事项

long long