2426번: 세계적인 석유 재벌

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


$O((n+m)\lg n)$

a[i]: i번째로 큰 나무의 높이
이제 필요한 연산은
1. a[i]의 정렬상태를 유지시키며 a[j]>=h인 작은 나무부터 c개 1씩 증가
2. mini<=a[i]<=maxi 인 i개수 출력
이 모든 연산은 펜윅트리로 가능하다.

1번만 대충 살펴보면,
펜윅트리에서 O(lgn)에 돌아가는 lower_bound를 구현해서 처리할 수 있다.
111122223333
이렇게 있고 h=1, c=10인 쿼리가 들어오면
(11112222)는 1씩 증가시키고
(3333)은 뒤에서부터 나머지 2개를 1씩 증가시킨다.
그러면 222233333344

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, bit[MXN + 1], a[MXN + 1], sz;
void update(int h, int x) {
    for (; h <= n; h += h&-h) bit[h] += x;
}
int query(int h) {
    int s = 0;
    for (; h; h -= h&-h) s += bit[h];
    return s;
}
int idx(int h) {
    int p = 0;
    for (int i = sz / 2; i; i /= 2) if (p + i <= n&&h > bit[p + i]) h -= bit[p += i];
    return p + 1;
}
int main() {
    scanf("%d %d", &n, &m);
    for (sz = 1; sz < n; sz *= 2);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a, a + 1 + n);
    for (int i = 1; i <= n; i++) update(i, a[i] - a[i - 1]);
    char c;
    int a, b;
    while (m--) {
        scanf(" %c%d%d", &c, &a, &b);
        if (c == 'F') {
            int p1, p2, p3, q;
            p1 = idx(b);
            a = min(a, n + 1 - p1);
            q = query(p1 + a - 1);
            p2 = idx(q);
            p3 = idx(q + 1);
            update(p1, 1); update(p2, -1);
            update(p3 + p2 - p1 - a, 1); update(p3, -1);
        }
        else printf("%d\n", idx(b + 1) - idx(a));
    }
    return 0;
}