【模板】可持久化线段树 1(主席树)(洛谷P3834)

题目背景

这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强,请使用主席树。同时请注意常数优化

题目描述

如题,给定N个正整数构成的序列,将对于指定的闭区间查询其区间内的第K小值。

输入输出格式

输入格式:

第一行包含两个正整数N、M,分别表示序列的长度和查询的个数[……]

继续阅读

送花(洛谷P2073)

题目背景

小明准备给小红送一束花,以表达他对小红的爱意。他在花店看中了一些花,准备用它们包成花束。

题目描述

这些花都很漂亮,每朵花有一个美丽值W,价格为C。

小明一开始有一个空的花束,他不断地向里面添加花。他有以下几种操作:

操作 含义

1 W C 添加一朵美丽值为W,价格[……]

继续阅读

迎接仪式 洛古p1136

题目描述

LHX教主要来X市指导OI学习工作了。为了迎接教主,在一条道路旁,一群Orz教主er穿着文化衫站在道路两旁迎接教主,每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字,但是领队突然发现,另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。

为了简[……]

继续阅读

教主的花园 洛古p1133

题目描述

教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值。

教主最喜欢3种树,这3种树的高度分别为10,20,30。教主希望这一圈树种得有层次感,所以任何一个位置的树要比它相[……]

继续阅读

红牌 洛古p1130

题目描述

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ,一共包括N个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程,每一步政府都派了M个工作人员来检查材料。不幸的是,并不是每一个工作人员效率都很高。尽管如此,为了体现“公开政府[……]

继续阅读

毁灭

题目描述

YJC决定对入侵C国的W国军队发动毁灭性打击。将C国看成一个平面直角坐标系,W国一共有n^2个人进入了C国境内,在每一个(x,y)(1≤x,y≤n)上都有恰好一个W国人。YJC决定使用m颗核导弹,每一颗核导弹将杀死某个圆内所有的W国人,恰好在圆上也会被杀死。现在YJC想知道,在这一轮核打[……]

继续阅读

轰炸

题目描述

C国和W国爆发了战争!YJC决定对W国的n个城市进行轰炸。每个城市都有一个重要度ai。设xi=‘重要度大于ai的城市数+1’,那么编号为i城市就是第xi个被轰炸的城市。显然这样能保证重要度大的城市先被轰炸,重要度相同的城市同时被轰炸。现在YJC想知道,对于每一个i,xi等于多少?[……]

继续阅读