수열과 쿼리 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;
}
}