标签: 线段树

14 篇文章

义乌中学暑假集训 2021.07.15 B
白云建立了 $n$ 个商店,白兔打算按照编号 $1\sim n$ 的顺序访问这些商店。商店 $i$ 有一个价格 $ai$ 表示交易商品所需的代价。 白兔在按顺序走时,每到达一个商店,可以花费代价购买一件商品,并放入自己手中。也可以出售手上的商品,并获得利润。 白兔的力量有限,同一时刻只能携带一个商品。问它遍历完所有商店后能够获得的利润最大是多少? …
义乌中学暑假集训 2021.07.13 D
给定 $n$ 个数的序列 ${a_i}$,有 $m$ 组询问,每次询问给定区间 $[l,r]$,问有多少个子区间 $[i,j]$ 满足 $a_i,\dots,a_j$ 中不同的整数的数目是奇数。 $n,m\leq 5\times 10^5,1\leq a_i\leq n$。 Sol 首先肯定是考虑将询问离线。 然后考虑如何维护这个答案。 不难发现,…
CF GYM102759 I. Query On A Tree 17
Description 题目链接:GYM102759 I 给定一棵以 $1$​ 为根节点的拥有 $N$​ 个节点的带点权树,初始时每个点的点权均为 $0$​,有 $Q$​ 次操作,每次操作有两种类型: 1 u,以 $u$ 为根节点的子树内每个点点权均加 $1$。2 u v,将节点 $u$ 到节点 $v$ 的简单路径上的点的点权均加 $1$。 每次操…
CF679E Bear and Bad Powers of 42
Description 题目链接:CF679E 定义一个正整数是坏的,当且仅当它是 $42$ 的次幂,否则它是好的。 给定一个长度为 $n$ 的序列 $a_i$,保证初始时所有数都是好的。 有 $q$ 次操作,每次操作有三种可能: 1 i 查询 $a_i$。2 l r x 将 $a_{l\dots r}$ 赋值为一个好的数 $x$。3 l r x …
CF453E Little Pony and Lord Tirek
Description 你有 $n$ 只小马(编号从 $1$ 到 $n$)。每只小马有三种属性。 $s_i$:时间为 $0$ 时这只小马拥有的法力值。 $m_i$:这只小马可以拥有的最大法力值。 $r_i$:这只小马单位时间内回复的法力值。 提雷克会给出 $m$​ 条指令,每一条都可以被描述为 $3$ 个整数:$t_i, l_i, r_i$。表示在…
AT1984 [AGC001F] Wide Swap
Description 题目链接:AT1984[AGC001F] 给出一个元素集合为 ${1,2,\dots,N}$( $1\leq N\leq 500,000$)的排列 $P$,当有 $i,j (1\leq i<j\leq N)$满足$j-i\geq K (1\leq K\leq N-1)$ 且 $|P_{i}-P_{j}|==1∣$ 时,…
P3792 由乃与大母神原型和偶像崇拜
Description 题目链接:P3792 给定一个长度为 $n$ 的序列 ${a_i}$,有 $m$ 个操作: 单点修改查询区间 $[l,r]$ 是否可以重排成值域上连续的一段。 $n,m\leq 5\times 10^5,a_i< 2.5\times 10^7$ Solution 可以考虑记录某个点之前第一个权值相同的数的位置 $p_i…
CF803G Periodic RMQ Problem
Description 题目链接:CF803G 一个序列 ${a_i}$ 由 $k$ 个长度为 $n$ 的序列 ${b_i}$ 拼接而成,支持 $q$ 个操作: 1 l r x,区间赋值2 l r求区间最小值 $1\leq n\leq 10^5,1\leq k \leq 10^4,1\leq q \leq 10^5,1\leq b_i\leq 10…
CF1045G AI robots
Description 题目链接:Luogu CF1045G 给定 $N$ 个点,每个点的位置为 $X_i$,覆盖半径为 $R_i$,能覆盖 $[X_i-R_i,X_i+R_i]$,权值为 $Q_i$,询问能互相覆盖到并且权值之差不大于 $K$ 的点对的数量。 $1\leq N\leq 10^5,1\leq K\leq 20,1\leq X_i,R…
bzoj 4491. 我也不知道题目名字是什么 题解
Preface 题目链接 Description 给定一个序列A[i],每次询问l,r,求[l,r]内最长子串,使得该子串为不上升子串或不下降子串 N,Q<=50000 Solution 设 $L[i]$ 表示以 $i$ 为起点,往左最多能成为子串的长度,$R[i]$ 表示以 $i$ 为起点,往右最多能成为子串的长度。 那么很显然区间 $[l…
Luogu P4088 [USACO18FEB]Slingshot P 题解
Preface 题目链接 rua!调了半天发现原来是 $id$ 的问题。。。 Description 有一个数轴,上面有 $n$ 个传送门,使用第 $i$ 个传送门,你可以从 $x_i$​ 走到 $y_i$​,花费的时间为 $t_i$ 秒。你的速度为 $1$ 格/秒,有 $m$ 次询问,每次你要从 $a_i$​ 走到 $b_i$​,最多使用一次传送…
loj 6062 「2017 山东一轮集训 Day2」Pair 题解
Description 题目链接 给出一个长度为 $n$ 的数列 $\{a_i\}$ 和一个长度为 $m$ 的数列 $\{b_i\}$,求 $\{a_i\}$ 有多少个长度为 $m$ 的连续子数列能与 $\{b_i\}$ 匹配。 两个数列可以匹配,当且仅当存在一种方案,使两个数列中的数可以两两配对,两个数可以配对当且仅当它们的和不小于 $h$。 对…