首先把初始的 \(a\) 也看成一个操作。
考虑所有满足 \(l_i=1\) 的操作，找到 \(x_{i,1}\) 最大的操作中 \(r_i\) 最小的操作 \(p\)，对所有操作进行如下修改：
- 如果 \(r_i\leq r_p\)，那么把 \(i\) 删去。
- 否则，将 \(x_{i}\) 的前缀替换成 \(x_p\)。
这样所有 \(l_i=1\) 的 \(x_{i,1}\) 都相同，于是我们可以把第一位删去，进入新的子问题。容易证明原问题中所有方案都可以对应到新问题上的一个方案。
直接暴力模拟可以得到一个 \(\mathcal{O}(L^2)\) 的做法，考虑优化。注意到如果某个操作的首位是之前被染过色的，那么它一定不会成为上文中的操作 \(p\)，因为将它染色的操作一定比它更优。所以首位被染过色的操作一定不会成为答案，自然地，其首位的具体值也不重要，我们只需要维护一个操作被染色部分的右端点 \(col_i\)。考虑 \(col_i\) 什么时候变化，注意到若 \(r_p>col_i\) 的时候，操作 \(i\) 一定被染色，所以每次将 \(col_i\) 和 \(r_p\) 取 \(\max\) 即可。
https://uoj.ac/submission/679817
标签：龙门,过色,染色,UOJ839,题字,被染,操作,col From： https://www.cnblogs.com/yllcm/p/18031428