수열과 쿼리 0 (백준 13545)

안녕하세요. 오늘은 누적합을 구해볼 거예요.

문제

https://www.acmicpc.net/problem/13545

아이디어

Ai부터 Aj까지의 합 (i<=j)이 0이라는 것은 A_0부터 A_i-1까지의 합과 A_0부터 A_j까지의 합이 같다는것을 의미합니다. 그래서 수열과 쿼리 4 문제에서 두 값이 같고 인덱스의 차이의 최댓값을 구한것에서 값이 같은것이 아니라 sum이 같은것으로 코드를 바꾸면 됩니다. 또한 입력으로 (a,b)가 주어졌어도 같으려면 a-1부터 b까지를 보아야합니다.

이때 주의할 점은 mo's를 할 때 범위를 늘리는것을 먼저 해야합니다. 그렇지 않으면 이상한 런타임 에러가 납니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <deque>
#define ll long long
using namespace std;

ll N, sqrt_N;
bool cmp(pair <pair <ll, ll>, ll> A, pair <pair <ll, ll>, ll> B)
{
    if (A.first.first / sqrt_N != B.first.first / sqrt_N) return A.first.first < B.first.first;
    return A.first.second < B.first.second;
}

deque <ll> dq[202020];
ll cnt[202020] = { 0 }, bucket[202020] = { 0 }; 
ll arr[202020] = { 0 }, sum[202020] = { 0 };
void PLUS(ll idx, ll dir)
{
    ll now;
    if (dq[sum[idx]].size())
    {
        now = dq[sum[idx]].back() - dq[sum[idx]].front();
        cnt[now]--; bucket[now / sqrt_N]--;
    }
    if (dir == 1) dq[sum[idx]].push_back(idx);
    else dq[sum[idx]].push_front(idx);

    now = dq[sum[idx]].back() - dq[sum[idx]].front();
    cnt[now]++; bucket[now / sqrt_N]++;
}
void MINUS(ll idx, ll dir)
{
    ll now;

    now = dq[sum[idx]].back() - dq[sum[idx]].front();
    cnt[now]--; bucket[now / sqrt_N]--;

    if (dir == 1) dq[sum[idx]].pop_back();
    else dq[sum[idx]].pop_front();
    if (dq[sum[idx]].size())
    {
        now = dq[sum[idx]].back() - dq[sum[idx]].front();
        cnt[now]++; bucket[now / sqrt_N]++;
    }
}
ll find()
{
    ll i, j;
    for (i = N / sqrt_N; i >= 0; i--)
    {
        if (bucket[i] == 0) continue;
        for (j = (i + 1) * sqrt_N - 1; j >= i * sqrt_N; j--)
        {
            if (cnt[j] == 0) continue;
            return j;
        }
    }   
}

ll Ans[101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll i, Q, a, b;
    vector <pair <pair <ll,ll>, ll> > v;

    cin >> N; sqrt_N = sqrt(N);
    sum[0] = 100000;
    for (i = 1; i <= N; i++)
    {
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }

    cin >> Q;
    for (i = 1; i <= Q; i++)
    {
        cin >> a >> b;
        v.push_back({ {a - 1,b},i });
    }
    sort(v.begin(), v.end(), cmp);

    ll s = 0, e = 0; PLUS(0, 1);
    for (i = 0; i < Q; i++)
    {
        pair <ll, ll> temp = v[i].first;
        while (s > temp.first) PLUS(--s, -1);
        while (e < temp.second) PLUS(++e, 1);
        while (s < temp.first) MINUS(s++, -1);
        while (e > temp.second) MINUS(e--, 1);

        Ans[v[i].second] = find();
    }

    for (i = 1; i <= Q; i++)
        cout << Ans[i] << "\n";
}

감사합니다.