BOJ 8217 유성

유성
(http://boj.kr/8217)

이 문제는 고민을 해봐도 모르겠어서 안 풀려 했는데, 방법을 알아두면 좋을 것 같아서 풀이를 봤다.

일단 기본적으로 구간 업데이트를 펜윅트리로 \(O(\log{n})\)만에 하는 방법은 알고 있어야 한다.
회원국별로 날짜를 이분탐색으로 찾으려고 해도, 그 날에 유성의 개수를 확인하려면 미리 저장해둘 수는 없기 때문에 \(O(k\log{m})\)으로 매번 트리를 만들어야 한다.
그래서 아이디어가 하나 더 들어가서, 어떤 날의 트리를 최대한 활용해야 한다.
그러기 위해 모든 회원국이 하는 이분탐색을 동시에 한다. 즉, 트리가 저장하고 있는 날짜 별로, 그 날에 가능한지 확인해야 하는 회원국들을 같이 확인해주면 된다. 이때 총합이 long long 범위도 넘어갈 수 있다는 것에 주의해야 한다.

이 방법을 사용하면 어쨌든 모든 회원국은 \(\log{k}\)일을 확인해야 하고, 한 번 확인할 때마다 트리의 상태를 \(k\)일 갱신해줘야 하고, 업데이트를 하는데 \(O(\log{m})\)정도 걸리니까 총 시간복잡도는 \(O(k\log{k}\log{m})\)정도 되는 것 같다.

싸리와 버드의 피라미드문제도 그렇고, 같이 할 수 있는 것들을 묶어서 한다는 것이 중요한 것 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> are[300001], can[300001];
long long tar[300001];
int q1[300001], q2[300001], lef[300001], rig[300001], ans[300001];
long long q3[300001], tree[300001];
 
int main() {
    int n, m, u, q;
    scanf("%d %d", &n, &m);
    for (int i = 1;i <= m;++i) {
        scanf("%d", &u);
        are[u].push_back(i);
    }
    for (int i = 1;i <= n;++i) 
        scanf("%lld", &tar[i]);
    scanf("%d", &q);
    for (int i = 1;i <= n;++i) {
        lef[i] = 1;
        rig[i] = q;
        ans[i] = q + 1;
    }
    for (int i = 1;i <= q;++i)
        scanf("%d %d %lld", &q1[i], &q2[i], &q3[i]);
 
    while (true) {
        bool c = false;
        for (int i = 1;i <= n;++i)
            if (lef[i] <= rig[i]) {
                c = true;
                can[(lef[i] + rig[i]) / 2].push_back(i);
            }
        if (!c)
            break;
 
        memset(tree, 0, sizeof(tree));
        for (int i = 1;i <= q;++i) {
            if (q1[i] <= q2[i]) {
                for (int x = q1[i];x <= m;x += x & -x)
                    tree[x] += q3[i];
                for (int x = q2[i] + 1;x <= m;x += x & -x)
                    tree[x] -= q3[i];
            }
            else {
                for (int x = q1[i];x <= m;x += x & -x)
                    tree[x] += q3[i];
                for (int x = 1;x <= m;x += x & -x)
                    tree[x] += q3[i];
                for (int x = q2[i] + 1;x <= m;x += x & -x)
                    tree[x] -= q3[i];
            }
 
            while (!can[i].empty()) {
                c = true;
                int now = can[i].back();
                can[i].pop_back();
                
                long long tot = 0;
                for (int beh : are[now]) {
                    for (int x = beh;x > 0; x -= x & -x)
                        tot += tree[x];
                    if (tot >= tar[now])
                        break;
                }
 
 
                if (tot >= tar[now]) {
                    ans[now] = min(ans[now], i);
                    rig[now] = i - 1;
                }
                else
                    lef[now] = i + 1;
            }
        }
    }
 
    for (int i = 1;i <= n;++i) {
        if (ans[i] == q + 1)
            printf("NIE\n");
        else
            printf("%d\n", ans[i]);
    }
 
    return 0;
}