투포인터1 [백준] 25219 - Alternating Heights (c++) https://www.acmicpc.net/problem/25219 문제 요약각각 키가 다른 학생 K종류가 있다. 일렬로 서있는 학생들의 종류를 나타내는 수열 A와 Q개의 쿼리가 주어진다. 각 쿼리에서 부분 배열 Al~Ar 이 교대 수열을 만족할 수 있는지 판별해라.교대 수열이란 다음 조건을 만족하는 배열이다:h[Al]>h[Al+1]Al+2]>h[Al+3]Ar] 풀이 (N^2+Q)투포인터위상정렬키의 대소관계를 표현한 그래프에서 사이클이 있는지 판별하는 문제로 바꿀 수 있다. 그래프에서 사이클이 있는지는 위상렬로 O(N)에 구할 수 있고 이를 투포인터로 각 l의 대한 최대 r을 전처리 하여 쿼리를 O(1)에 처리할 수 있다.#include using namespace std;#define ll long l.. 2025. 1. 23. 이전 1 다음