| 题目名称 | 1776. [国家集训队2012]Attack |
|---|---|
| 输入输出 | nt2012_attack.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 10000 ms (10 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：29， 通过率：20.69% | ||||
 天一阁 |
100 | 21.055 s | 256.77 MiB | C++ |
 FoolMike |
100 | 21.142 s | 355.25 MiB | C++ |
 cstdio |
100 | 24.439 s | 112.66 MiB | C++ |
 炎帝 |
100 | 31.961 s | 256.77 MiB | C++ |
|
天一阁 |
100 | 34.731 s | 102.60 MiB | C++ |
 pb0207 |
100 | 53.852 s | 276.51 MiB | C++ |
|
pb0207 |
80 | 103.080 s | 276.51 MiB | C++ |
|
pb0207 |
75 | 117.295 s | 262.68 MiB | C++ |
 thomount |
55 | 101.754 s | 1.21 MiB | C++ |
|
pb0207 |
55 | 120.291 s | 276.51 MiB | C++ |
| 关于 Attack 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
为什么树狀数组比线段树常数小这么多啊
pb0207
2017-11-30 20:18
6楼
| ||||
|
整体二分大法好！各种打错变量名我也是醉了……
| ||||
|
为什么块的大小取sqrt(n) 比 sqrt(n*log2(n)) 快，这不科学，求大神解释
| ||||
|
哈哈哈哈哈哈，时隔多年，终于过了！！！！
| ||||
|
回复 @cstdio :
QAQQAQ主席树Orzzzzzzzzzzzzzzzzzzzz  Asm.Def
2014-10-28 23:15
2楼
| ||||
|
果然划分树被主席树各种吊打……像我这种常数巨大的人都能最慢数据2.904s过……
一开始非常傻叉的写了个每块重新建树Orz…… | ||||
1776. [国家集训队2012]Attack
★★★★ 输入文件：nt2012_attack.in
输出文件：nt2012_attack.out
简单对比时间限制：10 s 内存限制：512 MiB
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座城市和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两座城市的太守。
输入的第二行到第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小太守的能力值。
若不存在第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
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.
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，保证所有操作均合法。
对于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，保证所有操作均合法。