[백준] 25219 - Alternating Heights (c++)

https://www.acmicpc.net/problem/25219

 

문제 요약

각각 키가 다른 학생 K종류가 있다. 일렬로 서있는 학생들의 종류를 나타내는 수열 A와 Q개의 쿼리가 주어진다. 각 쿼리에서 부분 배열 Al~Ar 이 교대 수열을 만족할 수 있는지 판별해라.
교대 수열이란 다음 조건을 만족하는 배열이다:
h[Al]>h[Al+1]<h[Al+2]>h[Al+3]<...h[Ar]

 

풀이 (N^2+Q)

• 투포인터
• 위상정렬

키의 대소관계를 표현한 그래프에서 사이클이 있는지 판별하는 문제로 바꿀 수 있다. 그래프에서 사이클이 있는지는 위상렬로 O(N)에 구할 수 있고 이를 투포인터로 각 l의 대한 최대 r을 전처리 하여 쿼리를 O(1)에 처리할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,k,q;cin>>n>>k>>q;
    int a[n];
    for(int& x:a)cin>>x;
    int mxr[n];
    int r=0;
    for(int i=0;i<n;i++) {
        bool dag=1;
        while(r<n&&dag) {
            //cout<< i<<' '<<r<<'\n';
            int deg[n+1]{};   
            queue<int> q;
            vector<int> adj[k+1]{};
            bool dir=0;
            for(int j=i+1;j<=r;j++) 
                if(dir=!dir)
                    adj[a[j]].push_back(a[j-1]),deg[a[j-1]]++;
                else
                    adj[a[j-1]].push_back(a[j]),deg[a[j]]++;
            for(int j=1;j<=k;j++)
                if(!deg[j])q.push(j);
            while(q.size()) {
                int u=q.front();q.pop();
                for(int v:adj[u]) 
                    if(!--deg[v])
                        q.push(v);
            }
            for(int x:deg)
                if(x)dag=0;
            if(dag)
                r++;
        }
        mxr[i]=r;
    }
    while(q--) {
        int l,r;cin>>l>>r;
        l--;r--;
        //cout<< mxr[l]<<' ';
        if(mxr[l]>r)
            cout<<"YES"<<'\n';
        else
            cout<<"NO"<<'\n';
    }
}