头脑游戏

MSIAhgdAHAGOOOOAybcsiQOSDhsm.

[ARC154D] A + B > C ?

先看看什么是我们容易得到的：排列的边界情况要么是 \(1\) 要么是 \(n\)，对于 \(n\)，我们并不能方便的找到什么性质，但是对于 \(1\)，\(1+1=2 \not >\operatorname{others}\)，而且 \(1\) 容易和大于号联系起来。

再观察一下询问：可以问三个数，自由度太高了啊？考虑令 \(i=j\)，即询问 \(2p_i\) 与 \(p_k\) 的大小关系。

类似打擂台地，假设 \(1\) 的位置为 \(x\)，初始时令 \(x=1\)，然后从 \(2 \sim n\) 枚举 \(i\)，如果 \(2p_i \not> p_x\)，那么 \(i \to x\)，这样，我们就找到了 \(2p_i\) 最小值的位置，也就是 \(1\) 的位置。

接下来，我们已经有了 \(p_x=1\)，接下来如果询问 i x j 会怎样呢？会返回 \(p_i+1\) 是否 \(>p_j\)，也就是 \(p_i\) 是否 \(\ge p_j\)，这样，我们就得到了比较操作。

我们要还原整个排列，而排列是性质非常好的，比如说，某个数的值与它的排名相等，所以，可以考虑将 \(p\) 排序，花费 \(n \log n\) 次操作。

我们通过排列的常用性质，加强限制，一些简单而实用的技巧解决了此题。