BOJ 13546 수열과 쿼리 4

H9 하위!
적당히 올릴 거 찾다 수쿼4를 낚아왔다.
뭐.. 풀 때는 고통받으며 푼거 같지만 모스를 안다면 심각히 힘든건 없어보이니 각설하고 풀이하자.

어떤 수열이 주어졌을 때 같은 두 값이 최대한 멀리 떨어진 거리를 구하는 문제이다.
이 문제를 푼다면, BOJ 13545 수열과 쿼리 0도 가볍게 날먹할 수 있다.

우선 풀이는 모스 알고리즘을 안다는 전제 하에 이루어진다. 아직 잘 모른다면 여기를 참고하자.

잘 생각해보자.
우리는 이 문제에서, 수열의 값이 될 수 있는 모든 값 x에 대해 (x가 등장하는 마지막 위치)-(x가 등장하는 첫 위치) 의 max를 찾아야한다.

그럼, 등장할 수 있는 모든 값 x에 대해 x가 등장하는 max Index와 min Index만을 저장하면 되지 않을까?
안타깝게도 이 방법은 사용할 수 없다. min과 max는 역연산이 존재하지 않기 때문에 쿼리의 범위가 이동하면서 해당 max Index 또는 min Index가 삭제될 경우 변경 후의 max Index와 min Index를 찾는 데에 상당한 시간 복잡도가 소요된다.

여기서 막혔다면 다시 한 번 생각해보라. 맨 끝 하나씩만 저장하는게 안 된다면 모든 인덱스를 저장하면 되지 않겠는가?
가능한 모든 x에 대해 A[x]를 x가 등장한 모든 인덱스를 정렬하여 저장한 list로 두자.

또 한 가지 궁금점이 생길 수 있는 부분이다. 정렬 상태를 유지하려면 상당한 시간이 소모되지 않겠는가?
하지만 이 과정이 모스의 쿼리 확장/축소 과정임을 기억해라. 확장과 축소는 반드시 쿼리 범위의 맨 끝에서만 일어난다. 즉 확장으로 추가된 인덱스는 가장 크거나 가장 작으며, 축소의 경우에도 마찬가지이다.

이를 이용하여 모스 알고리즘을 적절히 구현해주면, 적절히 AC를 따낼 수 있다.

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

#define sz(x) x.size()
#define frt(x) x.front()
#define bck(x) x.back()

#define NMAX 100010
#define VMAX 100010
#define QMAX 100010

int n,k,m,sq;
int arr[NMAX];
list<int> exi[VMAX];
int cnt[NMAX];
int sqd[400];
int op[QMAX];

struct Query{
	int idx,s,e;
	bool operator<(Query& t){
		if(s/sq^t.s/sq)return s/sq<t.s/sq;
		return e<t.e;
	}
};

vector<Query> qv;

void add(int x){
	if(sz(exi[arr[x]])>=2){
		int d=bck(exi[arr[x]])-frt(exi[arr[x]]);
		--cnt[d];--sqd[d/sq];
	}
	if(exi[arr[x]].empty()||bck(exi[arr[x]])<x){
		exi[arr[x]].push_back(x);
	}
	else{
		exi[arr[x]].push_front(x);
	}
	if(sz(exi[arr[x]])>=2){
		int d=bck(exi[arr[x]])-frt(exi[arr[x]]);
		++cnt[d];++sqd[d/sq];
	}
}

void erase(int x){
	if(sz(exi[arr[x]])>=2){
		int d=bck(exi[arr[x]])-frt(exi[arr[x]]);
		--cnt[d];--sqd[d/sq];
	}
	if(bck(exi[arr[x]])==x){
		exi[arr[x]].pop_back();
	}
	else{
		exi[arr[x]].pop_front();
	}
	if(sz(exi[arr[x]])>=2){
		int d=bck(exi[arr[x]])-frt(exi[arr[x]]);
		++cnt[d];++sqd[d/sq];
	}
}

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>arr[i];
	for(sq=0;sq*sq<=n;sq++);
	cin>>m;
	qv.resize(m);
	for(int i=0;i<m;i++){
		qv[i].idx=i;
		cin>>qv[i].s>>qv[i].e;
	}
	sort(qv.begin(),qv.end());
	
	int l=1,r=1;
	cnt[0]=sqd[0]=k+3;
	add(1);
	for(int i=0;i<m;i++){
		int s=qv[i].s,e=qv[i].e;
		while(l>s){
			add(--l);
		}
		while(r<e){
			add(++r);
		}
		while(l<s){
			erase(l++);
		}
		while(r>e){
			erase(r--);
		}
		int p=(n+1)/sq;
		while(!sqd[p])p--;
		int q=min(n,(p+1)*sq);
		while(!cnt[q])q--;
		op[qv[i].idx]=q;
	}
	for(int i=0;i<m;i++){
		cout<<op[i]<<"\n";
	}
}