bzoj#P2674. Attack
Attack
题目描述
chnlich 非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。
他的敌人有 座城市和 个太守,N个城市可以看作在二维平面上的 个点。 座城市的标号为。第 座城市的坐标为 ,镇守这座城市的太守的能力值为 。 chnlich 每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第 小的城市(奇袭结束之后城市与太守依然存在)。不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被 chnlich 发现。
现在,chnlich 想要知道,每次奇袭时他的敌人的能力值。
输入格式
输入的第一行包含两个整数 , 表示城市与太守的个数, 表示接下来发生了 个事件。
输入的第二行到第 行,每行包含三个整数,第 行的三个整数依次表示编号为i的城市的 ,含义如题所述。
输入的第 行到第 行,每行有两种可能形式:
-第一种
QUERY x0 y0 x1 y1 k
表示 chnlich 询问一个相对顶点为 的矩形中,第 小能力值太守的能力值。
- 第二种
SWAP x y
表示 chnlich 的敌人交换了编号为 和 两座城市的太守。
输出格式
对于每一个 QUERY
,输出一行。若不存在第 小能力值的太守,输出 It doesn't exist.
。否则输出一个整数,表示矩形内能力值第 小太守的能力值。
样例输入
3 5
1 1 1
2 2 2
3 3 3
QUERY 1 1 3 3 3
SWAP 0 1
QUERY 2 2 4 4 1
SWAP 2 2
QUERY 2 2 3 3 3
样例输出
3
1
It doesn't exist.
数据规模与约定
对于 的数据,。
对于 的数据,。
另有 的数据,不存在 SWAP
操作。
另有 的数据,QUERY
操作次数 。
另有 的数据,所有城市的 坐标都相等,且询问中矩形的 坐标与所有城市的 坐标均相等;
对于 的数据,$N\le 6\times 10^4,M\le 10^4,0\le X_i,Y_i,Z_i\le 10^9,k\le 10^9$,保证所有操作均合法。