나무는 쿼리를 싫어해~ (백준 20212)

안녕하세요. 오늘은 좀 많이 이상한 쿼리를 해볼거예요.

문제

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

아이디어

가장 먼저 떠올릴 수 있는 아이디어는 그냥 값/좌표 압축으로 최대 10만개 (5만개의 쿼리에서 각 최대 2개씩 나오므로)의 값만 가지고 느리게 갱신되는 세그먼트 트리를 쓰면 된다고 생각할 수 있습니다. 하지만 여기서 문제가 하나 있습니다. 바로 그 사이에 있는 값이죠.

만약 원래 문제에서 구간 [3,5]에 2를 더하라고 하면 전체적으로 3, 4, 5에 2씩 더해져서 총 6이 더해져야 합니다. 하지만 값 압축이 되면 3과 5는 인접할 확률이 높아지므로 2을 더해버리면 3과 5에만 2가 더해져서 4가 더해지는것으로 처리가 됩니다.

그래서 이 문제를 해결하기 위해서는 특별한 방법을 써야합니다.
바로 모든 값을 관리하는 것입니다. 하지만 당연히 10억개를 다 관리하면 메모리초과가 납니다. 그러므로 값과 구간을 번갈아가면서 배치할 겁니다. 그리고 각 (값 혹은 구간)에 있는 수들의 개수를 가중치로 삼아서 더할때 곱해서 더해주면 됩니다. 구간도 하나의 인덱스로 취급하는데 하나의 인덱스에 0개부터 10억개까지 다양한 개수의 값들이 있을 수 있는 것이죠. 그러므로 당연히 더해줄 때에도 그 개수만큼 더해주어야합니다.

간단히 학생과 반을 막 모아서 나열한다고 생각해봅시다. 반 하나랑 학생 한명을 똑같이 하나의 세트로 취급하는 것입니다. 이때 일련의 학생들에게 밥을 나눠준다고 하면 겉에서 봤을때에는 학생 몇명과 반 몇개가 밥을 받았지만 사실 받아야하는 밥은 전체 학생 수, 즉 (학생 한명)의 개수 + (모든 반에 있는 학생의 수의 합)이 필요한 것입니다.

만약 수들이 {1,4,6,9,10,11,13,19}가 있다고 해봅시다. 압축을 하면 {1,2,3,4,5,6,7,8}이 됩니다. 그런데 이때 각 수들 사이에 또다른 수가 있으므로 사실은 {1,[2,3],4,[5,5],6,[7,8],9,[?],10,[?],11,[12,12],13,[14,18],19)가 됩니다. 압축을 하면 {1,2,3,4...,15}가 됩니다. 이때 각 인덱스에 들어가있는 값의 개수를 세어보면 {1,2,1,1,1,2,1,0,1,0,1,1,1,5,1}이 됩니다. 이 값이 가중치가 됩니다.

이제 더해주면 됩니다. 만약 구간 [4,11]이면 위의 값에서 인덱스 3부터 인덱스 11까지 더하는것과 같습니다. 그러면 각 구간에 있는 수들의 개수(가중치) 가 {1,1,1,2,1,0,1,0,1}이 됩니다. 그러므로 각 인덱스에 더하는 수를 그대로 더하는것이 아니라 가중치를 곱해서 더해주어야 합니다. 그러면 모든 쿼리를 처리할 수 있습니다 (k번째 1번쿼리를 처리하는건 오프라인 쿼리로 쉽게할수 있죠?^^)

소스코드

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

ll Gajungchi[202020] = { 0 }, GajungchiTree[808080] = { 0 };
ll tree[808080] = { 0 }, lazy[808080] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return GajungchiTree[node] = Gajungchi[s];
    ll mid = (s + e) / 2;
    return GajungchiTree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
void pp(ll s, ll e, ll node)
{
    if (lazy[node])
    {
        tree[node] += lazy[node] * GajungchiTree[node];
        if (s != e)
        {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    pp(s, e, node);
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll l, ll r, ll value)
{
    pp(s, e, node);
    if (e < l || r < s) return;
    if (l <= s && e <= r)
    {
        lazy[node] += value;
        pp(s, e, node);
        return;
    }
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, l, r, value);
    change(mid + 1, e, node * 2 + 1, l, r, value);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    vector <pair <pair <ll, ll>, pair <ll, ll> > > second_query; //{{k,i},{j,몇번째 2번쿼리인지}}
    vector <pair <pair <ll, ll>, ll> > first_query; //{{i,j},k}
    first_query.push_back({ {0,0},0 }); //인덱스는 1부터 시작하도록 맞춰주기
    vector <ll> nums;

    ll N, i, type, a, b, c, SecondQueryNum = 0;
    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> type >> a >> b >> c;
        if (type == 1) first_query.push_back({ {a,b},c });
        else second_query.push_back({ {c,a},{b,++SecondQueryNum} });
        nums.push_back(a); nums.push_back(b);
    }
    sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); ll NumSize = nums.size();
    sort(second_query.begin(), second_query.end());

    for (i = 1; i <= NumSize * 2 - 1; i++)
    {
        if (i % 2 == 1) Gajungchi[i] = 1;
        else Gajungchi[i] = nums[i / 2] - nums[i / 2 - 1] - 1;
    }
    init(1, 200000, 1);

    ll FirstQueryNum = first_query.size() - 1; //첫번째거는 {{0,0},0}이므로 세지 않음
    ll j = 0, Ans[50505] = { 0 };
    for (i = 1; i <= FirstQueryNum; i++)
    {
        a = first_query[i].first.first; a = lower_bound(nums.begin(), nums.end(), a) - nums.begin();
        b = first_query[i].first.second; b = lower_bound(nums.begin(), nums.end(), b) - nums.begin();
        c = first_query[i].second;
        change(1, 200000, 1, a * 2 + 1, b * 2 + 1, c);

        while (j < SecondQueryNum && second_query[j].first.first == i)
        {
            a = second_query[j].first.second; a = lower_bound(nums.begin(), nums.end(), a) - nums.begin();
            b = second_query[j].second.first; b = lower_bound(nums.begin(), nums.end(), b) - nums.begin();
            Ans[second_query[j].second.second] = SUM(1, 200000, 1, a * 2 + 1, b * 2 + 1); 
            j++;
        }
    }

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

감사합니다.