BOJ 8217번 유성

문제 링크

\(1\le{N, M, K}\le{300,000}\)

\(1\le{a_i, p_i}\le{10^9}\)

M개의 구역이 있다. 각각의 구역은 N개의 국가중 하나에 의해 소유된다. 

N개의 국가는 각자 pi개의 운석 샘플을 가져가야 한다.

유성이 K번 떨어진다. 유성이 한번 떨어질 때에는 특정 연속된 구간에 특정량이 떨어진다.

li, ri, ai 로 표현될 수 있으며 구역은 원형이므로 li > ri 일 수도 있음에 유의한다. 

유성이 어떤 국가에 속한 구역에 떨어지면 그 떨어진 개수만큼 해당 국가는 샘플을 습득할 수 있는 것이다.

그렇다면 각 국가가 필요로 하는 샘플의 개수를 처음으로 충족하게 되는 건 몇 번째 유성이

떨어졌을 때인지 구하는 문제이다. 즉, 답은 N개의 정수를 출력해야한다.

naive 하게 생각해보면 각각의 국가에 대해 이분탐색을 하면서 운석이 떨어지는건 레이지 세그트리로

생각해볼 수가 있다. 그럼 시간복잡도가 O(NM(lgM)(lgK)) 이다. 그런데 어차피 포인트 쿼리만 사용할 것이므로

(어차피 각 국가가 소유하는 구역들은 연속적이지 않고 임의기 때문에 각각 포인트쿼리를 날려서 더할수밖에없다.)

레이지 대신 BIT 의 range update, point query 를 이용해보자. 그럼 복잡도가 아마 O(NMlgK) 까진 줄것이다.

그런데 이정도론 택도없다. 그럼 어떻게 할까? 답은 패러럴 바이너리 서치(parallel binary search) 이다. 

자세한 설명은 생략한다. 이렇게 하면 복잡도가 O((KlgM + N + MlgM)lgK) (?) 가 된다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
struct query{
    int l, r, a;
};
int N, M, K;
ll tr[300003];
int lo[300003], hi[300003];
int need[300003];
query Q[300003];
vector<int> qry[300003];
vector<int> terr[300003];
void update(int pos, int val){
    while(pos <= M){
        tr[pos] += val;
        pos += pos & -pos;
    }
}
ll query(int pos){
    ll ret = 0;
    while(pos > 0){
        ret += tr[pos];
        pos -= pos & -pos;
    }
    return ret;
}
 
int main() {
    fastio();
    cin >> N >> M;
    for(int i = 1 ; i <= M; i++){
        int a;
        cin >> a;
        terr[a].pb(i);
    }
    for(int i = 1 ; i <= N; i++) cin >> need[i];
    cin >> K;
    for(int i = 1 ; i <= K; i++){
        int l, r, a;
        cin >> l >> r >> a;
        Q[i] = {l, r, a};
    }
    for(int i = 1; i <= N; i++) lo[i] = 1, hi[i] = K + 1;
    while(1){
        int isEnd = 1;
        for(int i = 1 ; i <= N; i++) {
            if(lo[i] < hi[i]) {
                isEnd = 0;
                int mid = (lo[i] + hi[i]) / 2;
                qry[mid].pb(i);
            }
        }
        if(isEnd) break;
        memset(tr,0,sizeof(tr));
        for(int i = 1; i <= K; i++){
            auto q = Q[i];
            if(q.l > q.r) {
                update(q.l, q.a);
                update(1, q.a);
                update(q.r + 1, -q.a);
            }
            else{
                update(q.l, q.a);
                update(q.r + 1, -q.a);
            }
            while(sz(qry[i])){
                int id = qry[i].back();
                qry[i].pop_back();
                ll sum = 0;
                for(int nd : terr[id]) {
                    sum += query(nd);
                    if(sum >= need[id]) break;
                }
                if(sum >= need[id]) hi[id] = i;
                else lo[id] = i + 1;
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        if(lo[i] == K + 1) cout << "NIE\n";
        else cout << lo[i] << '\n';
    }
    return 0;
}