백준 23592 Reactor

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

 

구간에 값을 더하는 쿼리이니 세그를 쓰고 싶다는 생각이 든다. 쿼리를 처리하며 vent되는 횟수를 세어야 하는데, vent될 때마다 $p_i$는 절반으로 줄어든다. 따라서 $p_i = 1$인 경우를 제외하면 vent되는 총 횟수는 최대 $O(N\log X)$ 정도이니 vent는 발생할 때마다 나이브하게 처리하되 $p_i = 1$인 경우만 묶어서 잘 처리하면 될 것 같다. 즉, 아래 두 작업을 수행할 수 있다면 문제를 풀 수 있다.

 

1. 쿼리 후 $p_i \ne 1$이면서 vent된 인덱스 중 하나를 빠르게 찾기

2. 쿼리 후 구간에서 $p_i = 1$인 인덱스에 대해서 카운트 1 증가시키기

 

1번 작업에서, vent된 인덱스가 구간의 최솟값이 되도록 더하기 쿼리를 빼기 쿼리로 바꾸자. 수열의 초깃값을 $p_i$로 두고 구간에서 $k$를 뺀다고 생각하면 쿼리 이후 값이 0 이하인지 여부로 vent되었는지 확인할 수 있다. 사탕상자처럼 구간의 최솟값은 $O(\log N)$에 찾아갈 수 있으니 $p_i \ne 1$인 케이스는 총 $O(Q \log^2 N)$에 처리할 수 있다. 최솟값을 찾아가는 과정에서 방문하는 노드의 lazy를 먼저 push해주면 $p_i$를 점 쿼리 처리하듯 변경해도 된다. 이때 $p_i$의 다음 값이 1이라면 2번 작업에서 처리할 것이니 1번 작업에서 다시 vent처리되지 않을 만큼 큰 수 inf로 변경하자.

 

2번 작업을 처리하기 위해 구간에서 $p_i = 1$인 인덱스 수를 관리하자. 목표는 세그의 각 노드가 담당하는 구간에서 $p_i=1$인 인덱스에 vent가 발생한 횟수를 관리하는 것이다. 구체적으로, 다음 세 가지를 처리해야 한다.

 

2-1. 구간에 속한 1들에만 카운트 1 증가

2-2. 구간의 카운트 횟수 구하기

2-3. 특정 인덱스에 1 추가하기

 

구간의 1 개수를 관리하면 구간 증가 쿼리에서는 구간에서 관리하는 값에 1 개수를 더해주는 식으로 lazy세그를 구성하여 처리할 수 있다. 특정 인덱스에 1을 추가할 때는 인덱스까지 내려가며 만나는 노드의 lazy를 먼저 push해준 뒤 아래에서부터 구간의 1 개수를 업데이트하면 꼬이지 않는다. 

 

어렵긴 한데 D3까지 갈 정도인지는 모르겠다. 체감상 https://www.acmicpc.net/problem/10070랑 비슷한 것 같다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll p[202020], seg[202020 << 2], lazy[202020 << 2], ans[202020], cnt[202020 << 2], lazy_cnt[202020 << 2], one[202020 << 2], N, Q;
 
void init(int now, int l, int r){
    if (l == r) {
        seg[now] = p[l];
        return;
    }
    int m = l+r >> 1;
    init(now*2, l, m);
    init(now*2+1, m+1, r);
    seg[now] = min(seg[now*2], seg[now*2+1]);
}
 
void push(int now, int l, int r){
    seg[now] -= lazy[now];
    if (l != r){
        lazy[now*2] += lazy[now];
        lazy[now*2+1] += lazy[now];
    }
    lazy[now] = 0;
}
void update(int now, int l, int r, int s, int e, int x){
    push(now, l, r);
    if (e < l or r < s) return;
    if (s <= l and r <= e){
        lazy[now] = x;
        push(now, l, r);
        return;
    }
    int m = l+r >> 1;
    update(now*2, l, m, s, e, x);
    update(now*2+1, m+1, r, s, e, x);
    seg[now] = min(seg[now*2], seg[now*2+1]);
}
 
void inc(int i){
    for (; i <= N; i += i & -i)
        ans[i]++;
}
 
void push_cnt(int now, int l, int r){
    cnt[now] += lazy_cnt[now] * one[now];
    if (l != r){
        lazy_cnt[now*2] += lazy_cnt[now];
        lazy_cnt[now*2+1] += lazy_cnt[now];
    }
    lazy_cnt[now] = 0;
}
void add_one(int now, int l, int r, int i){
    push_cnt(now, l, r);
    one[now]++;
    if (l == r) return;
    int m = l+r >> 1;
    if (i <= m) add_one(now*2,l,m,i);
    else add_one(now*2+1,m+1,r,i);
}
void update_cnt(int now, int l, int r, int s, int e){
    push_cnt(now, l, r);
    if (e < l or r < s) return;
    if (s <= l and r <= e) {
        lazy_cnt[now] = 1;
        push_cnt(now, l, r);
        return;
    }
    int m = l+r >> 1;
    update_cnt(now*2, l, m, s, e);
    update_cnt(now*2+1, m+1, r, s, e);
    cnt[now] = cnt[now*2] + cnt[now*2+1];
}
ll query_cnt(int now, int l, int r, int s, int e){
    push_cnt(now, l, r);
    if (e < l or r < s) return 0;
    if (s <= l and r <= e) return cnt[now];
    int m = l+r >> 1;
    return query_cnt(now*2, l, m, s, e) + query_cnt(now*2+1, m+1, r, s, e);
}
 
void go(int now, int l, int r){
    // cout << "go: " << now << ' ' << l << ' ' << r << endl;
    if (l == r){
        inc(l);
        p[l] /= 2;
        if (p[l] == 1) {
            p[l] = 1e18;
            add_one(1,1,N,l);
        }
        seg[now] = p[l];
        // cout << "update: " <<l << ' ' << seg[now] << endl;
        return;
    }
    int m = l+r >> 1;
    push(now*2, l, m);
    push(now*2+1, m+1, r);
    // cout << now << ' ' << l << ' ' << r << ' ' << m << ' ' << seg[now] << ' ' << seg[now*2] << ' ' << seg[now*2+1] << endl;
    if (seg[now*2] <= 0) go(now*2, l, m);
    else go(now*2+1, m+1, r);
    seg[now] = min(seg[now*2], seg[now*2+1]);
    // cout << now << ' ' << l << ' ' << r << ' ' << seg[now] << ' ' << seg[now*2] << ' ' << seg[now*2+1] << endl;
}
 
int query(int i){
    int ret = 0;
    for (; i; i -= i & -i)
        ret += ans[i];
    return ret;
}
int query(int l, int r){
    return query(r) - query(l-1);
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> p[i];
        if (p[i] == 1){
            add_one(1,1,N,i);
            p[i] = 1e18;
        }
    }
    init(1,1,N);
    while (Q--){
        int op, l, r, k;
        cin >> op >> l >> r;
        if (op == 1){
            cin >> k;
            update(1,1,N,l,r,k);
            update_cnt(1,1,N,l,r);
            int sibal = 0;
            while (seg[1] <= 0) 
                go(1,1,N);
        }
        else cout << query(l, r) + query_cnt(1,1,N,l,r) << '\n';
    }
}