BOJ 13550 | 수열과 쿼리 7

수열과 쿼리 0과 완전히 같은 문제이다.

다만 수열과 쿼리 0은 마이너스 값까지 신경써야 했다면 이 문제는 그런 게 없는 대신 (psum[j] - psum[i-1]) % K == 0을 찾는 것이므로 모든 psum 값에 mod K 를 해 주어야 한다.

2 <= K <= 1,000,000 이므로 배열 크기만 맞춰준다면 수열과 쿼리 0을 푼 시점에서 정말 어렵지 않게 통과할 수 있다.

#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 = 900;
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 >> K;
    lint sum = 0;
    arr[0] = 0;
	for (int i = 1; i <= N; i++){
		int t; cin >> t;
        sum += t;
		sum %= K;
		arr[i] = sum;
	}
	
	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;
	}
	
	
}