自动搬运

查看原文

来自洛谷，原作者为

	Elysian_Realme 吾愿你前行的道路有群星闪耀。愿你留下的足迹有百花绽放。你即是上帝的馈赠，世界因你而瑰丽。

搬运于2025-08-24 22:54:12，当前版本为作者最后更新于2024-03-28 22:02:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10050 [CCO2022] Alternating Heights

解题思路

先考虑暴力，对于每一个 $[l,r]$ 的区间，我们都可以将其抽象成一个由大小关系组成的图（从大指向小）。

如果没有环，那么这些学生的身高排序就是这张图的拓扑序。

如果这张图出现了环，那么肯定不成立（因为必定可以推出来 $x < x$）。

如果直接这么写显然就是 $O(n^3+q)$（$O(n^2)$ 枚举每一组 $[l,r]$ 再拓扑）。

不难发现，$\forall l,r\in [1,n],l<r$ 如果 $[l,r]$ 成立，那么 $[l,r-1]$ 必定成立，如果 $[l,r]$ 不成立，那么 $[l,r+1]$ 必定不成立。

这样一来，我们就可以二分预处理出每一个 $l$ 最大的 $r$，复杂度就可以变成 $O(n^2\log n+q)$

// Problem: P10050 [CCO2022] Alternating Heights
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10050
// Memory Limit: 1000 MB
// Time Limit: 2000 ms
// 
// By：lmq
// AC Time：2024-03-28 19:53:18

#include <bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,nxt;
}mp[100005];
int n,k,m,top,cnt,ans;
int a[3003],v[3003];
int idx[3003],rd[3003];
void add(int u,int v){
	rd[v]++;
	mp[++top].u=u;
	mp[top].v=v;
	mp[top].nxt=idx[u];
	idx[u]=top;
}
bool check(int l,int r){
	cnt=0,top=0,ans=0;
	memset(idx,0,sizeof(idx));
	memset(rd,0,sizeof(rd));
	for(int i=l+1;i<=r;i+=2){
		add(a[i-1],a[i]);
		if(i+1<=r){
			add(a[i+1],a[i]);
		}
	}
	queue <int> que;
	for(int i=1;i<=k;i++){
		if(!rd[i])
			que.push(i);
	}
	while(!que.empty()){
		int u=que.front();
		cnt++;
		que.pop();
		for(int i=idx[u];i!=0;i=mp[i].nxt){
			int v=mp[i].v;
			if(!--rd[v])
				que.push(v);
		}
	}
	return cnt==k;
}
signed main(){
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++){
		int l=i-1,r=n+1;
		while(l+1!=r){
			int mid=(l+r)>>1;
			if(check(i,mid))
				l=mid;
			else
				r=mid;
		}
		v[i]=max(l,i);
	}
	for(int i=1;i<=m;i++){
		int l,r;scanf("%d%d",&l,&r);
		if(r<=v[l])
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}