수열과 쿼리 7 (백준 13550)

안녕하세요. 오늘은 합의 배수를 찾을 거예요.

문제

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

아이디어

이 문제는 수열과 쿼리 4와 비슷합니다.
A1부터 A_i까지의 합을 S_i라고 하면
S_i- S(j-1)은 K로 나눈 나머지가 0이여야하고
그러면 Si와 S(j-1)은 K로 나눈 나머지가 같아야 합니다.
그러므로 수열과 쿼리 4를 arr값이 아닌 sum값 %K한 값으로 계산을 해주면 정답을 받을 수 있습니다.
수열과 쿼리 0과도 비슷합니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <deque>
#include <list>
#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;
}

list <ll> dq[1010101];
ll cnt[101010] = { 0 }, bucket[1010] = { 0 };
ll arr[101010] = { 0 }, sum[101010] = { 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 K, i, Q, a, b;
    vector <pair <pair <ll, ll>, ll> > v;

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

    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";
}

감사합니다.