The kth maximum number

内存限制：512 MiB 时间限制：50 Sec

神犇Aleph在陪蒟蒻Bob玩一个游戏。神犇Aleph随手在地面上画了一个巨大无比的二维平面，然后在其上做一些微

小的贡献或教蒟蒻Bob做人。由于神犇Aleph是队爷，所以有时他会施用"队爷光环"这一魔法，在二维平面上的某坐

标整点处添加一个权值为v的贡献；又由于神犇Aleph是神犇，所以有时他会施用"嘲讽"这一技能，询问蒟蒻Bob在

矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2，包括边界)中，神犇Aleph所做的第k大的贡献是多少。由于神犇Al

eph是Au爷，所以他不会在同一个坐标整点处做两次或两次以上的贡献。现在神犇Aleph希望蒟蒻Bob回答他的每次

询问。然而蒟蒻Bob傻傻不会做，于是来求助您，宇宙第一神犇，请您来回答神犇Aleph的每次询问。

输入的第一行为两个正整数N, Q，表示横纵坐标的范围和神犇Aleph的操作次数（包括贡献次数和询问次数）。

接下来Q行，每行代表神犇Aleph的一个操作，操作格式如下：

首先第一个数字type，表示操作种类。type=1表示贡献，type=2表示询问。

若type=1，接下来会有三个正整数x, y, v，表示在坐标整点(x, y)添加一个贡献v。(1≤x, y≤N, 1≤v≤10^9)

若type=2，接下来会有五个正整数x1, y1, x2, y2, k，表示询问矩形区域(x1, y1), (x2, y2)中第k大的贡献。

(1≤x1≤x2≤N，1≤y1≤y2≤N，1≤k≤Q)

初始时平面上不存在贡献。

本题共有7组测试数据。对于所有的数据，N≤500,000。

Q的范围见下表：

测试点1-2 Q=1,000

测试点3-7 Q=50,000

对于每个询问(type=2的操作)，回答第k大的贡献。若不存在第k大的贡献，请输出"NAIVE!ORZzyz."（输出不含双引号）。


			

10 7

1 1 1 1

1 2 2 3

1 4 1 2

1 3 4 4

2 1 1 4 1 3

2 2 2 3 5 4

2 2 1 4 4 2


			NAIVE!ORZzyz.

NAIVE!ORZzyz.

3

BZPRO Powered by Remmina.
Github Repository

#4604. The kth maximum number