标签 线段树 下的文章
- 首页
- 线段树
「2019 Multi-University Training Contest 2」Longest Subarray
题目链接:HDU 6602
你有一个长度为 $n$ 的序列 $a$ 和两个整数 $C, K$ 满足序列中的所有元素 $1 \le a_{i} \le C$。
我们定义一个连续子序列 $a_{l}, a_{l + 1}, \dots, a_{r}$ 是「好的」当且仅当:
$$ \forall x \in [1, C], \sum_{i = l} ^ {r} [a_{i} = x] = 0\ \text{或}\ \sum_{i = l} ^ {r} [a_{i} = x] \ge K $$
抽象地,如果一个数字在子序列中出现过,那么它的出现次数必须不少于 $K$ 次。
他需要求出「好的」连续子序列的最长长度。
本题有多组数据。
数据范围:$1 \le n, C, K \le 10 ^ 5$,$1 \le a_{i} \le C$,$1 \le \sum n, \sum C, \sum K \le 5 \times 10 ^ 5$。
「NOI 2018」你的名字
题目链接:UOJ 395
小 A 被选为了 ION2018 的出题人,他精心准备了一道质量十分高的题目,且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届,所以在题目命名上也是有规定的,ION 命题手册规定:每年由命题委员会规定一个小写字母字符串,我们称之为那一年的命名串,要求每道题的名字必须是那一年的命名串的一个非空连续子串,且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因,小 A 不知道 ION2017 每道题的名字,但是他通过一些特殊手段得到了 ION2017 的命名串,现在小 A 有 $Q$ 次询问:每次给定 ION2017 的命名串 $S$ 和 ION2018 的命名串 $T$,求有几种题目的命名,使得这个名字一定满足命题委员会的规定,即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因,所有询问给出的 ION2017 的命名串都是某个串的连续子串 $S[l \dots r]$。
数据范围:$1 \le \lvert S \rvert \le 5 \times 10 ^ 5$,$1 \le Q \le 10 ^ 5$,$\sum \lvert T \rvert \le 10 ^ 6$,$1 \le l \le r \le \lvert S \rvert$。
「Codeforces 700E」Cool Slogans
题目链接:Codeforces 700E
Bomboslav 成立了一个品牌代理商,正在帮助公司创建商标和广告。就这个问题而言,公司的广告应该是其名称的非空子串。
有时,公司会对品牌进行重塑并改变广告。如果广告 $B$ 作为子串在广告 $A$ 中出现至少 $2$ 次(允许重叠),那么认为广告 $A$ 比 $B$ 更酷。
你得到了某个公司的名字 $w$,你的任务是帮助 Bomboslav 确定最长的广告序列 $s_1, s_2, \dots, s_k$ 满足任何一个广告都比上一个更酷。
数据范围:$1 \le \lvert w \rvert \le 2 \times 10 ^ 5$。
「Codeforces 1073G」Yet Another LCP Problem
题目链接:Codeforces 1073G
定义 $\text{LCP}(s, t)$ 字符串 $s$ 和 $t$ 的最长公共前缀,再定义 $s[x\dots y]$ 为字符串 $s$ 从位置 $x$ 到 $y$ 的子串。
给定一个长度为 $n$ 的字符串 $s$ 和 $q$ 个询问。每次询问给出两个长度分别为 $k_i, l_i$ 的序列 $a, b$。你需要计算 $\sum_{i = 1} ^ k \sum_{j = 1} ^ l \text{LCP}(s[a_i \dots n], s[b_j \dots n])$ 的值。
数据范围:$1 \le n, q, \sum k_i, \sum l_i \le 2 \times 10 ^ 5$,$1 \le k_i, l_i \le n$。
「ZJOI 2019」线段树
题目链接:LOJ 3043
九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就是线段树。
线段树的核心是懒标记,下面是一个带懒标记的线段树的伪代码,其中 tag
数组为懒标记:
其中函数 $\text{Lson}(\text{Node})$ 表示 $\text{Node}$ 的左儿子,$\text{Rson}(\text{Node})$ 表示 $\text{Node}$ 的右儿子。
现在可怜手上有一棵 $[1, n]$ 上的线段树,编号为 $1$。这棵线段树上的所有节点的 tag
均为 $0$。接下来可怜进行了 $m$ 次操作,操作有两种:
- $1\ l\ r$,假设可怜当前手上有 $t$ 棵线段树,可怜会把每棵线段树复制两份(
tag
数组也一起复制),原先编号为 $i$ 的线段树复制得到的两棵编号为 $2i − 1$ 与 $2i$,在复制结束后,可怜手上一共有 $2t$ 棵线段树。接着,可怜会对所有编号为奇数的线段树进行一次 $\text{Modify}(\text{root}, 1, n, l, r)$。 - $2$,可怜定义一棵线段树的权值为它上面有多少个节点
tag
为 $1$。可怜想要知道她手上所有线段树的权值和是多少。
数据范围:$1 \le n, m \le 10 ^ 5$。
「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$。
「Codeforces 280D」K-Maximum Subsequence Sum
题目链接:Codeforces 280D
你有一个长度为 $n$ 的序列 $a_i$,接下来进行 $m$ 次操作,操作分为如下 $2$ 种:
0 i val
:将第 $i$ 个数 $a_i$ 修改为 $val$。1 l r k
:你需要在序列 $a_l, a_{l + 1}, \cdots, a_r$ 中找出至多 $k$ 个不相交的子序列,使得他们的和最大。形式化地,你需要找出至多 $k$ 对 $(x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)$(其中 $l\le x_1\le y_1<x_2\le y_2<\cdots<x_t \le y_t\le r$,$0\le t\le k$),使得 $(a_{x_1} + a_{x_1 + 1} + \cdots + a_{y_1}) + (a_{x_2} + a_{x_ 2 + 1} + \cdots + a_{y_2})+\cdots + (a_{x_t} + a_{x_t + 1} + \cdots + a_{y_t})$ 的值最大。
特别地,你可以选择 $0$ 个子序列,这时和式等于 $0$。
数据范围:$1 \le n, m\le 10 ^ 5$,$\vert a_i, val \vert \le 500$,$1\le k\le 20$,求 $k$ 个子序列和的操作不超过 $10^4$ 个。
「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$。