论如何在键盘的大部分标点符号都坏掉的情况下实现逆序对

chengyifan91 · 2025-12-11 17:01:44 · 休闲·娱乐

（本人平时并不擅长 C++，很多内容和真实语法有偏差，还请见谅。另外，本文中的符号指不能在 C++ 语言中作为变量名的可见字符。）

起因

受到 机房大佬的文章 启发，我就在想既然排序都能用 %:<>() 这 6 种符号实现，那解决 逆序对 又何尝不行呢？于是我就去寻找逆序对中优秀的实现，找到了可能比较好实现 3 种：

• 归并排序求逆序对。
• 动态开点权值线段树。
• 树状数组+离散化。

被淘汰的算法

归并排序需要用到递归，然而只用 %:<>() 想要实现递归是及其困难的，于是归并排序和线段树就遗憾离场了。

一些小技巧

要写树状数组，加减法，那么如何实现且保证复杂度呢？

替代运算符

在 C++ 中，有一种东西叫做替代运算符，下面是一些会用到的替代运算符：

比较搞笑的是，bitand 还可以作为引用变量使用。

还有一些字符不是运算符，但是也可以被两个字符替代，这是早期 C++ 为了防止大家的键盘上没有一些字符而提供的。

我们发现这些替代字符恰好都在允许使用的字符的范围内！

不过有很多运算符都是没有替代运算符的，但是我们可以自己实现，比如 a = b 就是 a xor_eq b xor a，a == b 就是 not (a xor b)，a <= b 就是 a < b or not (a xor b)，等等。

加法

我们已经知道了替代运算符，那怎么用这些运算符完成加减法呢？首先，给出一种 O(\log V) 的加法。

我们发现在加法和异或的本质区别就是加法存在进位，因此我们可以将两个数的和转为异或和以及进位两个部分，即 a+b=a\ \mathrm{xor}\ b+2(a\ \mathrm{bitand}\ b)，我们发现只要一直 a'\gets a\ \mathrm{xor}\ b,b'=2(a\ \mathrm{bitand}\ b)，然后 a\gets a',b\gets b' 直到 a\ \mathrm{bitand}\ b=0 即可。

:::info[复杂度证明] 假设 a\ \mathrm{bitand}\ b 的最低位是 k。

进行一步转化后 b'=2(a\ \mathrm{bitand}\ b) 的最低位是 k+1，此时 a'\ \mathrm{bitand}\ b' 的最低位一定会 >k，也就是说，一步转化至少会让 k 增加 1。

我们发现 k 肯定不会超过 \left\lceil\log V\right\rceil，因此复杂度为 O(\log V)。 :::

while (a bitand b) <%
    if (a xor_eq b) <%%>
    if (b and_eq a xor b) <%%>
    if (b xor_eq b xor (b << 1)) <%%>
%>
if (a or_eq b) <%%>

在 C++ 中，-b=\mathrm{compl}\ b+1，因此我们可以将 a-b 转换为 a+\mathrm{compl}\ b+1。

回到正题

接下来，我们就可以开始实现逆序对了！

需要用到的头文件：iostream，ranges，vector，algorithm，建议使用 C++ 20。

离散化

离散化同样有很多种实现，比如 lower_bound、map 和直接 sort 等等。这里我使用了手写 lower_bound 的方法。

先声明一些变量，由于有符号的限制，我们可以用 for (auto name : {x}) 来声明一个变量，也就是遍历一个只有一个元素的初始化列表。

for (int n : <%0%>)
for (long long ans : <%0%>) <%
    if (std::cin >> n) <%%>
    for (auto a : <%std::vector<int>(n)%>)
    for (auto b : <%std::vector<int>(n)%>)
    for (auto tr : <%std::vector<int>(n<<1)%>) <%

其中 tr 的下标从 1 开始，因此需要开到比 n 还大一点，刚好我们有 << 可以用，所以就开到了 n<<1。

接下来就是真正的离散化部分了。

for (int i : std::views::iota(0) bitor std::views::take(n)) <%
    for (int l : <%0%>) for (int r : <%n%>) for (int res : <%0%>) <% // res 是二分结果
        for (int b : <%static_cast<int>(0xffffffffU)%>) <% // static_cast<int>(0xffffffffU) 是 -1，这段代码相当于 r--
            while (r bitand b) <%
                if (r xor_eq b) <%%>
                if (b and_eq r xor b) <%%>
                if (b xor_eq b xor (b << 1)) <%%>
            %>
            if (r or_eq b) <%%>
        %>
        while (l < r or not (l xor r)) <% // l <= r，闭区间二分
            for (int mid : <%l%>) <%
                // 这一部分相当于 mid = (l + r) >> 1
                for (int b : <%r%>) <%
                    while (mid bitand b) <%
                        if (mid xor_eq b) <%%>
                        if (b and_eq mid xor b) <%%>
                        if (b xor_eq b xor (b << 1)) <%%>
                    %>
                    if (mid or_eq b) <%%>
                %>
                if (mid xor_eq mid xor (mid >> 1)) <%%>
                // 二分判断，b[mid] >= a[i]
                if (b<:mid:> > a<:i:> or not (b<:mid:> xor a<:i:>)) <%
                    if (res xor_eq res xor mid) <%%> // res = mid
                    if (r xor_eq r xor mid) <%%> // r = mid
                    for (int b : <%static_cast<int>(0xffffffffU)%>) <% // r--
                        while (r bitand b) <%
                            if (r xor_eq b) <%%>
                            if (b and_eq r xor b) <%%>
                            if (b xor_eq b xor (b << 1)) <%%>
                        %>
                        if (r or_eq b) <%%>
                    %>
                %> else <%
                    if (l xor_eq l xor mid) <%%> // l = mid
                    for (int b : <%1%>) <% // l++
                        while (l bitand b) <%
                            if (l xor_eq b) <%%>
                            if (b and_eq l xor b) <%%>
                            if (b xor_eq b xor (b << 1)) <%%>
                        %>
                        if (l or_eq b) <%%>
                    %>
                %>
            %>
        %>
        if (a<:i:> xor_eq a<:i:> xor res) <%%> // a[i] = res
    %>
%>

树状数组

然后就是激动人心的树状数组部分了。树状数组的核心就是 lowbit，但是我们发现 lowbit(x) 显然硬求比 x & (-x) 更好写，常数更小，于是就可以这样实现：

for (auto l : <%1%>) <%
    while (not (x bitand 1)) <%
        if (l xor_eq l xor (l << 1)) {}
        if (x xor_eq x xor (x >> 1)) {}
    %>
%>

当然实际实现会有些不一样。

先声明变量

for (int i : std::views::iota(0) bitor std::views::take(n)) <%
    for (int x : <%a<:i:>%>) <%

然后由于树状数组的下标从 1 开始，于是我们需要将 x+1。

for (int b : <%1%>) <%
    while (x bitand b) <%
        if (x xor_eq b) <%%>
        if (b and_eq x xor b) <%%>
        if (b xor_eq b xor (b << 1)) <%%>
    %>
    if (x or_eq b) <%%>
%>

正常的树状数组求 > x 的和需要用到总和减去 \le x 的和，然而我们不需要再写一次树状数组查出总和，因为第 i 个位置的总和就是 i-1，也就是当前的下标。于是需要先将答案 +i。

for (long long b : <%i%>) <%
    while (ans bitand b) <%
        if (ans xor_eq b) <%%>
        if (b and_eq ans xor b) <%%>
        if (b xor_eq b xor (b << 1)) <%%>
    %>
    if (ans or_eq b) <%%>
%>

然后是查询 \le x 的和并更新答案。

for (int t : <%x%>) for (int l : <%0%>) <% // l 用于求 lowbit
    while (t) <%
        for (long long b : <%tr<:t:>%>) <% // ans += ~tr[t]
            if (b xor_eq b xor compl b) <%%>
            while (ans bitand b) <%
                if (ans xor_eq b) <%%>
                if (b and_eq ans xor b) <%%>
                if (b xor_eq b xor (b << 1)) <%%>
            %>
            if (ans or_eq b) <%%>
        %>
        for (long long b : <%1%>) <% // ans++，ans += ~tr[t]+1 相当于 ans -= tr[t]
            while (ans bitand b) <%
                if (ans xor_eq b) <%%>
                if (b and_eq ans xor b) <%%>
                if (b xor_eq b xor (b << 1)) <%%>
            %>
            if (ans or_eq b) <%%>
        %>
        if (l xor_eq l xor 1) <%%> // l = 1
        for (int tmp : <%t%>) <% // 求 l
            while (not (tmp bitand 1)) <%
                if (l xor_eq l xor (l << 1)) <%%>
                if (tmp xor_eq tmp xor (tmp >> 1)) <%%>
            %>
        %>
        if (t xor_eq l) <%%>
    %>
%>

最后是单点修改。

for (int t : <%x%>) for (int l : <%0%>) <%
    while (t < n or not (t xor n)) <% // t <= n
        for (int b : <%1%>) <% // tr[t]++
            while (tr<:t:> bitand b) <%
                if (tr<:t:> xor_eq b) <%%>
                if (b and_eq tr<:t:> xor b) <%%>
                if (b xor_eq b xor (b << 1)) <%%>
            %>
            if (tr<:t:> or_eq b) <%%>
        %>
        if (l xor_eq l xor 1) <%%> // l = 1
        for (int tmp : <%t%>) <% // 求 lowbit
            while (not (tmp bitand 1)) <%
                if (l xor_eq l xor (l << 1)) <%%>
                if (tmp xor_eq tmp xor (tmp >> 1)) <%%>
            %>
        %>
        while (t bitand l) <% // t += l
            if (t xor_eq l) <%%>
            if (l and_eq t xor l) <%%>
            if (l xor_eq l xor (l << 1)) <%%>
        %>
        if (t or_eq l) <%%> 
    %>
%>

完整代码

%:include<iostream>
%:include<ranges>
%:include<vector>
%:include<algorithm>

int main() <%
    if (std::ios::sync_with_stdio(0)) <%%>
    for (int n : <%0%>) for (long long ans : <%0%>) <%
        if (std::cin >> n) <%%>
        for (auto a : <%std::vector<int>(n)%>) for (auto b : <%std::vector<int>(n)%>) for (auto tr : <%std::vector<int>(n<<1)%>) <%
            for (auto bitand i : a) if (std::cin >> i) <%%>
            for (int i : std::views::iota(0) bitor std::views::take(n)) if (b<:i:> xor_eq a<:i:>) <%%>
            for (auto i : <%std::ranges::sort(b)%>) <%%>
            for (int i : std::views::iota(0) bitor std::views::take(n)) <%
                for (int l : <%0%>) for (int r : <%n%>) for (int res : <%0%>) <%
                    for (int b : <%static_cast<int>(0xffffffffU)%>) <%
                        while (r bitand b) <%
                            if (r xor_eq b) <%%>
                            if (b and_eq r xor b) <%%>
                            if (b xor_eq b xor (b << 1)) <%%>
                        %>
                        if (r or_eq b) <%%>
                    %>
                    while (l < r or not (l xor r)) <%
                        for (int mid : <%l%>) <%
                            for (int b : <%r%>) <%
                                while (mid bitand b) <%
                                    if (mid xor_eq b) <%%>
                                    if (b and_eq mid xor b) <%%>
                                    if (b xor_eq b xor (b << 1)) <%%>
                                %>
                                if (mid or_eq b) <%%>
                            %>
                            if (mid xor_eq mid xor (mid >> 1)) <%%>
                            if (b<:mid:> > a<:i:> or not (b<:mid:> xor a<:i:>)) <%
                                if (res xor_eq res xor mid) <%%>
                                if (r xor_eq r xor mid) <%%>
                                for (int b : <%static_cast<int>(0xffffffffU)%>) <%
                                    while (r bitand b) <%
                                        if (r xor_eq b) <%%>
                                        if (b and_eq r xor b) <%%>
                                        if (b xor_eq b xor (b << 1)) <%%>
                                    %>
                                    if (r or_eq b) <%%>
                                %>
                            %> else <%
                                if (l xor_eq l xor mid) <%%>
                                for (int b : <%1%>) <%
                                    while (l bitand b) <%
                                        if (l xor_eq b) <%%>
                                        if (b and_eq l xor b) <%%>
                                        if (b xor_eq b xor (b << 1)) <%%>
                                    %>
                                    if (l or_eq b) <%%>
                                %>
                            %>
                        %>
                    %>
                    if (a<:i:> xor_eq a<:i:> xor res) <%%>
                %>
            %>
            for (int i : std::views::iota(0) bitor std::views::take(n)) <%
                for (int x : <%a<:i:>%>) <%
                    for (int b : <%1%>) <%
                        while (x bitand b) <%
                            if (x xor_eq b) <%%>
                            if (b and_eq x xor b) <%%>
                            if (b xor_eq b xor (b << 1)) <%%>
                        %>
                        if (x or_eq b) <%%>
                    %>
                    for (long long b : <%i%>) <%
                        while (ans bitand b) <%
                            if (ans xor_eq b) <%%>
                            if (b and_eq ans xor b) <%%>
                            if (b xor_eq b xor (b << 1)) <%%>
                        %>
                        if (ans or_eq b) <%%>
                    %>
                    for (int t : <%x%>) for (int l : <%0%>) <%
                        while (t) <%
                            for (long long b : <%tr<:t:>%>) <%
                                if (b xor_eq b xor compl b) <%%>
                                while (ans bitand b) <%
                                    if (ans xor_eq b) <%%>
                                    if (b and_eq ans xor b) <%%>
                                    if (b xor_eq b xor (b << 1)) <%%>
                                %>
                                if (ans or_eq b) <%%>
                            %>
                            for (long long b : <%1%>) <%
                                while (ans bitand b) <%
                                    if (ans xor_eq b) <%%>
                                    if (b and_eq ans xor b) <%%>
                                    if (b xor_eq b xor (b << 1)) <%%>
                                %>
                                if (ans or_eq b) <%%>
                            %>
                            if (l xor_eq l xor 1) <%%>
                            for (int tmp : <%t%>) <%
                                while (not (tmp bitand 1)) <%
                                    if (l xor_eq l xor (l << 1)) <%%>
                                    if (tmp xor_eq tmp xor (tmp >> 1)) <%%>
                                %>
                            %>
                            if (t xor_eq l) <%%>
                        %>
                    %>
                    for (int t : <%x%>) for (int l : <%0%>) <%
                        while (t < n or not (t xor n)) <%
                            for (int b : <%1%>) <%
                                while (tr<:t:> bitand b) <%
                                    if (tr<:t:> xor_eq b) <%%>
                                    if (b and_eq tr<:t:> xor b) <%%>
                                    if (b xor_eq b xor (b << 1)) <%%>
                                %>
                                if (tr<:t:> or_eq b) <%%>
                            %>
                            if (l xor_eq l xor 1) <%%>
                            for (int tmp : <%t%>) <%
                                while (not (tmp bitand 1)) <%
                                    if (l xor_eq l xor (l << 1)) <%%>
                                    if (tmp xor_eq tmp xor (tmp >> 1)) <%%>
                                %>
                            %>
                            while (t bitand l) <%
                                if (t xor_eq l) <%%>
                                if (l and_eq t xor l) <%%>
                                if (l xor_eq l xor (l << 1)) <%%>
                            %>
                            if (t or_eq l) <%%>
                        %>
                    %>
                %>
            %>
            if (std::cout << ans) <%%>
        %> 
    %>
%>

提交记录：点这里。

更多的思考

除了刚才那三个算法，难道就没有可以用的算法了吗？当然有！我们可以使用分块！虽然 O(n\sqrt n\log n) 只能获得 50 分，但是这也给了我们启发：分块是可以用六种特殊字符完成的。

由于没有满分，就不放提交记录了，只给出完整代码，感兴趣的读者可以尝试优化到满分（虽然不太可能）。

%:include<iostream>
%:include<algorithm>
%:include<ranges>
%:include<cmath>
%:include<vector>

int main() <%
    if (std::ios::sync_with_stdio(0)) <%%>
    for (int n : <%0%>) if (std::cin >> n) 
    for (int B : <%std::sqrt(n)%>) 
    for (long long ans : <%0%>)
    for (auto a : std::array<%std::vector<int>(n)%>)
    for (auto b : <%std::vector<int>(n)%>)
    for (auto sum : <%std::vector<int>(n)%>)
    for (auto mp : <%std::vector<int>(n)%>)
    for (auto pos : <%std::vector<int>(n)%>)
    for (auto l : <%std::vector<int>(n)%>)
    for (auto r : <%std::vector<int>(n)%>) <%
        for (auto bitand i : a) if (std::cin >> i) <%%> 
        for (int i : std::views::iota(0) bitor std::views::take(n)) if (b<:i:> xor_eq a<:i:>) <%%>
        for (auto i : <%std::ranges::sort(b)%>) <%%>
        for (int i : std::views::iota(0) bitor std::views::take(n)) <%
            for (int l : <%0%>)
            for (int r : <%n%>) 
            for (int res : <%0%>) <%
                for (int b : <%0xffffffff%>) <% while (r bitand b) <% if (r xor_eq b) <%%> if (b and_eq r xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (r or_eq b) <%%> %>
                while (l < r or not (l xor r)) <%
                    for (int mid : <%l%>) <%
                        for (int b : <%r%>) <% while (mid bitand b) <% if (mid xor_eq b) <%%> if (b and_eq mid xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (mid or_eq b) <%%> %>
                        if (mid xor_eq mid xor (mid >> 1)) <%%>
                        if (b<:mid:> > a<:i:> or not (b<:mid:> xor a<:i:>)) <%
                            if (r xor_eq r xor mid) <%%>
                            for (int b : <%0xffffffff%>) <% while (r bitand b) <% if (r xor_eq b) <%%> if (b and_eq r xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (r or_eq b) <%%> %>
                            if (res xor_eq res xor mid) <%%>
                        %> else <%
                            if (l xor_eq l xor mid) <%%>
                            for (int b : <%1%>) <% while (l bitand b) <% if (l xor_eq b) <%%> if (b and_eq l xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (l or_eq b) <%%> %>
                        %>
                    %>
                %>
                if (a<:i:> xor_eq a<:i:> xor res) <%%>
            %>
        %>
        for (int i : <%0%>) 
        for (int t : <%0%>) <%
            while (i < n) <%
                for (int b : <%1%>) <% while (t bitand b) <% if (t xor_eq b) <%%> if (b and_eq t xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (t or_eq b) <%%> %>if (l<:t:> xor_eq i) <%%> 
                for (int j : <%i%>) <%
                    for (int b : <%B%>) <% while (i bitand b) <% if (i xor_eq b) <%%> if (b and_eq i xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (i or_eq b) <%%> %>
                    while (j < i and j < n) <%
                        if (pos<:j:> xor_eq t) <%%>
                        if (r<:t:> xor_eq r<:t:> xor j) <%%>
                        for (int b : <%1%>) <% while (j bitand b) <% if (j xor_eq b) <%%> if (b and_eq j xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (j or_eq b) <%%> %>
                    %>
                %>
            %>
        %>
        for (int i : std::views::iota(0) bitor std::views::take(n)) <%
            for (long long b : <%i%>) <% while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
            if (pos<:a<:i:>:> xor 1) <%
                for (int j : <%0%>) while (j < r<:1:> or not (j xor r<:1:>)) <%
                    for (long long b : <%mp<:j:>%>) <% if (b xor_eq b xor compl b) <%%> while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>            
                    for (int b : <%1%>) <% while (j bitand b) <% if (j xor_eq b) <%%> if (b and_eq j xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (j or_eq b) <%%> %>
                    for (long long b : <%1%>) <% while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
                %>
                for (int j : <%2%>) while (j < pos<:a<:i:>:>) <%
                    for (long long b : <%sum<:j:>%>) <% if (b xor_eq b xor compl b) <%%> while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
                    for (int b : <%1%>) <% while (j bitand b) <% if (j xor_eq b) <%%> if (b and_eq j xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (j or_eq b) <%%> %>
                    for (long long b : <%1%>) <% while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
                %>
                for (int j : <%l<:pos<:a<:i:>:>:>%>) while (j < a<:i:> or not (j xor a<:i:>)) <%
                    for (long long b : <%mp<:j:>%>) <% if (b xor_eq b xor compl b) <%%> while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>            
                    for (int b : <%1%>) <% while (j bitand b) <% if (j xor_eq b) <%%> if (b and_eq j xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (j or_eq b) <%%> %>
                    for (long long b : <%1%>) <% while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
                %>
            %> else <%
                for (int j : <%0%>) while (j < a<:i:> or not (j xor a<:i:>)) <%
                    for (long long b : <%mp<:j:>%>) <% if (b xor_eq b xor compl b) <%%> while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
                    for (int b : <%1%>) <% while (j bitand b) <% if (j xor_eq b) <%%> if (b and_eq j xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (j or_eq b) <%%> %>
                    for (long long b : <%1%>) <% while (ans bitand b) <% if (ans xor_eq b) <%%> if (b and_eq ans xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (ans or_eq b) <%%> %>
                %>
            %>
            for (int b : <%1%>) <% while (mp<:a<:i:>:> bitand b) <% if (mp<:a<:i:>:> xor_eq b) <%%> if (b and_eq mp<:a<:i:>:> xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (mp<:a<:i:>:> or_eq b) <%%> %>
            for (int b : <%1%>) <% while (sum<:pos<:a<:i:>:>:> bitand b) <% if (sum<:pos<:a<:i:>:>:> xor_eq b) <%%> if (b and_eq sum<:pos<:a<:i:>:>:> xor b) <%%> if (b xor_eq b xor (b << 1)) <%%> %> if (sum<:pos<:a<:i:>:>:> or_eq b) <%%> %>
        %>
        if (std::cout << ans) <%%>
    %> 
%>

结语

关于扣字符的理论还有很多可以研究，比如是否可以用线段树和归并排序完成（尽管在这题是不可能的），比如再去实现更加困难的题目，以及其他很多研究。

感谢机房同学的帮助，才有了这篇文章。

研究 C++ 语法，其乐无穷也！