题目名称 1345. [ZJOI2013] K大数查询
输入输出 zjoi13_sequence.in/out
难度等级 ★★★☆
时间限制 3000 ms (3 s)
内存限制 512 MB
测试数据 10 简单对比
题目来源 2013-04-03
开放分组 全部用户
提交状态
分类标签
通过:148, 提交:608, 通过率:24.34%
GravatarGo灬Fire 100 0.412 s C++
GravatarKirin 100 0.455 s C++
Gravatarchaijing 100 0.478 s C++
Gravatarcstdio 100 0.494 s C++
GravatarLink 100 0.500 s C++
Gravatarnew ioer 100 0.503 s C++
GravatarKirin 100 0.504 s C++
Gravatarboom 100 0.517 s C++
Gravatar水中音 100 0.522 s C++
GravatarsssSSSay 100 0.525 s C++
关于 K大数查询 的讨论
这题打的真爽
GravatarC语言入门
2014-03-02 21:20 1楼
整体二分大法好!
整体二分中的统计可以用段修改段查询的树状数组/线段树(结束时要回滚操作,不能直接清空),也可以用CDQ分治
Gravatarcstdio
2014-10-20 10:42 2楼
居然这么慢QAQ
果然树状数组套线段树就是不行=。=
算了至少还是过了的
GravatarHouJikan
2015-02-27 17:30 3楼
动态开点线段树
Gravatar天一阁
2015-03-03 20:06 4楼
poi……
Gravatar水中音
2015-03-27 16:56 5楼
插入的数的个数可能爆int
GravatarNgshily
2016-03-16 14:03 6楼
数据范围有误?c是大于0的!
GravatarTenderRun
2016-06-25 12:04 7楼
评测机太慢太慢……本地1.3s评测死活过不了
GravatarTenderRun
2016-06-25 15:49 8楼
整体二分和CDQ是一个东西吗?
GravatarTenderRun
2016-06-26 16:41 9楼
电脑上1和l傻傻分不清。。。
Gravatar_Itachi
2016-07-23 15:33 10楼
整体二分大法吼啊!
GravatarMarvolo
2016-08-18 20:03 11楼
STL30行,谁来比短?
Gravatar_Itachi
2016-10-05 16:10 12楼
写一发整体二分被K大坑惨了。。
Gravatar_Itachi
2016-10-05 17:14 13楼
Gravatar哒哒哒哒哒!
2016-10-07 06:19 14楼
垂死病中惊坐起,膜拜神犇wmd
Gravatarsxysxy
2016-12-10 10:13 15楼
linux下gedit的第一份代码。。手残把sum[o]写成sum[0]。。
add标记不下传速度会快一点。
Gravatar再见
2017-01-02 12:19 16楼
GravatarL_in
2017-02-22 17:46 17楼
回复 @. :
论Consolas字体和语法高亮的重要性
Gravatarrvalue
2017-01-18 08:49 18楼
数据略水
GravatarCydiater
2017-01-23 09:38 19楼
整体二分(树状数组或线段树)
权值线段树套区间线段树
GravatarGo灬Fire
2017-04-07 21:13 20楼
整体二分跑的好快啊233
GravatarsssSSSay
2017-04-04 18:28 21楼
树套树+卡常过了。。。。。
我觉得我要去学一下整体二分。。
GravatarHeHe
2017-09-01 19:46 22楼
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
GravatarShirry
2018-04-16 08:02 23楼

1345. [ZJOI2013] K大数查询

★★★☆   输入文件:zjoi13_sequence.in   输出文件:zjoi13_sequence.out   简单对比
时间限制:3 s   内存限制:512 MB

【题目描述】

有N个位置,M个操作。操作有两种,每次操作如果是:

1 a b c:表示在第a个位置到第b个位置,每个位置加上一个数c

2 a b c:表示询问从第a个位置到第b个位置,第C大的数是多少。

【输入格式】

第一行N,M接下来M行,每行形如1 a b c或2 a b c

【输出格式】

输出每个询问的结果

【样例输入】

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

【样例输出】

1
2
1

【提示】

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=long long

【说明】

第一个操作后位置 1 的数只有 1 , 位置 2 的数也只有 1 。

第二个操作 后位置 1 的数有 1 、 2 ,位置 2 的数也有 1 、 2 。

第三次询问 位置 1 到位置 1 第 2 大的数是1 。

第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。