- CF1313D
- \(k \le 8\) 明示状压 \(DP\) 。
- 考虑将一种魔法在 \(L\) 处加入，在 \(R+1\) 处删除，将这 \(2n\) 个点 (设为序列 \(a\) ) 排序后，让 \(x\) 管理 \([a_x,a_{x+1})\) ，认为 \(a_{2*n+1}=a_{2*n}\) ，注意可能一个点重复出现，但这没有影响。
- 设当前扫到 \(x\) ，设 \(dp_j\) 表示覆盖 \(x\) 管理的区间状态为 \(j\) ，最多 \(8\) 个，前缀管理到的孩子区间最多几个能开心。
- 初始 \(dp_0=0\) ，其余为 \(-inf\) 。
- 转移，
对于加入，找到没被覆盖的位置 \(k\) 插入，设区间长度为 \(len\) 。
若 \(j\) 的第 \(k\) 位为 \(1\) ，\(dp_j=dp_{j\oplus(1<<k)}+len*[j有奇数个位为1]\) 。
否则，\(dp_j+=len*[j有奇数个位为1]\) 。
对于删除，找到其位置 \(k\) ，将覆盖标记清空。
若 \(j\) 的第 \(k\) 位为 \(1\) ，\(dp_j=-inf\) 。
否则，\(dp_j=max(dp_j,dp_{j\oplus(1<<k)})+len*[j有奇数个位为1]\)。
- 这个题当然有其它更复杂的做法，但这种做法码量优势极大，所与 \(DP\) 题会做后一定要尝试有无更简单的做法。
