这是一道好题！
要求一张牌只能用一面，说明选了一面就不能选另一面（废话）。
这种限制关系我们可以用二分图的思想解决。
于是把每张牌的两面的值连边。
对于一条边只能选一个端点。
如果连出了环说明每个点都能被选到，如果连出的是树，说明一定有一个点是选不到的。
我们要求的顺子中如果包含了一棵树，那么这棵树包含的那一段就是凑不出的，即不合法。
求出一个联通块是环还是树并查集即可。
对于每一棵树我们可以求出它的max和min。
那现在问题转化为：对于一段区间，判断它是否完全包含了一些小区间。
按照右端点排序，看左端点是否包括即可。
而那些不包括在牌内的值在图中就变成了一个点（可以说是简化的树吧）。
如果顺子要求这个值肯定也是不合法的。
#include<bits/stdc++.h>
#define LL long long
#define N 100003
#define INF 2100000000
#define mod 1000000007
using namespace std;
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
int n,K,Q;
int minn,maxx,fa[N],vis[N],ans[N];
vector<int>tree[N],q;
struct node{
int l,r,id;
}qry[N];
vector<node>V;
bool cmp(const node &x,const node &y)
{
return x.r<y.r;
}
int get(int x)
{
if(fa[x]==x)return x;
return fa[x]=get(fa[x]);
}
void dfs(int x)
{
minn=min(minn,x);maxx=max(maxx,x);
for(int i=0;i<tree[x].size();++i)
{
int v=tree[x][i];
if(vis[v])continue;
vis[v]=1;
dfs(v);
}
}
int main()
{
n=read();K=read();
for(int i=1;i<=n;++i)fa[i]=i;
for(int i=1;i<=K;++i)
{
int a=read(),b=read();
int f1=get(a),f2=get(b);
if(f1==f2)q.push_back(a);//判断是环是树
else
{
fa[f1]=f2;
tree[a].push_back(b);
tree[b].push_back(a);
}
}
for(int i=0;i<q.size();++i)
if(!vis[q[i]])vis[q[i]]=1,dfs(q[i]);
for(int i=1;i<=n;++i)
{
if(vis[i])continue;
minn=n,maxx=1;
vis[i]=1;
dfs(i);
V.push_back({minn,maxx,0});
}
Q=read();
for(int i=1;i<=Q;++i)qry[i].l=read(),qry[i].r=read(),qry[i].id=i;
sort(qry+1,qry+1+Q,cmp);
sort(V.begin(),V.end(),cmp);
int p=0,maxl=0;
for(int i=1;i<=Q;++i)//将所有询问放在一起处理
{
while(p<V.size()&&V[p].r<=qry[i].r)maxl=max(maxl,V[p].l),p++;
if(maxl>=qry[i].l)ans[qry[i].id]=1;
}
for(int i=1;i<=Q;++i)
{
if(ans[i])printf("No\n");
else printf("Yes\n");
}
return 0;
}
/*
*/
View Code