bzoj#P2674. Attack

Attack

题目描述

chnlich 非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。

他的敌人有 NN 座城市和 NN 个太守,N个城市可以看作在二维平面上的 NN 个点。NN 座城市的标号为0,1,2,,N10,1,2,\dots,N-1。第 ii 座城市的坐标为 (Xi,Yi)(X_i,Y_i),镇守这座城市的太守的能力值为 ZiZ_i。 chnlich 每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第 KK 小的城市(奇袭结束之后城市与太守依然存在)。不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被 chnlich 发现。

现在,chnlich 想要知道,每次奇袭时他的敌人的能力值。

输入格式

输入的第一行包含两个整数 N,MN,MNN 表示城市与太守的个数,MM 表示接下来发生了 MM 个事件。

输入的第二行到第 N+1N+1 行,每行包含三个整数,第 i+2i+2 行的三个整数依次表示编号为i的城市的 Xi,Yi,ZiX_i,Y_i,Z_i,含义如题所述。

输入的第 N+2N+2 行到第 N+M+1N+M+1 行,每行有两种可能形式:

-第一种 QUERY x0 y0 x1 y1 k 表示 chnlich 询问一个相对顶点为 (x0,y0),(x1,y1)(x_0,y_0),(x_1,y_1) 的矩形中,第 kk 小能力值太守的能力值。

  • 第二种 SWAP x y 表示 chnlich 的敌人交换了编号为 xxyy 两座城市的太守。

输出格式

对于每一个 QUERY,输出一行。若不存在第 kk 小能力值的太守,输出 It doesn't exist.。否则输出一个整数,表示矩形内能力值第 kk 小太守的能力值。

样例输入

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.

数据规模与约定

对于 30%30\% 的数据,N,M103N,M\le 10^3

对于 40%40\% 的数据,N3×104N\le 3\times 10^4

另有 10%10\% 的数据,不存在 SWAP 操作。

另有 10%10\% 的数据,QUERY 操作次数 2\le 2

另有 10%10\% 的数据,所有城市的 YY坐标都相等,且询问中矩形的 YY 坐标与所有城市的 YY 坐标均相等;

对于 100%100\% 的数据,$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$,保证所有操作均合法。