[NOISG 2023 Finals] Curtains

[NOISG 2023 Finals] Curtains

给定 \(m\) 个区间 \([l_i, r_i]\)，\(q\) 次询问，回答是否存在若干区间的并恰好为 \([u_i, v_i]\)。

\(1 \le n, m,q \le 5 \times 10^5\)，\(1 \le l_i \le r_i \le n\)

离线进行扫描线是显然的。把询问挂在 \(r\) 上，处理 \(l\) 的答案。

显然，对于询问 \([L,R]\)，所有满足 \(L \le l_i \le R\) 的区间的并必须恰好为 \([L, R]\)，有两个方向：

第一种

考虑把区间填满：如果有位置 \(L \le i \le R\) 没有任何区间覆盖到，则该询问 NO。所以考虑对于每一个位置 \(i\) 记录覆盖该点的区间中 \(l\) 的最大值：

\[f_i=\max _{l_j \le i \le r_j \le R}\{ l_j\} \]

那么就要求 \(\forall L \le i \le R\)，\(f_i \ge L\)，即 \(\min \limits_{L \le i \le R} f_i \ge L\)（实际上由于 \(f_i \le i\)，此处 \(\min \limits_{L \le i \le R} f_i=L\)）。

得出为 YES 的充要条件。

那么 \(f\) 怎么维护呢，这显然是一个区间取 \(\max\)，区间求 \(\min\) 的问题，线段树可以直接维护。

第二种

考虑让区间相连接。维护 \(g_i\) 表示左端点为 \(i\)，最远能覆盖到哪里。询问 \([l,r]\) 为 YES 的充要条件是 \(g_l = r\)。

加入一个区间 \([l,r]\)，会使满足 \(i \le l\) 且 \(g_i \ge l\) 的 \(g_i \gets r\)。这个看似不好维护，实际上可以维护 min，在所有 \(g_i\) 都满足的区间上做区间赋值，其余暴力到叶子，复杂度不高于双 log。听说还能直接打标记维护。