标签 主席树 下的文章
- 首页
- 主席树
「CodeChef GERALD07」Chef and Graph Queries
题目链接：CodeChef GERALD07
大厨有一个无向图 $G$。顶点从 $1$ 到 $n$ 标号，边从 $1$ 到 $m$ 标号。
大厨有 $q$ 对询问 $L_i, R_i$。对于每对询问，大厨想知道当仅保留编号 $X$ 满足 $L_i \le X \le R_i$ 所在的边时，图 $G$ 中有多少了连通块。
注意数据可能包含自环和重边！
本题有 $T$ 组数据。
数据范围：$1 \le T \le 10 ^ 3$，$1\le n, m, q \le 2\times 10 ^ 5$，$1\le L_i \le R_i \le M$，所有的 $n, m, q$ 的和均不超过 $2\times 10 ^ 5$。
「POI 2014」Couriers
题目链接：LOJ 2432
给定长度为 $n$ 的正整数序列 $p_i$。有 $m$ 组查询，每次查询区间 $[a,b]$ 中出现次数严格大于一半的数。
数据范围：$1\le n,m\le 5\times 10^5$，$1\le p_i\le n$。
「SPOJ 10628」COT - Count on a Tree
题目链接：SPOJ 10628
你有一棵 $n$ 个节点的树，节点从 $1$ 到 $n$ 编号。每个点都有一个权值 $a_i$。现在有 $m$ 个询问，每个询问形如：
u v k：求节点 $u,v$ 之间的路径上的第 $k$ 小权值。
数据范围：$1\le n,m\le 10^5$。
「Codeforces 813E」Army Creation
题目链接：Codeforces 813E
Vova 非常喜欢玩电脑游戏，现在他正在玩一款叫做 Rage of Empires 的策略游戏。
在这个游戏里，Vova 可以雇佣 $n$ 个不同的战士，第 $i$ 个战士的类型为 $a_i$。Vova 想要雇佣其中一些战士，从而建立一支平衡的军队。如果对于任何一种类型，军队中这种类型的战士都不超过 $k$，那么这支军队就被称为平衡的。当然 Vova 想让这支军队的人数尽量多。
现在 Vova 有 $q$ 个计划，第 $i$ 个计划他只能雇佣区间 $[l_i,r_i]$ 之间的战士。对于每个计划，你需要求出可以组建的平衡军队的最多人数。
本题强制在线，对于给定的 $l_i,r_i$，我们设上一个计划的答案为 $\text{lastans}$（初始值为 $0$），实际的 $l_i,r_i$ 通过如下方式生成：
- $l_i \leftarrow ((l_i + \text{lastans})\bmod n) + 1$。
- $r_i \leftarrow ((r_i + \text{lastans})\bmod n) + 1$。
- 如果 $l_r>r_i$，交换 $l_i$ 和 $r_i$。
数据范围：$1\le n,k,q,a_i\le 10^5$。
「Luogu 2617」Dynamic Rankings
题目链接：Luogu 2617
给定一个含有 $n$ 个数的序列 $a_i$，接下来有 $m$ 个询问，询问分为以下 $2$ 种：
Q i j k：询问区间 $[i,j]$ 排序后的第 $k$ 个数。C i t：将 $a_i$ 修改为 $t$。
数据范围：$1\le n, m \le 10 ^ 5$，$0 \le a_i \le 10^9$。