DpsD everyday

2025-9-3

Coloring Brackets

第一天选水了。
设 \(f[l,r,a,b]\) 表示合法匹配区间 \([l,r]\) 内的染色方案，要求左端点是 \((\) 且染色状态为 \(a\) ，右端点是 \()\) 且染色状态为 \(b\) 。
直接分讨转移即可。

Record

Sonya and Bitwise OR

对于单次询问，考虑 \(cdq\) 分治。
然后发现，按位或是满足单调性的运算，可以使用双指针统计，进一步发现，\(\boldsymbol{或运算的值最多改变\log 次}\) 。
所以可以提前预处理中点向两边或的值改变的位置，这样可以 \(\log n\) 合并。
把这个过程放到线段树上，就可以解决本题。复杂度 \(O(n\log n\log a)\) 。

Record