수열과 쿼리 4 (백준 13546)

안녕하세요. 오늘은 수열과 쿼리 4 문제를 풀어볼 거예요.

문제

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

아이디어

기본적인 아이디어는 mo's입니다.
그런데 여기서 더 추가해야하는게 있습니다.

덱을 만들어서 dq[x]에는 x가 있는 인덱스 (지금 쿼리에서 포함하고 있는)를 오름차순으로 넣습니다. 그리고 back-front를 하면 x끼리의 거리의 최댓값이 구해집니다. 하지만 수는 10만개이기 때문에 모든 쿼리마다 모든 x를 볼 수는 없습니다. 그래서 이 덱의 back-front값의 범위가 0부터 N이라는 점에서 이 값을 가지고 제곱근분할법을 하면 됩니다.

소스코드

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

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

    ll now = dq[arr[idx]].back() - dq[arr[idx]].front();
    cnt[now]++;
    bucket[now / sqrt_N]++;
}
void MINUS(ll idx, ll dir)
{
    ll now = dq[arr[idx]].back() - dq[arr[idx]].front();
    cnt[now]--;
    bucket[now / sqrt_N]--;
    if (dir == 1) dq[arr[idx]].pop_back();
    else dq[arr[idx]].pop_front();
    if (dq[arr[idx]].size())
    {
        ll now = dq[arr[idx]].back() - dq[arr[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;
    cin >> N >> K; sqrt_N = sqrt(N);
    for (i = 1; i <= N; i++) cin >> arr[i];

    ll Q, a, b;
    vector <pair <pair <ll, ll>, ll> > v;
    cin >> Q;
    for (i = 1; i <= Q; i++)
    {
        cin >> a >> b;
        v.push_back({ { a,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 (e < temp.second) PLUS(++e, 1);
        while (e > temp.second) MINUS(e--, 1);
        while (s < temp.first) MINUS(s++, -1);
        while (s > temp.first) PLUS(--s, -1);
        Ans[v[i].second] = find();
    }

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

감사합니다.