标签: 主席树

「AtCoder 133F」Colorful Tree

There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex ai and Vertex bi, and the color and length of that edge are ci and di, respectively. Here the color of each edge is represented by an integer between 1 and N−1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

  • Query j (1≤j≤Q): assuming that the length of every edge whose color is xj is changed to yj, find the distance between Vertex uj and Vertex vj. (The changes of the lengths of edges do not affect the subsequent queries.)

「CQOI 2015」 任务查询系统

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

「HDU 6621」 K-th Closest Distance

You have an array: a1, a2, ......, an and you must answer for some queries.
For each query, you are given an interval [L, R] and two numbers p and K. Your goal is to find the Kth closest distance between p and aL, aL+1, ..., aR.
The distance between p and ai is equal to |p - ai|.
For example:

「16届同大邀请赛」美味佳肴

众所周知,天才程序员菜哭武是一个伟大的厨师。这天,张老师和石头来到菜哭武家做客,想尝一尝菜哭武的手艺。
菜哭武手上有n种食材,每种食材个数无限多,编号为i的食材有一个美味度ai。一道菜中,每种编号的食材至多有一个,
而这道菜的美味度是这道菜包含的食材的美味度之和。

「SCOI2015」情报传递

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务: