P14513 [NFLSPC #8] 追忆desuwa

Zhengxu Sakiko 是一位著名的算法竞赛选手。只不过他由于记性太差经常忘记学过的算法。 这就是为什么他常常追忆过去。

请注意本题特殊的空间限制。 给定 $m$ 个三元组 $(l,r,v)$。 有 $q$ 个操作，每次给出 $x,y$，表示查询 $l\le x\le r$ 且 $v\le y$ 的三元组中，$v$ 的最大值是多少。 如果不存在满足条件的三元组，输出 $0$。 本题强制在线。

第一行两个整数 $m,q$。 接下来 $m$ 行每行三个整数表示一组 $(l,r,v)$。 接下来 $q$ 行每行两个整数 $p,q$ 表示当前询问满足 $x=p\oplus ans,y=q\oplus ans$，其中 $\oplus$ 表示异或操作，$ans$ 表示上次询问的答案和 $2^{21}-1$ 按位与的值。初始的 $ans$ 是 $0$。

对于每个询问输出一行表示答案。

### 数据范围 |子任务名称|子任务编号|分值|限制 |:-:|:-:|:-:|:-:| |用脚维护|1|25|空间限制为 2048MiB| |不劳而获|2|25|$q\le 3\times 10^4$| |数据结构大师|3|25|$q\le 10^5$| |我即是虚像|4|25|无特殊限制| 对于所有数据：$1\le m,q\leq 10^6,1\le l\le r\le 2\times 10^6, 0\le v>1; int L{B[x].rk0(i)},R{B[x].rk0(j)}; if (R-L>=k) return qry(L,R,k,l,mid,x+1); else return qry(pos[x]+B[x].rk1(i),pos[x]+B[x].rk1(j),k-(R-L),mid,r,x+1); } } tr; int main() { int n,m;read(n,m); vector a(n); for (int i=0;i