自动搬运

查看原文

来自洛谷，原作者为

	Y204335 **

搬运于2025-08-24 22:33:29，当前版本为作者最后更新于2024-10-25 15:41:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[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;
}