题解：AT_agc079_c [AGC079C] Sort by Queue and Reverse

P2441M · 2026-11-13 17:11:59 · 题解

不难发现，每次加入一个数后，立刻输出所有当前应该输出的数显然不劣，所以如果忽略反转操作，只考虑添加、弹出操作，那么整个长度为 2n 的操作序列可以唯一确定。

为了方便，可以把队列视作双端队列，反转操作相当于切换队列的队首方向，不妨用 0/1 标记。设 a_x 表示添加 x 时的队首方向，b_x 表示弹出 x 时的队首方向。

设 S 为当前队列内的数，当加入一个新的数 x 时，考察每个 y\in S：

使用带权并查集维护 2n 个变量，出现矛盾就判无解。

这个判定也是充分的，若当前需要输出 x，考察每个队列内的 y>x：

• 若 y 在 x 之前被加入，则第二个条件保证了 x 从被添加的一端弹出，不会被堵住。
• 若 y 在 x 之后被加入，则第一个条件保证了弹出 x 的一端与加入 y 的一端相反，同样不会堵住。

直接做有 \mathcal{O}(n^2) 条约束，考虑优化。

对 S 从小到大排序，<x 的数构成一段前缀。观察到对于 S 中相邻的两个数 u<v，若已经有 b_u=b_v，则我们完全可以把 u 扔掉，只保留 b_v 跟其他的 a 合并就好了。因此我们再用一个 set 维护 T，对于 S 中相邻的两个数 u<v，若 v\notin T，则表示我们已经确定 b_u=b_v。

添加 x 时：

• 取 S 中的最小元素 y，若 y<x，则将 b_y,a_x 合并。
• 不断取出 T 中 <x 的元素 y，将 b_y,a_x 合并，再把 y 从 T 中删除。

然后再把 x 添加到 S 中，在 T 中处理增加的 \mathcal{O}(1) 个相邻对。

这样时间复杂度就优化到了 \mathcal{O}(n\log{n})。

现在考虑如何最小化反转次数。对于长为 2n 的操作序列，如果固定每个操作对应的队首方向 dir_i\in\{0,1\}，那么反转次数就是 \sum\limits_{i=1}^{2n-1}(dir_i\oplus dir_{i+1})。一个变量 x 的 dir 可以写成 d_x\oplus X，其中 d_x 表示带权并查集中 x 到根的路径异或和，X 表示 x 对应的连通块是否整体反转。因此我们需要为每个连通块决策是否整体反转。

感觉上不太好做，不妨进一步观察性质。图中的边都形如 (a_x,b_y)，其中 y\leq x。把边画到操作序列上，观察到不同连通块的边不会相交。具体来说，考察边 (a_{x_1},b_{y_1}) 和 (a_{x_2},b_{y_2})，它们满足在操作序列中的出现顺序为 a_{x_1},a_{x_2},b_{y_1},b_{y_2}，显然 y_1<y_2\leq x_2，因此 x_2 被加入时必然会向 y_1,y_2 连边，于是这两条边必然来自同一个连通块。

因此可以考察同一连通块中的点在操作序列中的相邻出现 u,v，设 u,v 之间夹着的连通块从左到右依次是 C_1,\cdots,C_k，显然我们总能通过反转使得 u 和 C_1 连接处、相邻区间连接处方向相同，那么这里需要额外的反转，当且仅当做了前面的反转处理后，C_k 和 v 连接处方向不同。设 \operatorname{first}(C),\operatorname{last}(C) 分别表示 C 在操作序列中第一次、最后一次出现的位置，于是我们计算 d_u\oplus d_{\operatorname{first}(C_1)}\oplus d_{\operatorname{last}(C_1)}\oplus\cdots\oplus d_{\operatorname{first}(C_k)}\oplus d_{\operatorname{last}(C_k)}\oplus d_v 即可。

用栈维护连通块的嵌套结构，对每个连通块维护第一次、最后一次出现对应的 d 和子区间累积的异或和即可。

总体时间复杂度为 \mathcal{O}(n\log{n})。

:::success[代码]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int MAXN = 2.5e5 + 5;

template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }

int tc, n, p[MAXN], pos[MAXN << 1];

struct DSU {
    int fa[MAXN << 1], d[MAXN << 1];

    void init(int n) {
        iota(fa + 1, fa + n + 1, 1);
        fill(d + 1, d + n + 1, 0);
    }

    int find(int x) {
        if (x == fa[x]) return x;
        int f = fa[x];
        fa[x] = find(fa[x]);
        d[x] ^= d[f];
        return fa[x];
    }

    bool unite(int x, int y, int z) {
        int fx = find(x), fy = find(y);
        z ^= d[x] ^ d[y];
        if (fx == fy) return !z;
        fa[fx] = fy;
        d[fx] = z;
        return true;
    }
} dsu;

struct Info {
    int rt, first, lst, sum;
};

int top;
Info stk[MAXN << 1];

int solve() {
    dsu.init(n * 2);

    set<int> s, t;
    vector<int> ord;
    int cur = 1;

    for (int i = 1; i <= n; ++i) {
        int x = p[i];
        if (!s.empty() && *s.begin() < x && !dsu.unite(*s.begin() + n, x, 0)) return -1;
        if (!s.empty() && *s.rbegin() > x && !dsu.unite(x + n, x, 1)) return -1;
        while (!t.empty() && *t.begin() < x) {
            int y = *t.begin();
            if (!dsu.unite(y + n, x, 0)) return -1;
            t.erase(t.begin());
        }
        auto it = s.insert(x).first;
        if (it != s.begin()) t.insert(x);
        if (++it != s.end()) t.insert(*it);

        ord.emplace_back(x);
        while (!s.empty() && *s.begin() == cur) {
            ord.emplace_back(cur + n);
            ++cur;
            s.erase(s.begin());
            if (!s.empty()) t.erase(*s.begin());
        }
    }

    int ans = 0;
    for (int u : ord) pos[dsu.find(u)] = u;
    for (int u : ord) {
        int r = dsu.find(u), w = dsu.d[u];
        if (!top || stk[top].rt != r) {
            stk[++top] = {r, w, w, 0};
        } else {
            auto &v = stk[top];
            ans += v.lst ^ w ^ v.sum;
            v.lst = w;
            v.sum = 0;
        }
        if (pos[r] == u) {
            int v = stk[top--].first ^ w;
            if (top) stk[top].sum ^= v;
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> p[i];
        cout << solve() << '\n';
    }

    return 0;
}

:::