DS 好闪，拜谢 DS。
考虑二进制的情况怎么做，那这两个操作就变成了取反和全局加 \(1\)。
建 01-trie，如果是 \(01\) 反转的话打交换儿子的标记即可。考虑全局加 \(1\)，最后一位 \(01\) 状态反转，并且反转后为 \(0\) 的位置会对前面的位有进位。递归 \(0\) 链并顺路交换左右儿子即可。
然后考虑三进制，其实是相同的：
建三进制 trie，\(1\) 操作相当于交换 \(1,2\) 两个儿子；全局加 \(1\) 就是原本的 \(0\) 儿子变成 \(1\) 儿子、\(1\) 儿子变成 \(2\) 儿子，以此类推。同样顺着 \(0\) 链递归交换即可，单次修改 \(O(n)\)。
所以每个点上维护其 \(3\) 个儿子的编号、反转标记以及当前值对应的下标即可。
总复杂度 \(O(3^n+Tn)\)，太厉害了。