陈太阳与序列

题目描述

给你一个序列 $a_1,a_2,…,a_n$,我们称一个区间 $[l,r]$ 为太阳区间当且仅当 $a_l,a_{l+1},…,a_r$ 这些数字最大值不超过最小值的 $k$ 倍。

现在给你一个序列,问有多少个太阳区间。

思路

考虑一个区间 $[l,r]$。随着右端点 $r$,的移动,合法的左端点 $l$ 一定单调变化。于是可以用两个单调队列维护其中的最大值 / 最小值。数据的生成方法随机,期望空间复杂度 $O(\log n)$。

代码

陈太阳与直径

题目描述

所有 $n$ 个节点有标号的无根树中,直径为 $0,1,…,n−1$ 的树有多少个。

由于答案很大,对 $mod$ 取模。

思路

陈太阳与酒店

题目描述

陈太阳在一条马路的边上开了很多家酒店。马路左边与右边分别有 $n$ 家和 $m$ 家酒店,左边的 $n$ 家酒店的舒适程度为 $a_1,a_2,…,a_n$,右边的 $m$ 家酒店的舒适程度为 $b_1,b_2,…,b_m$。

对于马路左边的第 $i$ 家会和右边的第 $l_i$ 到第 $r_i$ 家酒店连双向双向边。陈太阳会给每个酒店定一个单价,单价要求为 $1$ 到 $K$ 之间的整数。对于一个酒店,如果所有与它连边的酒店的单价都比他小,那么就不会有人入住这家酒店。

陈太阳想给这些酒店定价,使得所有有人入住有人入住酒店的舒适程度的平均值最大。

输入

第一行三个正整数 $n,m,K$,表示马路左右两边分别有 $n$ 和 $m$ 家酒店。

第二行 $n$ 个整数 $a_1,a_2,…,a_n$ 表示左边的 $n$ 家酒店的舒适程度。

第三行 $m$ 个整数 $b_1,b_2,…,b_m$表示右边的 $m$ 家酒店的舒适程度。

接下来 $n$ 行,每行两个整数 $1≤l_i≤r_i≤m$。

数据保证每个点都至少存在一个点与它相连。

思路

代码