Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

06/2
19:37
暴力

[bzoj 4604] The kth maximum number

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

神犇Aleph在陪蒟蒻Bob玩一个游戏。神犇Aleph随手在地面上画了一个巨大无比的二维平面,然后在其上做一些微小的贡献或教蒟蒻Bob做人。由于神犇Aleph是队爷,所以有时他会施用"队爷光环"这一魔法,在二维平面上的某坐标整点处添加一个权值为v的贡献;又由于神犇Aleph是神犇,所以有时他会施用"嘲讽"这一技能,询问蒟蒻Bob在矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2,包括边界)中,神犇Aleph所做的第k大的贡献是多少。由于神犇Aleph是Au爷,所以他不会在同一个坐标整点处做两次或两次以上的贡献。现在神犇Aleph希望蒟蒻Bob回答他的每次询问。然而蒟蒻Bob傻傻不会做,于是来求助您,宇宙第一神犇,请您来回答神犇Aleph的每次询问。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入的第一行为两个正整数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-7Q=50,000

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

NAIVE!ORZzyz.
NAIVE!ORZzyz.
3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

直接nth_element暴力就好了(pascal选手一脸怨念

 

[bzoj 4604] The kth maximum number