「FJOI2015」火星商店问题-线段树分治+可持久化Trie

有 $n$ 个商店,每个商店都有一个特殊商品,每个人在任何时间都可以买。第一天可能没有进货,有若干次询问,而之后的每天,都有一次进货和若干次询问,每次进货都是某个商店进了某个编号的货,每次询问都是询问在编号为 $l$ 到 $r$ 的商店中,在 $d$ 天内进的货的编号异或 $x$ 的最大值。

「SDOI2017」树点涂色-LCT+树链剖分

Bob 有一棵 $n​$ 个点的有根树,其中 $1​$ 号点是根节点。Bob 在每个节点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是,这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob 可能会进行这几种操作:

  • 1 x,把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色;
  • 2 x y,求 $x$ 到 $y$ 的路径的权值;
  • 3 x,在以 $x$ 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob 一共会进行 $m$ 次操作。

「CF540E」Infinite Inversions-动态开点线段树

现在有一个由所有正整数组成的无限递增序列: $p = {1,2,3,…}$ 。

对这个序列执行 $n$ 次交换操作。每次一个操作,给出两个整数 $a,b$,交换位置 $a$ 和 $b$ 处的元素。

你的任务是在所有操作结束后,输出最终序列的逆序对个数,即满足 $i < j$ 且 $p_i > p_j$ 的有序数对 $(i,j)$ 的数量。

「CF369E」Valera and Queries-线段树

有 $n$ 条线段,分别为 $[l_i,r_i]$ 。

有 $m$ 个询问,分别为 $cnt_i,p_1,p_2,…,p_{cnt_i}$

对于每个询问,输出有多少线段至少覆盖这 $cnt_i$ ​个点中的一个。($\sum cnt_i \le 3 \cdot 10^5$)

「CF256E」Lucky Arrays-简单线段树

给定一个长度为 $n(1 \le n \le 77777)$ 的数列 $a$ ,初始的时候全为 0。

给出一个 $3 \times 3$ 的矩阵 $w_{i,j}$ ,$w_{i,j} = 1$ 时代表 $(i,j)$ 这个有序数对为和谐的数对,否则 $(i,j)$ 不为一个和谐数对。

一个数列 $a$ 是和谐的当且仅当对于所有的 $1\le i \le n-1$ , $(a_i,a_{i+1})$ 均为和谐数对。

有 $m(1\le m \le 77777)$ 次修改和询问,每次给出两个整数 $v_i,t_i$,将 $a_{v_i} (1 \le v_i \le n)$ 修改为 $t_i(0\le t_i \le 3)$。

每次修改后都询问,如果将数列里所有的 $0$ 都替换为任意 $1$ 到 $3$ 之间的整数(不同位置的 $0$ 可以替换为不同的数),那么最后产生的和谐的数列有多少种。每次修改后的查询并不会使数列发生任何改变。

答案对 $777777777$ 取模。

「CF160E」Buses and People-线段树

Bertown 大街可以抽象为一条数轴。在数轴上有 $10^9$ 个巴士站。站点按照它们在数轴上的顺序从 $1$ 到 $10^9$ 的整数编号。这个城市有 $n$ 辆公共汽车。每天第 $i$ 个公共汽车从 $s_i$ 位置出发,到 $f_i$ 位置停止( $s_i < f_i$ ),它在所有位于 $s_i$ 与 $f_i$ 的中间站点停靠并且仅在晚上返回。公共汽车在时间 $t_i$ 开始行驶,并且它也在时间 $t_i$ 完成行驶(行驶、停靠都是瞬间的)。所有公共汽车的开始时间 $t_i$ 都不同。公交车有无限的容量。

Bertown 有很多居民。今天第 $i$ 个人要从 $l_i$ 位置出发到 $r_i$ 位置结束( $l_i < r_i$ );第 $i$ 个人在时间 $b_i$ 进入他的出发位置( $l_i$ )。一方面,每个人都希望尽快到达目的地,另一方面,他不想换乘公交车。

也就是:为第 $i$ 个人挑选的公交汽车 $j$ ,满足 $s_j≤l_i$, $r_i≤f_j$ 和 $b_i≤t_j$ 的条件下,$t_j$ 最小。

你的任务是确定每个人今天是否可以到达目的地,如果可以,找到每个人将乘坐的公交车的号码,不可以则输出 $-1$ 。

「CF115E」Linear Kingdom Races-dp+线段树优化

你是一个赛车比赛的组织者,想在线性王国中安排一些比赛。

线性王国有 $n$ 条连续的从左到右的道路。道路从左到右依次编号为从 $1$ 到 $n$ ,因此道路按照升序排列。在这些道路上可能会有几场比赛,每一场比赛都将使用这些道路的某个连续的子序列。而且,如果某场比赛举行了,你将获得一定数额的金钱。没有比赛在时间上重叠,所以每一段道路可以在多个比赛中使用。

不幸的是,所有道路的状况都不佳,需要修理。每条路都有与之相关的维修费用,你需要支付这笔费用来修理道路。只有在某场比赛中需要使用的所有道路都进行了修复,才能进行比赛。你的任务是修复道路并使你的利润最大化。你的利润被定义为你从比赛中获得的总金额减去你花在修理道路上的钱。请注意,您可以决定不修任何道路,并获得利润 $0$ 。

输出你能获得的最大利润。

「SCOI2016」美味-可持久化线段树

一家餐厅有 $n$ 道菜,编号 $1,\dots,n$ ,大家对第 $i$ 道菜的评价值为 $a_i(1 \leq i \leq n)$。有 $m$ 位顾客,第 $i$ 位顾客的期望值为 $b_i$,而他的偏好值为 $x_i$ 。因此,第 $i$ 位顾客认为第 $j$ 道菜的美味度为 $b_i \text{XOR} (a_j+x_i)$ ,$\text{XOR}$ 表示异或运算。

第 $i$ 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 $l_i$ 道到第 $r_i$ 道中选择。请你帮助他们找出最美味的菜。

「POI2015」Kinoman-线段树

共有 $m$ 部电影,编号为 $1$ 到 $m$,第 $i$ 部电影的好看值为 $w[i]$。在 $n$ 天之中(从 $1$ 到 $n$ 编号)每天会放映一部电影,第 $i$ 天放映的是第 $f[i]$ 部。你可以选择 $l,r(1 \leq l \leq r \leq n)$ ,并观看第 $l,l+1,\dots , r$ 天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

「HEOI2016/TJOI2016」树-线段树

在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为 $1$),有以下两种操作:

  1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)

  2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)

你能帮帮她吗?

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×