QOJ 9801 Dot Product Game 题解

和上一篇一起的。

怎么置换群还在追我。

根据排序不等式，显然答案最大是就是排列 对应位置的数完全相同的时候。我们其实并不在乎下标，只在乎对应的值。因此我们不妨固定 ，先将 排序，对应调整 序列的位置，将对 的操作转化到对 的操作上。

显然这个游戏就变成了两个人分别选择一对 中的元素并交换。由于你需要点积增加，因此逆序对必须减少，所以游戏不可能永远进行。不妨把 看作一个置换，恒同变换是死局（已经排好序的情况）。非死局任何一次操作都会使得置换的奇偶性改变（因为你进行了一次对换），归纳一下发现就是偶置换必败，奇置换必胜。

可以根据“逆序对奇偶性等于置换奇偶性”来求出置换的奇偶性。接下来考虑修改操作。对 的修改可以对应到 上。具体的，在 上的 等同于在 上进行 ，不难发现这样之后对应的元素是相同的（再次强调我们并不在乎下标）。

我们再次考虑对 排序的那个过程，发现这个过程等同于给 复合上 的逆。令 为所有修改操作复合起来的结果，因此我们最后关心的是 的奇偶性。单个轮换的奇偶性是容易计算的，其等于 ，因此 的奇偶性是好确定的。并且，由于恒同变换是偶置换，因此 和 奇偶性相同。因此里面每一项都确定了。

▶

INFO 参考代码

#include <algorithm>
#include <iostream>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace ds {
    ull lowbit(ull x) { return x & -x; }

    struct bit {
        std::vector<ull> t;
        void add(uint pos, ull val) {
            if (pos == 0) {
                t[pos] += val;
                return;
            }
            for (; pos < t.size(); pos += lowbit(pos)) {
                t[pos] += val;
            }
            return;
        }

        ull query(uint pos) {
            ull ret = 0;
            for (; pos; pos -= lowbit(pos)) {
                ret += t[pos];
            }
            ret += t[pos];
            return ret;
        }

        bit(uint n) : t(n) {}
    };
}; // namespace ds

namespace solve {
    struct solver {
        uint n;

        bool is_even(std::vector<uint> v) {
            std::reverse(v.begin(), v.end());

            ull cnt = 0;

            ds::bit b(n);

            for (size_t i = 0; i < n; i++) {
                cnt += b.query(v[i]);
                b.add(v[i], 1);
            }

            return cnt & 1;
        }

        void solve() {
            std::cin >> n;
            std::vector<uint> a(n), b(n);
            for (size_t i = 0; i < n; i++) {
                std::cin >> a[i];
                a[i]--;
            }
            for (size_t i = 0; i < n; i++) {
                std::cin >> b[i];
                b[i]--;
            }
            bool ret = is_even(a) ^ is_even(b);
            std::cout << (ret ? "A" : "B");

            for (size_t i = 0; i < n - 1; i++) {
                char c;
                uint l, r, t;
                std::cin >> c >> l >> r >> t;
                l--, r--;
                r++;
                uint len = r - l;
                t %= len;
                if (c == 'A') {
                    t = len - t;
                }
                ret ^= (t & 1) * ((len - 1) & 1);
                std::cout << (ret ? "A" : "B");
            }
            std::cout << "\n";
            return;
        }
    };

} // namespace solve

int main() {
    uint t;
    std::cin >> t;
    while (t--) {
        solve::solver s;
        s.solve();
    }
    std::cout << std::flush;
    return 0;
}

/**
 * 好的。
 *
 * 我们不妨固定 a 不动。
 *
 * 根据排序不等式，反正就是两个都是正序的时候最大。
 *
 * 因此我们将 a 排序，同时交换 b 对应元素的位置。
 *
 * 这样我们可以转化成两个人都操作 b 中的元素。
 *
 * 我们再次考虑一下。
 *
 * 首先有一个结论就是逆序对数等于置换奇偶性。
 *
 * 因此偶置换显然先手赢，否则后手。
 *
 * 然后相当于是先复合上 b 在符合 a 的逆。
 *
 * 此时如果是偶数置换就是先手赢。
 *
 * 轮换的话，我们把 a 上的轮换转化成 b 上的逆。
 *
 * 然后轮换的奇偶性是已知的。结束。
 *
 * 考虑简单证明一下那个逆序对数等于偶置换数。
 *
 * 显然根据定义你就证完了。
 *
 * 或者有一个简单的理解方法。把中间的元素排列。
 *
 *  ------ i ----- j -----
 *
 * 我们假设 i 在前面，j 在后，我们要换 i 到 j。
 *
 * 比 i 小的元素会对逆序对产生 -1 的贡献，比 i 大的就是 +1。
 * j 的话比 j 小的会有 +1 的贡献，否则就是 -1。
 *
 * 所有的摸 2 就抵消了。
 *
 * 因此就是交换 i j 的逆序对变化。
 *
 * 结束！
 */

后面应该还有一篇和扫描线有关的题解。另外我其实并不是认为这是一个诈骗题，感觉就是一个有点意思的群论题目啊。