BOJ 13545 | 수열과 쿼리 0

수열과 쿼리 4를 풀었다면 날먹이 가능하다는 글을 읽고 도전해 보았다.

우선, [i~j]의 합은 계산해 놓은 누적합 배열이 psum이라고 할 때 psum[j] - psum[i-1]이다.

이 합이 0이려면 psum[i-1] = psum[j] 이면 되는 것이다.

따라서 같은 값의 최대 거리를 찾는 수열과 쿼리 4 문제를 이용해서 arr 대신 psum으로 계산하면 된다.

여기까지는 의식의 흐름대로 왔는데 계속 OutofBound가 나서 잠깐 당황했다.

psum 배열 크기를 1,000,000까지 늘렸는데도 계속 OutofBound가 나길래 왜이러지 하고 생각하다가 이 문제에서 누적합은 최소 -100,000에서 최대 100,000까지 가능하다는 걸 깨달았다.

psum을 그대로 쓰려면 cnt[psum]에서 마이너스 값 때문에 OutofBound가 나기 때문에 psum의 모든 값에 일정치를 더해서 전부 플러스로 바꿔주어야 한다.

다행히 우리는 psum[i]의 값이 같은지만 관심이 있기 때문에 얼마를 더하든 문제가 없다.

누적합과 마이너스 값 두개만 눈치챈다면 수열과 쿼리 4를 푼 시점에서 어렵지 않게 해결이 가능할 것이다.

#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[1001100];
lint table[1001100];
vector<list<int>> hatidx;

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

const int SIZE_PER_BUCKET = 300;
const int BUCKET_SIZE = 1111111 / 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(1001100);
	cin >> N;
    lint sum = 0;
    arr[0] = 0;
	for (int i = 1; i <= N; i++){
		int t; cin >> t;
        sum += t;
		arr[i] = sum;
	}
    for (int i = 0; i <= N; i++){
        arr[i] += 100010;
    }
	
	int M; cin >> M;
	for (int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		q.push_back({a-1, 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;
	}
	
	
}