BZOJ-3110-K大数查询-ZJOI2013-暴力

发布时间：2020-12-14 02:42:11 所属栏目：大数据来源：网络整理

导读：描述有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。分析暴力的做法,正解是? 树套树或者zkw线段树我现在只想说是

描述

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

分析

暴力的做法,正解是?~~树套树或者zkw线段树~~ 我现在只想说是整体二分...
读入所有的命令,把所有的插入命令收集起来处理,按照插入的数值的大小从大到小 (相等时按先后顺序) 排序.
按照先后顺序遍历命令. 如果是插入命令,标记该插入已经生效; 否则如果是查询命令,从前到后遍历插入命令,如果当前的插入命令已经生效,则更改查询的排名,具体怎么更改就是减去重合区间长度
如果更改后排名小于等于0,第C大就是当前的插入操作所插入的值.
既然暴力可以,就不用写二维线段树了. 比赛时善于利用STL来暴力是个很好的办法.
但是暴力也有技巧

代码

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!