题解：P10050 [CCO2022] Alternating Heights

Elysian_Realme · 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;
}