「FJOI2015」火星商店问题-线段树分治+可持久化Trie

有 $n$ 个商店,每个商店都有一个特殊商品,每个人在任何时间都可以买。第一天可能没有进货,有若干次询问,而之后的每天,都有一次进货和若干次询问,每次进货都是某个商店进了某个编号的货,每次询问都是询问在编号为 $l$ 到 $r$ 的商店中,在 $d$ 天内进的货的编号异或 $x$ 的最大值。

可持久化线段树学习笔记

可持久化线段树,是一种可以进行可持久化操作的线段树,具有优越的时间复杂度。

「SDOI2013」森林-主席树+LCA+启发式合并

小Z有一片森林,含有$N$个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有$M$条边。

小Z希望执行$T$个操作,操作有两类:

  • Q x y k查询点$x$到点$y$路径上所有的权值中,第$k$小的权值是多少。此操作保证点$x$和点$y$连通,同时这两个节点的路径上至少有$k$个点。

  • L x y在点$x$和点$y$之间连接一条边。保证完成此操作后,仍然是一片森林。

强制在线。

对于所有的数据$n,m,T \leq 8 \times 10^4$。

「CQOI2015」任务查询系统-可持久化线段树

超级计算机中的任务用三元组 $(S_i,E_i,P_i)$ 描述, $(S_i,E_i,P_i)$ 表示任务运行区间为 $[S_i,E_i]$ ,其优先级为 $P_i$ 。

给出 $n$ 个任务。随后给出 $m$ 个询问,第 $X_i$ 秒正在运行的任务中,优先级最小的 $K_i$ 个任务的优先级之和是多少。特别的,如果 $K_i$ 大于第 $X_i$ 秒正在运行的任务总数,则直接回答第 $X_i$ 秒正在运行的任务优先级之和。

强制在线。

「Luogu2617」Dynamic Rankings-树状数组-可持久化线段树

给定一个含有 $n$ 个数的序列 $\{a_n\}$ ,回答询问或执行操作:

  • Q i j k ($1\leq i\leq j\leq n, 1\leq k\leq j-i+1$)表示询问$a[i],a[i+1]……a[j]$中第 $k$ 小的数。

  • C i t ($1 \leq i \leq n,0\leq t \leq 10^{9}$)表示把 $a[i]$ 改变成为 $t$ 。

「POI2014」KUR-Couriers-主席树

给一个数列 $\{a_n\}$ ,每次询问区间 $[l,r]$ 内有没有一个数出现次数超过一半。如果有,输出这个数,如果没有,输出 $0$ 。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×