P7833 [CCO2021] Loop Town题解

· · 题解

[CCO2021] Loop Town

题目大意

有一个长 l 的环，有 n 个人，他们有初始顺序 a 和最终顺序 b，要求给每个人规定路线，使得路线交叉次数最少。

题目分析

两人路线的交叉其实相当于交换这两人的相对位置，题目也就是问每次可以交换相邻的两人，最少多少次交换可以把初始顺序变为最终顺序。

如果这是在链上，其实就是经典的逆序对问题，但很容易就能发现逆序对在环上是没有意义的，但逆序对描述的部分性质在环上仍然成立，逆序对描述的是一种包含关系，即 a_i<a_j<b_j<b_i，在这种情况下显然一定需要一次交换。同样在环上，这种包含关系也一定需要一次交换，但不同的是，像 b_i<a_j<a_i<b_j 这样的情况，在链上一定要交换，而在环上则不一定。

考虑如何处理，在环上所有人都向同一方向走一定是不劣的（显然如果方向不同，则如 a_i<a_j<b_i<b_j 的情况可能产生额外的贡献），这里钦定向右。

可以处理出每条路线被其他几条路线包含，在离散化后处理每条路线，使用树状数组可以实现 O(n\log n) 的处理，但是由于在环上，终点和起点的相对位置可以改变，从而改变路线，所以要处理 n 次，总复杂度为 O(n^2\log n)。

考虑优化，由于是整体平移，位置的相对关系是不变的，所以只有当平移后出现了 a_i=b_i 的情况，路线完全发生变化（从一路向右一圈变为直接到达，如下图），包含关系发生变化，答案才会改变。

考虑平移 b 后贡献的变化情况，从而能从之前的答案直接转移，设 path_i 为 i 从 a_i 向右走直到 b_i 的路线上点的集合（可以从 n 走到 1）。

  1. 当 path_i 完全改变时，原来满足 path_j\subset path_i 的 j 将不再满足条件，而 path_i 在完全变化前一定是首尾相接的（如上图），此时只有当 j 满足 a_i\in path_j 时（由于 a_i 互不相同，所以不会出现重叠的情况），path_j\not\subset path_i，所以减少的贡献可以由 n-sum_{a_i\in path_j} 算出（注意此处的 j 可以等于 i）。
  2. 当 path_i 完全改变时，原来不满足 path_i\subset path_j 的 j 可能满足条件，j 满足条件当且仅当 a_i\in path_j，新增贡献也就是 sum_{a_i\in path_j}。

可以发现，贡献的变化只和每一时刻的 sum_{a_i\in path_j} 相关，考虑快速计算 sum_{a_i\in path_j}，由于 b 为一个 1\dots n 的排列（指离散化后，不难发现中间状态是无用的），所以每一次平移 b 后一定有一个新的 j 使得 b_j=a_i，也就是一定会有一个新的 j 满足 a_i\in path_j，此时 sum_{a_i\in path_j} 一定加一，但由于当 a_i=b_i 时路线会完全变化，所以要减去 sum_{a_i=b_i}，这样就能从上一时刻的 sum_{a_i\in path_j} 转移到当前时刻。

可以先朴素处理初始的答案，用差分处理初始时刻的 sum_{a_i\in path_j}，并把每个人挂到对应能使得 a_i=b_i 的平移次数上，之后再计算每次平移后的答案以及 sum_{a_i\in path_j}，答案取最小值即可。

初始处理为 O(n\log n)，之后每次平移均摊复杂度为 O(1)，总时间复杂度为 O(n\log n)。

注：处理初始答案时，有多种包含的情况，代码中使用了 3 个树状数组，相应处理的情况以注释给出；在处理初始时刻的 sum_{a_i\in path_j} 时，在对差分前缀和后，要把每一个点的值减一，去掉自身；在计算每次平移的答案时，第一种情况（贡献减少）中，由于出现 a_i=b_i 的时，新的满足 a_i\in path_j 的 j 就是 i，此时就会把 i 算上，如果算初始 sum_{a_i\in path_j} 不减去自身，在此处就会算重；由于在代码中 sum_{a_i\in path_j} 在答案之后更新，贡献变化的第二种情况（贡献增加）中的 j 显然不能在这一时刻满足 a_j=b_j，所以要还要减去 sum_{a_i=b_i}，并且由于这一时刻满足 a_i\in path_j 的 j 就是 i 而多算上的自身也会在这里被消掉。

代码

#include <bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int n, l, id[N], lsh[N], pre[N];
ll ans, res, cnt;
pair<int, int> a[N];
vector<int> x[N];
struct tree {
    int tr[N];
    tree()
    {
        memset(tr, 0, sizeof(tr));
    }
    void upd(int x, int w)
    {
        while (x <= n) {
            tr[x] += w;
            x += x & -x;
        }
    }
    int quary(int x)
    {
        int res = 0;
        while (x) {
            res += tr[x];
            x -= x & -x;
        }
        return res;
    }
} tr1, tr2, tr3; // 1 A-B-B-A  2 -B-B-A A- 3 -B-A A-B-
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fir >> a[i].sec;
        lsh[i] = a[i].sec;
    }
    sort(a + 1, a + n + 1);
    sort(lsh + 1, lsh + n + 1);
    for (int i = 1; i <= n; i++) {
        id[i] = lower_bound(lsh + 1, lsh + n + 1, a[i].sec) - lsh;
    }
    for (int i = 1; i <= n; i++) {
        if (id[i] < i) {
            tr2.upd(id[i], 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i <= id[i]) {
            pre[i]++;
            pre[id[i] + 1]--;
            x[n - (id[i] - i)].push_back(i);
            res += tr1.quary(n) - tr1.quary(id[i] - 1);
            res += tr2.quary(n) - tr2.quary(id[i] - 1);
            tr1.upd(id[i], 1);
        } else {
            pre[1]++;
            pre[id[i] + 1]--;
            pre[i]++;
            x[i - id[i]].push_back(i);
            res += tr3.quary(n) - tr3.quary(id[i] - 1);
            tr1.upd(n, 1);
            tr3.upd(id[i], 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        pre[i] += pre[i - 1];
    }
    for (int i = 1; i <= n; i++) { // self
        pre[i]--;
    }
    ans = res;
    for (int i = 1; i < n; i++) { //-->
        for (auto j : x[i]) {
            res += (pre[j] + i - cnt - x[i].size()) - (n - (pre[j] + i - cnt));
        }
        cnt += x[i].size();
        ans = min(ans, res);
    }
    cout << ans;
    return 0;
}