标签 线段树 下的文章

「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$ 通过如下方式生成：

1. $l_i \leftarrow ((l_i + \text{lastans})\bmod n) + 1$。
2. $r_i \leftarrow ((r_i + \text{lastans})\bmod n) + 1$。
3. 如果 $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$。