题目解析
线段树；二分查找；
详情参考 ACL｜通用「线段树」模板
定义二元运算符 op 和单位元 e。
使用数组 AAA，构建线段树，时间复杂度 O(N)\mathrm{O}(N)O(N)。
1. 对于赋值操作我们直接使用 sgt.set(int p, T x)，时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
2. 对于交换操作，和赋值操作类似，先使用 sgt.get(int p) 操作获取 ALA_LAL 和 ARA_RAR 的值，时间复杂度 O(1)\mathrm{O}(1)O(1)；然后再使用 sgt.set(int p, T x) 操作，时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
3. 查询区间最大值，使用 sgt.prod(l, r) 操作得出，时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
4. 在线段树上二分查找，使用 sgt.max_right(int l)，若返回值大于 RRR 则输出 −1-1−1，否则输出答案。时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
总的时间复杂度 O(N+QlogN)\mathrm{O}(N + Q\log{N})O(N+QlogN)。
AC代码
