题目集 1
题目集 1
题目一：区间内线段计数
题目信息
- 命题人：Aiyiyi
- 提出时间：2021 年 2 月 25 日
- 来源：原创
- 致谢：感谢 Kinesis 与 LightningUZ 在本题讨论中的贡献
题目描述
正整数坐标轴上初始有 \(k\) 条线段。每条线段用一对整数 \((L, R)\) 表示，其中 \(L < R\)。
你需要维护这些线段，并依次处理 \(m\) 次操作。操作有以下两种：
- \(\texttt{add}\ L\ R\)：加入线段 \((L, R)\)。
- \(\texttt{query}\ L\ R\)：询问当前已有线段中，有多少条被区间 \([L, R]\) 完全包含。
也就是说，线段 \((L', R')\) 会被一次查询 \((L, R)\) 计入答案，当且仅当
\[ L \le L' < R' \le R. \]
数据范围
\[ 1 \le m,\ k \le 10^{6}, \qquad 1 \le L < R \le 10^{9}. \]
题目二：欧拉函数最小公倍数求和
题目信息
- 命题人：Aiyiyi
- 提出时间：2021 年 2 月 25 日
- 来源：原创
- 致谢：感谢 Kinesis 与 LightningUZ 在本题讨论中的贡献
题目描述
给定正整数 \(n\)，求
\[ \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda(i, j), \]
其中
\[ \lambda(x, y) = \operatorname{lcm}\bigl(\varphi(x), \varphi(y)\bigr). \]
这里 \(\varphi\) 表示欧拉函数，\(\operatorname{lcm}\) 表示最小公倍数。
答案对 \(998244353\) 取模。
数据范围
\[ 1 \le n \le 10^{6}. \]
题目三：共链点集计数
题目信息
- 命题人：Aiyiyi
- 提出时间：2021 年 2 月 25 日
- 来源：Aiyiyi 独立发现
- 致谢：感谢 Yoluko 在本题讨论中的贡献
- 相关链接：Library Checker：Frequency Table of Tree Distance
题目描述
给定一棵 \(n\) 个结点的树。
对于每个整数 \(K\)，其中 \(1 \le K \le n\)，求有多少种方式可以选出恰好 \(K\) 个结点，使得这些结点全部位于树上的同一条简单路径上。
每个答案都对 \(998244353\) 取模。
数据范围
\[ 1 \le n \le 10^{5}. \]
Comments have been disabled for this content