题解：AT_abc457_e [ABC457E] Crossing Table Cloth
manboo
·
·
题解
题意概述：
不难发现，对于询问 $S,T$，选择两块布 $i,j$ 满足题目条件，不妨设 $l_i\le l_j$，该方案必然属于以下两种方案之一：
- 方案一：$S=l_i\le l_j-1\le r_i<r_j=T$。即，布 $i$ 覆盖 $S$ 而不覆盖 $T$，布 $j$ 覆盖 $T$ 而不覆盖 $S$，布 $i,j$ 覆盖 $\left[S,T\right]$。这里不用考虑 $i,j$ 是否相等，因为 $l_i\le l_j-1$ 就已经决定了 $i\ne j$。
- 方案二：$i\ne j,S=l_i\le l_j\le r_j\le r_i=T$。即，布 $i$ 只覆盖 $\left[S,T\right]$，布 $j$ 覆盖在 $\left[S,T\right]$ 之内，且两布不相等。这里，只是说 $i\ne j$，不代表 $l_i\ne l_j,r_i\ne r_j$。
两种方案交集为空，并集为所有满足题目条件的方案。
不难发现，两种方案都要用到以 $S$ 为左端点的布，和以 $T$ 为右端点的布，因此考虑用 $a_l$ 存储所有以 $l$ 为左端点的布的右端点 $r$，用 $b_r$ 存储所有以 $r$ 为右端点的布的左端点 $l$，其内部从小到大排序，注意不可以去重，即使有重复的也可以在方案二里用到。
对于方案一，贪心地让 $r_i$ 尽可能大，$l_j$ 尽可能小，只要 $r_i<T$ 的最大 $r_i$ 与 $l_j>S$ 的最小 $l_j$ 满足 $l_j-1\le r_i$，那么就是合法的。这可以通过二分查找来实现。
对于方案二，首先需要满足存在**至少**一块布的覆盖区间为 $\left[S,T\right]$，其次需要快速判断区间 $\left[S,T\right]$ 内是否存在布 $j$ 满足 $S\le l_j\le r_j\le T$ 且 $i\ne j$。转换一下：
- 存在**至少**两块布的覆盖区间为 $\left[S,T\right]$，此时必然合法。
- 不存在布的覆盖区间为 $\left[S,T\right]$，此时必然不合法。
- 存在**恰好**一块布的覆盖区间为 $\left[S,T\right]$，并且存在布 $j$ 满足 $S\le l_j\le r_j<T$ 或 $S<l_j\le r_j\le T$。
对于前两种情况，可以开个 map 记录所有覆盖区间的个数。
对于第三种情况，我们先考虑条件一：存在布 $j$ 满足 $S\le l_j\le r_j<T$。
换句话说，就是在所有左端点大于或等于 $S$ 的布中，最小右端点需要小于 $T$。
设函数 $f_r\left(l\right)$ 表示以 $l$ 为左端点的布中的最小右端点，函数 $g_r\left(l\right)$ 表示左端点大于或等于 $l$ 的布中的最小右端点，那么 $g_r\left(l\right)$ 就是 $f_r\left(l\right)$ 的后缀最小值，即：
$$g_r\left(l\right)=\min\limits_{i=l}^n f_r\left(i\right)=\min\left(g_r\left(l+1\right),f_r\left(l\right)\right)$$
读入时预处理 $f_r$ 函数，然后从后往前枚举 $l$ 即可预处理得到 $g_r$ 函数。
当 $g_r\left(S\right)<T$ 时，条件一成立；否则不成立。
考虑条件二：存在布 $j$ 满足 $S\le l_j\le r_j<T$。
换句话说，就是在所有右端点小于或等于 $T$ 的布中，最大左端点需要大于 $S$。
设函数 $f_l\left(r\right)$ 表示以 $r$ 为右端点的布中的最大左端点，函数 $g_l\left(r\right)$ 表示右端点小于或等于 $r$ 的布中的最大左端点，同理可以读入时预处理 $f_l$ 函数，然后从前往后枚举 $r$ 预处理得到 $g_l$ 函数：
$$g_l\left(r\right)=\max\limits_{i=1}^r f_l\left(i\right)=\max\left(g_l\left(r-1\right),f_l\left(r\right)\right)$$
当 $g_l\left(T\right)>S$ 时，条件二成立；否则不成立。
当两个条件满足至少一个时，第三种情况合法；否则不合法。
方案一、二同样只要满足其一，答案即为 `Yes`；否则答案为 `No`。
代码如下：
```c++
typedef pair<int,int> pir;
const int N=200005;
int n,m;
int fr[N],gr[N],fl[N],gl[N];
vector<int> a[N],b[N];
map<pir,int> cnt;
int q,S,T;
inline bool proposal_1()
{
// 方案一
int ri=0,lj=0;
auto it_ri=lower_bound(a[S].begin(),a[S].end(),T);
if(it_ri==a[S].begin()) return false;
it_ri--,ri=*it_ri;
auto it_lj=upper_bound(b[T].begin(),b[T].end(),S);
if(it_lj==b[T].end()) return false;
lj=*it_lj;
return lj-1<=ri;
}
inline bool proposal_2()
{
// 方案二
int t=cnt[{S,T}];
if(t>=2) return true;
if(!t) return false;
return gr[S]<T||gl[T]>S;
}
int main()
{
memset(fr,0x3f,sizeof(fr));
memset(fl,0,sizeof(fl));
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
fr[l]=min(fr[l],r);
fl[r]=max(fl[r],l);
a[l].push_back(r);
b[r].push_back(l);
cnt[{l,r}]++;
}
gr[n]=fr[n];
for(int l=n-1;l;l--) gr[l]=min(gr[l+1],fr[l]);
gl[1]=fl[1];
for(int r=2;r<=n;r++) gl[r]=max(gl[r-1],fl[r]);
for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end()),sort(b[i].begin(),b[i].end());
q=read();
for(int i=1;i<=q;i++)
{
S=read(),T=read();
if(proposal_1()||proposal_2()) puts("Yes");
else puts("No");
}
return 0;
}
```