BZOJ3110 - [Zjoi2013]K大数查询

BZOJ3110 - Click Here

  

Description

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

  

Input

  第一行N,M

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

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

  a<=b<=N

  1操作中abs(c)<=N

  2操作中c<=Maxlongint

  

Output

  输出每个询问的结果

  

Solutions

  树套树。权值线段树套区间线段树。

  一开始,我想的是区间线段树套权值线段树,然后利用二分答案来求解。但是每次操作时间是$log_{}^{3}N$,很明显过不了。后来发现,可以将二分答案转换成二分查找(常用技巧QAQ)。

  改成权值线段树套区间线段树,然后每次询问就可以用二分查找解决。这样,询问的时间就可以降为$log_{}^{2}N$。

  P.S. 线段树的空间复杂度是4N!!!害我RE了一下午

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang