선행 : 모스 알고리즘 모스 알고리즘으로 해결 가능하다. [Li, Ri] 쿼리 구간에 대해 COUNT[x] = (A[j]==x) 인 j 의 갯수 위와 같은 정보를 저장하자. 그러면 모스 알고리즘이 돌아가면서 COUNT[x] 값이 갱신될 때, 정답도 같이 갱신해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465// code by RiKang, weeklyps.com#include#include#include#define PII pair#define PIII pair using namespace::std; const int N = ..
선행 : 모스 알고리즘 모스 알고리즘으로 해결 가능하다. [Li, Ri] 쿼리 구간에 대해 COUNT[x] = (A[j]==x) 인 j 의 갯수 COUNT2[x] = (COUNT[j]==x) 인 j 의 갯수 위와 같은 정보를 저장한다면, COUNT2[x] !=0 을 만족하는 최대의 x가 정답이 됨은 문제 설명 상 자명하다. 또한, [Li, Ri] 일 때의 정답과 [L(i+1), R(i+1)] 일 때의 정답의 차이는 |L(i+1)-L(i)| + |R(i+1)-R(i)| 이하이다.(* 추가or삭제되는 A[j] 의 개수보다 정답이 더 크게 변할 순 없기 때문이다. 정답이 증가할 때와 감소할 때 모두 생각해 보면 간단히 증명 가능) 이를 이용해 'COUNT2[x] !=0 을 만족하는 최대의 x' 를 지속적으로 ..