T245311 有理有据题

（K-D Tree练习题）

一个秘密组织制造了 $n$ 个反物质炸弹，打算对一个军事基地进行打击。这个军事基地中有一些建筑，每个建筑可以看作笛卡尔坐标系上的一个线段，其中第i个建筑为的两个端点为 $(i,a_i)$ ，$(i,b_i)$ ，其中 $ai\le bi$ 。一开始在军事基地中已经发现了 $m$ 个建筑，编号 $1$ 到 $m$ 。 这 $n$ 个反物质炸弹的爆破能力也是不同的，这些炸弹经过特殊的设计，第i枚炸弹的爆炸范围为一个左下角坐标为 $(-\infty,l_i)$，右上角坐标为 $(+\infty,r_i)$ 的矩形。假如一个建筑线段上的有一个点被炸弹爆破到，则这个建筑可认为被摧毁。 现在有一些事件发生： (1) $A\ \ a_x\ \ b$，在军事基地中又发现了一个新建筑，假设已经发现了 $x-1$ 个建筑，那么新发现的这个即为第 $x$ 个，在坐标系中的线段端点为 $(x,a_x)$ , $(x,b_x)$ 。 (2) $C\ \ x$，查询第 $x$ 个反物质炸弹能摧毁的最长连续区间的长度，即要求 $[l,r]$ 内的建筑都能被 $x$ 号炸弹摧毁， $r-l+1$ 的最大值。如果没有建筑会被摧毁，那么这个最大值可认为是 $0$ 。 (3) $Q$，求出所有 $n$ 个反物质炸弹能摧毁的最长连续区间的长度的异或和。 设 $A、C、Q$ 分别为三种操作的数量，则总事件数为 $A＋C＋Q$ 。请维护这三种操作。

第一行三个正整数分别为 $n，m，A＋C＋Q$ 的值。 接下来 $n$ 行，每行两个正整数 $l_i,r_i$ ，为第 $i$ 号反物质炸弹的爆破参数。接下来 $m$ 行，每行两个正整数 $a_i,b_i$ ，为第 $i$ 号建筑的纵坐标范围。接下来 $A＋C＋Q$ 行，每行描述一个事件，格式详见问题描述或样例。

输出 $C+Q$ 行，每行为对应操作的答案。

所有数据范围内都有一定梯度。 对于 $10\%$ 的数据，$n, m,A,C ≤1000，Q = 1$ 。 对于另 $10\%$ 的数据， $n