1. 复杂信息维护
- 题意：
给定序列 \(a_1,a_2,...,a_n\)，支持两种操作：
- 给 \(l \le x \le r\) 的所有 \(a_x\) 加上 \(k\)。
- 查询 \(\sum\limits_{i=l}^{r}sin(a_i)\)。
\(n,m\le 10^5\)
- 做法：
维护 \(\sin\) 和还有 \(\cos\) 和就行。
理由是下面这俩柿子：
\[\begin{aligned}\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta\\\cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta\end{aligned} \]所以：
\[\begin{aligned}\sum\limits_{k=l}^{r}\sin(a_k+c)=\sum\limits_{k=l}^{r}(\sin a_k\cos c+\sin c\cos a_k)=\cos c(\sum\limits_{k=l}^{r}\sin a_k)+\sin c(\sum\limits_{k=l}^{r}\cos a_k)\\ \sum\limits_{k=l}^{r}\cos(a_k+c)=\sum\limits_{k=l}^{r}(\cos c\cos a_k-\sin c\sin a_k)=\cos c(\sum\limits_{k=l}^{r}\cos a_k)-\sin c(\sum\limits_{k=l}^{r}\sin a_k)\end{aligned}\]- 题意：
给你一颗树的括号序列，求其直径。
然后 \(m\) 次询问，每次交换两个括号，求交换后的直径。
保证交换后的序列合法。
\(n,m\le 10^5\) - 题解
- 题意：
- 区间修改：\(a_i=a_i\times c,i\in[l,r]\)。
- 区间询问：\(\varphi(\prod\limits_{i=l}^{r}a_i)\mod (10^9+7)\)。
\(n\le 4\times 10^5,q\le 2\times 10^5\)
2. 需要脑洞的题目
- 题意：
将序列子段从小到大或从大到小排序,一共 \(m\) 次，最后查询位置 \(q\) 上的值。
\(n,m\le 10^5\) - 做法：
考虑 \(01\) 序列的排序如何实现。
我们发现 \(01\) 序列排序之后有一边是 \(0\)，一边是 \(1\)，所以给某个子段排序相当于两个区间覆盖操作，可以使用线段树维护
然后再考虑对于原数组 \(a_i\)，二分 \(q\) 位置上的最终值 \(p\)。将 \(a_i<p\) 的 \(i\) 标记为 \(0\) ，否则标记为 \(1\)。对于这个 \(01\) 序列排序，最后如果位置 \(q\) 上面的数是 \(1\)，就说明 \(p\) 一定比这个二分的值大。
嗝，咕咕咕