P11233 [CSP-S 2024] 染色——某种对区间处理的trick?
暴力
首先有一个十分显然的暴力
记录每个颜色结尾的位置，然后n^2转移
总复杂度 O(n^3)
显然炸掉
研究一下答案的结构
当一个点产生贡献时，那么肯定前方有一个对应的点呼应
要让这两个点呼应上就得让中间一段是一个全部为同一个数的区间
如果把头尾都算起来变成一个区间的话（至于为什么，可以看作是对这一整段的约束），就可以很方便地观察到什么情况下两个区间可以共存了
举了几个例子之后发现两个区间可以共存
那么这个时候就可以把区间的两端给削掉，将条件转化为两两不交
同时可以发现，转化后的区间两两不交是对的，对区间两端的限制可以直接转化为01的取反
（其实好像不削掉也可以用就是了）