大家好，我是 Piggod，notch 说让我讲一篇线段树入门，讲了将给我 6767676767 dollar。
题单：https://atcoder.jp/contests/aalc001
3，2，1。
A
线段树板子，没啥好讲的。
B
注意到 (min,+)(\min,+)(min,+) 运算是可以合并的，上懒标记线段树即可。
C
考虑在线段树里面二分。
只说询问 222。当前区间为 [l,r][l,r][l,r] 的时候，如果答案加 [l,mid][l,mid][l,mid] 还不会超，那就递归右儿子；否则递归左儿子。
O(qlogn)O(q\log n)O(qlogn)。
D
空悲切。
维护：
* cic_ici 为区间内 iii 的个数。
* fi,jf_{i,j}fi,j 为区间 x<yx\lt yx<y，cx=i,xy=jc_x=i,x_y=jcx =i,xy =j 的方案数。
显然可以线段树维护。
答案即为 ∑i=12∑j=0i−1fi,j\sum_{i=1}^2\sum_{j=0}^{i-1} f_{i,j}∑i=12 ∑j=0i−1 fi,j 。
时间复杂度：O(qV2logn)O(qV^2\log n)O(qV2logn)。
如果值域再大一点，开 nV2nV^2nV2 个节点会 MLE，那咋办？
可以离线下来所有询问，扫 VVV 遍，第 iii 遍只维护 fif_{i}fi 。时间复杂度不变。
E
维护区间内 R G B RG GB RGB 的答案。
O(qklogn)O(qk\log n)O(qklogn)，k=5k=5k=5。
F
最长连续段板子。维护区间左端点开始最长连续段，右端点开始最长连续段，然后随便判判即可。
时间复杂度：O(qlogn)O(q\log n)O(qlogn)。
G
维护 ∑Ai,∑Ai2,∑Ai3,∑Ai4\sum A_i,\sum A_i^2,\sum A_i^3,\sum A_i^4∑Ai ,∑Ai2 ,∑Ai3 ,∑Ai4 ，然后二项式展开推一个特别史的式子即可。
时间复杂度：O(qk2logn)O(qk^2\log n)O(qk2logn)。
未完待续。
