这是本文档旧的修订版！
补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 2 | 0 | 0 |
| C | 0 | 0 | 0 |
| D | 0 | 0 | 0 |
| E | 0 | 0 | 0 |
| G | 0 | 0 | 0 |
| J | 0 | 0 | 0 |
| K | 0 | 0 | 0 |
题解
B. xay loves monotonicity
题意
给定一个序列 $A$ 和序列 $B$，其中 $0\le b_i\le 1$ 接下来三种操作：
- $a_i\gets t$
- 对 $l\le i\le r$，$b_i\gets b_i\oplus 1$
- 给定 $l,r$。选取最长下标序列 $l\le i_1\le i_2\le \cdots i_k\le r$，满足 $a_{i_1}\le a_{i_2}\le\cdots \le a_{i_k}$，且对任意 $i_t\lt j\lt i_{t+1}$ 有 $a_j\lt a_{i_t}$。
对每个操作 $3$，输出 $b_{i_t}\neq b_{i_{t+1}}$ 的个数。
题解
设 $ma(L,R)=\max(a[L\sim R]),mb(L,R)$ 表示 $ma(L,R)$ 对应的 $b_i$，如果存在多个就取最右边的。
设 $\text{query}(L,R,p,q)$ 表示假如当前序列末尾对应 $a_i=p,b_i=q$ 时遍历区间 $(L,R)$ 得到的答案。
于是，如果 $a_i\gt ma(L,M)$，则 $\text{query}(L,R,p,q)=\text{query}(M+1,R,p,q)$。
否则，有 $\text{query}(L,R,p,q)=\text{query}(L,M,p,q)+\text{query}(M+1,R,ma(L,M),mb(L,M))$。
建立线段树，每个区间维护 $\text{query}(M+1,R,ma(L,M),mb(L,M))$。
这样，对一个询问，如果该询问正好对应一个线段树区间，则查询复杂度 $O(\log n)$。
否则，将该询问拆分成 $O(\log n)$ 个线段树区间，串联查询计算答案，时间复杂度 $O(\log^2 n)$。
对与修改操作，修改完暴力询问更新 $\text{query}(M+1,R,ma(L,M),mb(L,M))$，由于这是线段树区间，所以复杂度为 $O(\log n)$。
所以修改的总复杂度也是 $O\left(\log^2 n\right)$。总时间复杂度 $O\left(n\log n+q\log^2 n\right)$。
ps. 比赛写了 $O(nq)$ 的假算法，居然过了。
