BOJ 13546 | 수열과 쿼리 4

아이디어는 고민해보니 떠오르는데 어디선가 자꾸 틀려서 나를 미치게 했던 문제다.

뭔가 오류는 발견되고 수정되는데 계속 1%컷나는게 정신에 심대한 악영향을 주었다;;

마지막에 MaxDistance를 연산하는 부분에서 SIZE_PER_BUCKET을 BUCKET_SIZE로 잘못 적었던 걸 눈치채지 못하고 다른 곳에서 한참 삽질했다.

원래는 수열과 쿼리 6을 풀었던 아이디어로 접근했으나 [i, j]에 같은 수가 3개 이상 들어갈 때를 고려하지 못했고, 평방 분할을 사용해야 한다는 글을 보고 따로 calculateMD 함수를 만들어서 처리하였다.

삽질하는 과정에서 JusticeHui님의 코드를 참고하였다.
https://justicehui.github.io/ps/2019/10/04/BOJ13546/

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

#define lint long long

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Query{
	int l, r;
	int idx;
};

int N, K;
lint arr[101100];
lint table[101100];
vector<list<int>> hatidx;

vector<Query> q;
lint ans[101100];

const int SIZE_PER_BUCKET = 300;
const int BUCKET_SIZE = 111111 / SIZE_PER_BUCKET + 20;

lint bucket[BUCKET_SIZE];

bool _cmp(Query &a, Query &b){
	if (a.l / SIZE_PER_BUCKET != b.l / SIZE_PER_BUCKET) 
		return a.l / SIZE_PER_BUCKET < b.l / SIZE_PER_BUCKET;
	return a.r < b.r;
}

void _Add(int x, int fb){ // x is index ( 1 ~ N ), 0left 1right
	//debug << "add excute" << endl;
	auto &hdx = hatidx[arr[x]];
	if (!hdx.empty()){
		int odis = hdx.back() - hdx.front();
		table[odis]--;
		bucket[odis/SIZE_PER_BUCKET]--;
	}
	
	if (fb == 1) hdx.push_back(x);
	else hdx.push_front(x);
	
	int distance = hdx.back() - hdx.front();
	table[distance]++; bucket[distance/SIZE_PER_BUCKET]++;
}

void _Sub(int x, int fb){
	auto &hdx = hatidx[arr[x]];
	
	int distance = hdx.back() - hdx.front();
	table[distance]--; bucket[distance/SIZE_PER_BUCKET]--;
	
	if (fb == 1) hdx.pop_back();
	else hdx.pop_front();
	
	if (!hdx.empty()){ //7 ... 7 ... [7]
		int ndis = hdx.back() - hdx.front();
		table[ndis]++; bucket[ndis/SIZE_PER_BUCKET]++;
	}
}

int calculateMD(){
	for (int i = BUCKET_SIZE-1; i >= 0; i--){
		if (bucket[i] != 0){
			for (int j = SIZE_PER_BUCKET-1; j >= 0; j--){
				if (table[i * SIZE_PER_BUCKET + j] > 0) 
					return i * SIZE_PER_BUCKET + j;
			}
		}
	}
	/*debug << "DEBUG" << endl;
	for (int i = 0; i < BUCKET_SIZE; i++){
		debug << bucket[i];
	}
	debug << endl;*/
	return 0;
}

int main(void){
	FASTIO;
	hatidx.resize(101100);
	cin >> N >> K;
	for (int i = 1; i <= N; i++){
		int t; cin >> t;
		arr[i] = t;
	}
	
	int M; cin >> M;
	for (int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		q.push_back({a, b, i});
	}
	sort(q.begin(), q.end(), _cmp);
	
	int lp = q[0].l, rp = q[0].r;
	for (int i = lp; i <= rp; i++){
		_Add(i, 1);
	}
	ans[q[0].idx] = calculateMD();
	
	for (int i = 1; i < M; i++){
		int l = q[i].l, r = q[i].r;
		int idx = q[i].idx;
		//debug << "for excute" << endl;
		
		
		while (rp < r) _Add(++rp, 1);
		while (l < lp) _Add(--lp, 0);
		while (rp > r) _Sub(rp--, 1);
		while (l > lp) _Sub(lp++, 0);
		
		//debug << "Max Distance : " << MD << endl;
		ans[idx] = calculateMD();
	}
	
	for (int i = 0; i < M; i++){
		cout << ans[i] << endl;
	}
	
	
}