将一个长度为$n$的序列复制$k$次，要求维护数据结构支持区间赋值与区间最小值查询，$q$次操作。$(n,q \le 10^5,k \le 10^4)$

线段树动态开点，对于没有开点的部分$[l,r]$，可以将原序列复制一遍到$2n$长度，将其对应到$[(l-1)\mod n+1,(l-1)\mod n+1+l-r]$的区间，使用ST表$O(1)$查询即可。

给定长度为$n$的序列，$q$次询问在$[l,r]$中最多能选多少数满足同一个数的出现次数不超过$k$，强制在线。$(n,q,k \le 10^5)$

设$a_i$为第$i$个数后面第$k$个相同的数的下标，如果没有则为$n+1$。所求转化为$[l,r]$区间内有多少$a_i>r$，主席树维护即可。

给定一个长度为 $n$ 的数列，每次选择两个不相交区间，在两个区间中各任意选择一个数，交换两个数的位置，每次询问询问一个区间的和的期望。

考虑左侧区间长度为 $L_1$, 右侧区间长度为 $L_2$ ,左侧区间期望和为 $E(L_1)$ ，则删除一个数之后的期望和应为 $\frac{(L_1 - 1)E(L_1)}{L_1}$，考虑右侧选择一个数 $a_i$ 对左侧区间的贡献为 $\frac{\sum_{i \in L_2} a_i}{L_2} = \frac{E(L_2)}{L_2}$ ,考虑对于左侧子区间的影响，应该考虑对左侧区间每个位置的贡献为 $\frac{E(L_2)}{L_2 L_1}$ 即可，线段树区间加区间乘维护即可。

给定一个长度为$2^n$的序列，维护一个数据结构支持以下几种操作。
1.单点赋值。
2.给定$k$，对于所有$i \ge 1$，翻转$[(i-1) \cdot 2^k+1, i \cdot 2^k]$区间。
3.给定$k$，对于所有$i \ge 1$，将$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$区间和$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$区间交换。
4.区间求和。
$(0 \le n \le 18,1 \le q \le 10^5)$

我们将序列从$0$开始编号，可以发现操作2和操作3分别等价于将$a_i$变为$a_{i\text{^}(2^k-1)}$和$a_{i\text{^}(2^k)}$。因此我们可以维护一个$x$，初始值为$0$，当进行2和3操作时根据上述规律对$x$进行异或，进行1或4操作时只需将对$a_i$的操作改为对$a_{i\text{^}x}$的操作即可。