color
显然没有被删除的元素形成一个子区间，所以答案的规模是 O(n^2) 的。对于一种颜色，如果一个区间内部和外部都有这种颜色的元素，那么这个区间就是不合法的。对于每个元素我们可以找出包含它的不合法区间，它们的左端点和右端点都有一个区间范围的限制。我们将区间视为平面上的一个点，那么不合法的区间可以视为 O(n) 个与坐标轴平行的矩形。用线段树维护一条扫描线从左往右扫，如果撞到矩形左边缘就在线段树中加入这条线段；如果撞到右边缘就弹出这条线段。求左端点固定的合法区间个数就是求当前线段树上权值为 0 的整点数，因为所有值都非负，维护一下最小值和最小值个数就可以了。
tree
如果 k=1 的话，我们可以两遍 DFS 求出每个点到其他点的距离和。考虑一般情况，我们也可以维护 0 次方到 k 次方和，然后二项式定理转移。这样做的复杂度是 O(nk^2) 的。
考虑到下降幂的可离散微分性（(x+1)^\underline{k}-x^\underline{k}=kx^\underline{k-1}），我们可以先求出下降幂和，然后用斯特林数将下降幂转为普通幂。这样就可以 O(k) 转移了，复杂度为 O(nk)。
square
考虑没有限制的情况，设 f_n 为长度为 n 的答案。则：
f(n)=\sum_{i=1}^n f_{n-i}\cdot i^2
设 F(x) 为数列 \{f_n\} 的生成函数，G(x) 为数列 \{n^2\} 的生成函数，则
F=1+FG
其中 G 的封闭形式是可以两次求导乘 x 求出的：
G(x)=\frac{x^2+3}{(1-x)^3}
解得
F(x)=\frac{(1-x)^3}{1-4x+2x^2-x^3}
展开成递推式，得
f_n=4f_{n-1}-2f_{n-2}+f_{n-3}
可以矩阵快速幂或者多项式取模做到 O(\log N)。
现在加入限制。考虑容斥，枚举 k 个有限制的位置强制断开，设这 k 个位置为 x_1,\cdots,x_k。此外，我们钦定 x_0=0,x_{k+1}=N。这组位置对答案的贡献为
(-1)^k\prod_{i=0}^k f_{x_{i+1}-x_i}
直接枚举复杂度是指数级的，但我们可以 DP。设 h_n 表示考虑了前 n 个限制，且第 n 个限制强制断开的答案，那么我们枚举上一次钦定断开的位置，可以得出转移
h_n=-\sum_{i=0}^{n-1}h_i f_{x_n-x_i}
答案就是 h_{M+1}。于是我们有了一个 O(M^2\log N) 的做法。但这还不够优秀，我们发现 h_n 到 h_{n+1} 就是乘了个 x_{n+1}-x_n 次的 f 的转移矩阵，再加上一项断开 x_{n+1} 的答案。所以我们把 h 也当成一个矩阵维护，就可以做到 O(\log N) 转移，总复杂度 O(M\log N)。
实际上这道题这样做还是复杂了，我们直接记答案的 0-2 次方和，分段做矩阵快速幂即可。但是前面这种方法更具有拓展性。
冷滟泽的个人博客