题解：P11080 [ROI 2019 Day 1] 拍照

· · 题解

闲话

考试碰到了这题，然后切了，然后代码厌氧，然后报了个 5 分回家！！！

讲题时把我推上去了，回来后点击蓝色按钮发现能写题解？

前置

分块？

分块在上，愿祂永远不会让你 WA，永远不会让你 TLE，永远不会让你 MLE，永远不会让你 RE。

Pro

给定一个序列，对于每一个 k，可以将 [l,r] 的数都改为 k，顺序任意，但每个 k 只能使用一次。问能否存在一种方案，使得序列最后变为一个期望的区间。

Sol

由于每种颜色只能染一次，那么颜色 i 染色的区间就一定是最靠左出现的 i 的节点编号和最靠右出现的 i 的节点编号。（至少此情况成立）

考虑一种无解的情况：有两个区间相交。如果两个区间相交，中间的部分将会同时出现 i 和 j 两种颜色，而这两种颜色覆盖之后，必然有一种颜色在上面，故不可能有解。

接着考虑所有区间的染色顺序。先说结论：按左端点 l 排序。因为已经没有了相交的情况，剩下的两种情况一定为相离或包含。如果是相离，那么什么顺序都可以；如果是包含，则 l_1<l_2<r_2<r_1 即可。所以按左端点排序一定是正确的。

最后再染一次色验证即可。暴力染色是 O(nm) 的，肯定过不去。可是作者想不到 @Wind_Leaves_Shadow 的解法，看到 3\times 10^5 这么可爱的数据，都能让 O(n\sqrt m) 过去，那必须秉承“能分块，不线段树”的原则，启动分块啊！！！

时间复杂度：O(n\sqrt m)，暂定最慢解。

Code

这里只贴了染色的代码：

for(int i=1;i<=num/*出现颜色个数*/;i++)
{
  int l=col[i].l,r=col[i].r,co=col[i].i;
  if(id[l]==id[r])
  {
    sk(l,r,co); // 处理散块
  }
  else
  {
    sk(l,L[id[l]+1]-1,co);
    sk(L[id[r]],r,co);
    for(int i=id[l]+1;i<id[r];i++)
    fk[i].first=1,fk[i].second=co;
  }
}

注：代码厌氧，作者应该强制 O2 的。