题目名称 1776. [国家集训队2012]Attack
输入输出 nt2012_attack.in/out
难度等级 ★★★★
时间限制 10000 ms (10 s)
内存限制 512 MB
测试数据 20 简单对比
题目来源 2014-10-27
开放分组 全部用户
提交状态
分类标签
主席树 划分树 可持久化 分块
通过:5, 提交:29, 通过率:17.24%
Gravatar天一阁 100 21.055 s C++
GravatarFoolMike 100 21.142 s C++
Gravatarcstdio 100 24.439 s C++
Gravatar炎帝 100 31.961 s C++
Gravatar天一阁 100 34.731 s C++
Gravatarpb0207 100 53.852 s C++
Gravatarpb0207 80 103.080 s C++
Gravatarpb0207 75 117.295 s C++
Gravatarthomount 55 101.754 s C++
Gravatarpb0207 55 120.291 s C++
关于 Attack 的讨论
果然划分树被主席树各种吊打……像我这种常数巨大的人都能最慢数据2.904s过……
一开始非常傻叉的写了个每块重新建树Orz……
Gravatarcstdio
2014-10-28 21:30 1楼
回复 @cstdio :
QAQQAQ主席树Orzzzzzzzzzzzzzzzzzzzz
GravatarAsm.Def
2014-10-28 23:15 2楼
哈哈哈哈哈哈,时隔多年,终于过了!!!!
Gravatar天一阁
2015-03-09 18:55 3楼
为什么块的大小取sqrt(n) 比 sqrt(n*log2(n)) 快,这不科学,求大神解释
Gravatar天一阁
2015-03-09 19:00 4楼
整体二分大法好!各种打错变量名我也是醉了……
GravatarFoolMike
2017-06-02 16:17 5楼
为什么树狀数组比线段树常数小这么多啊
Gravatarpb0207
2017-11-30 20:18 6楼

1776. [国家集训队2012]Attack

★★★★   输入文件:nt2012_attack.in   输出文件:nt2012_attack.out   简单对比
时间限制:10 s   内存限制:512 MB
Attack(李超)
时间限制:10.0s   内存限制:512.0MB

【试题来源】

2012集训队互测-李超

【问题描述】

chnlich非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。
他的敌人有N座城市和N个太守,N个城市可以看作在二维平面上的N个点。
N座城市的标号为0,1,2,……,N-1。
第i座城市的坐标为(Xi,Yi),镇守这座城市的太守的能力值为Zi。
chnlich每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。
不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被chnlich发现。
现在,chnlich想要知道,每次奇袭时他的敌人的能力值。

【输入格式】

输入的第一行包含两个整数N,M,N表示城市与太守的个数,M表示接下来发生了M个事件。
输入的第二行到第N+1行,每行包含三个整数,第i+2行的三个整数依次表示编号为i的城市的Xi,Yi,Zi,含义如题所述。
输入的第N+2行到第N+M+1行,每行有两种可能形式:
第一种
QUERY x0 y0 x1 y1 k
表示chnlich询问一个相对顶点为(x0,y0),(x1,y1)的矩形中,第k小能力值太守的能力值。
第二种
SWAP x y
表示chnlich的敌人交换了编号为x和y两座城市的太守。

【输出格式】

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

【样例输入】

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%的数据,N,M<=1000;
对于40%的数据,N<=30000;
另有10%的数据,不存在SWAP操作;
另有10%的数据,QUERY操作次数<=2;
另有10%的数据,所有城市的Y坐标都相等,且询问中矩形的Y坐标与所有城市的Y坐标均相等;
对于100%的数据,N<=60000,M<=10000,0<=Xi,Yi,Zi<=10^9,k<=10^9,保证所有操作均合法。