题目大意

详细题目传送门
有 \(k\) 个未知数 \(k_1,k_2,\cdots,k_n\)

然后有一个数组 \(a\)。

\(Q\) 组询问，每组给出 \(l,r\)。求是否存在一种赋值方法满足 \(k_{a_l}>k_{a_{l+1}}<k_{a_{l+2}}>\cdots k_{a_r}\)。即满足大于小于大于··· 。
\(k\leq n\leq 3000,Q\leq 10^6\)

思路

发现对于多组数据每组单独处理肯定是无法做到的。可以看看能不能先根据一些区间的连续性来推出每一个区间是否合法。

之后发现对于一个区间 \([l,r]\) 合法，那么 \([l,i],i\in [l,i]\) 全部合法。若 $[l,r] $ 不合法，则 \([l,i],i\in[r,n]\) 一定全部不合法。所有我们发现可以枚举每一个 \(l\)，尝试二分求出一个最大的 \(r\) 使 \([l,r]\) 合法。

之后考虑如何判断 \([l,r]\) 是否合法。发现类似与差分约束，可是只有大于关系没有不等式关系。于是对于每一个要求的 \(h_{A_{x-1}}>h_{A_x}<h_{A_{x+1}}\)，我们连两个有向边 \(A_{x-1}\rightarrow A_x\) 和 \(A_{x+1}\rightarrow A_x\)。之后得到一张有向无权图。

显然如果图出现了环就非法，没有就合法。考虑到 \(h\) 互不相同的条件发现所有的有向边的约束全部是大于关系，且没有规定 \(h\) 的值域，所以自然不存在相等情况。

时间复杂度 \(Q+n^2\log n\)。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=3000+5;
const ll MAXQ=1e6+5;
ll n,k,Q;
ll a[MAXN];
bool gd[MAXN][MAXN];
vector<ll>adj[MAXN];
ll ind[MAXN];
void add(ll u,ll v){
	adj[u].push_back(v);
	ind[v]++;
}
bool check(ll l,ll r){
	memset(ind,0,sizeof(ind));
	for(int i=1;i<=k;++i){
		adj[i].clear();
	}
	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<ll>q;
	ll tot=0;
	for(int i=1;i<=k;++i){
		if(!ind[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		tot++;
		for(auto v:adj[u]){
			ind[v]--;
			if(!ind[v]){
				q.push(v);
			}
		}
	}
	return tot==k;
}
ll ans[MAXN];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>Q;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=1;i<=n;++i){
		ll l=i,r=n;
		ans[i]=i;
		while(l<=r){
			ll mid=(l+r)>>1;
			bool good=check(i,mid);
			if(good){
				l=mid+1;
				ans[i]=mid;
			}else{
				r=mid-1;
			}
		}
	};
	for(int i=1;i<=Q;++i){
		ll x,y;
		cin>>x>>y;
		if(y<=ans[x]){
			cout<<"YES\n";
		}else{
			cout<<"NO\n";
		}
	}
	return 0;
}