5419번: North-Western Winds

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


$O(tn\lg n)$

x축 정렬하고 보면 y 성분 값이 감소하거나 같은 쌍의 개수를 구하는 문제가 된다.
fenwick tree를 이용해서 해결한다.

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int MXN = 75e3;
int t, n, sz, bit[MXN + 1];
pair<int, int> p[MXN];
int main() {
    for (scanf("%d", &t); t--;) {
        map<int, int> mp;
        long long r = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second), mp[p[i].second *= -1] = 0;
        sort(p, p + n);
        sz = 0;
        for (auto &it : mp) it.second = ++sz, bit[sz] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = mp[p[i].second]; j; j -= j&-j) r += bit[j];
            for (int j = mp[p[i].second]; j <= sz; j += j&-j) bit[j]++;
        }
        printf("%lld\n", r);
    }
    return 0;
}

8889번: 등고선 지도

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


$O(tmn\lg (mn))$

다각형을 이루는 x축과 평행한 선분들 중 아래는 +1 위는 -1로 표시하자.
그러면 어떤 점에서 아래로 가며 지나친 선분들의 값을 누적하면 그 점의 레벨을 알 수 있다.
모든 다각형에 대해 가장 왼쪽 아래의 점들을 배열에 저장하고 x를 기준으로 오름차순 정렬해놓는다.
주어진 선분들을 왼쪽에서 오른쪽으로 스위핑하면서 펜윅트리를 이용해 해당 점들 아래의 누적값을 구하여 최대 레벨을 구한다.

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int MXM = 2e4, MXK = 1e2;
struct st {
    int x, y, c;
}sg[MXM*MXK];
int t, n, m, sz, my, bit[MXM*MXK / 2 + 1];
pair<int, int> p[MXK], q[MXM];
int main() {
    for (scanf("%d", &t); t--;) {
        sz = my = 0;
        scanf("%d", &m);
        map<int, int> mp;
        for (int i = 0; i < m; i++) {
            scanf("%d", &n);
            for (int j = 0; j < n; j++) scanf("%d%d", &p[j].first, &p[j].second), mp[p[j].second] = 0;
            int tp = min_element(p, p + n) - p;
            q[i] = p[tp];
            int j = tp;
            do {
                sg[sz++] = { p[j].first,p[j].second,1 };
                sg[sz++] = { p[(j + 1) % n].first,p[(j + 1) % n].second,-1 };
                j = (j + 2) % n;
            } while (tp^j);
        }
        for (auto &it : mp) it.second = ++my;
        fill(bit + 1, bit + 1 + my, 0);
        sort(sg, sg + sz, [](st i, st j) {return i.x < j.x; });
        sort(q, q + m);
        int res = 0;
        for (int i = 0, j = 0; i < m; i++) {
            for (; j < sz&&sg[j].x <= q[i].first; j++)
                for (int k = mp[sg[j].y]; k <= my; k += k&-k) bit[k] += sg[j].c;
            int s = 0;
            for (int k = mp[q[i].second]; k; k -= k&-k) s += bit[k];
            res = max(res, s);
        }
        printf("%d\n", res);
    }
    return 0;
}

12016번: 라운드 로빈 스케줄러

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


$O(n\lg n)$

작업 수행 시간이 작은 것부터 보면서 진행중인 작업 개수*반복 횟수를 누적한다.
마지막으로 작업을 수행할 때 0번부터 해당 작업 사이 진행할 작업 개수는 bit를 이용해 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int bit[MXN + 1], n;
long long r[MXN], c[MXN + 1], s;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", c + i), c[i] = c[i] * n + i - 1;
    sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++) {
        int h = c[i] % n;
        r[h] = (s += (c[i] / n - c[i - 1] / n)*(n - i + 1)) - n + i + h;
        for (int j = h + 1; j; j -= j&-j) r[h] -= bit[j];
        for (int j = h + 1; j <= n; j += j&-j) bit[j]++;
    }
    for (int i = 0; i < n; i++) printf("%lld\n", r[i]);
    return 0;
}

3653번: 영화 수집

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


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

처음에 아래부터 n, n-1, ..., 2, 1 과 같이 쌓여 있을 것이다. 이후 들어올 쿼리 qi를 누적해서 써보면,
ai: n, n-1, ..., 2, 1, q0, q1, q2 ...
위 수열에서 x 이전의 항중 값이 x인 항의 가장 큰 번호를 f(x) 라 하자.
구하고자 하는 답은 i번째 항과 f(ai)번째 항 사이에 있는 수의 종류와 같음을 알 수 있다.
쿼리 x가 들어올 때마다 f(x)를 이용하여 bit를 업데이트 하는 방식으로 해결할 수 있다.

#include<cstdio>
const int MXN = 1e5;
int t, n, m, a[MXN + 1], bit[MXN * 2 + 1];
void update(int h) {
    for (; h <= n + m; h += h&-h) bit[h]++;
}
int query(int h) {
    int s = 0;
    for (; h; h -= h&-h) s += bit[h];
    return s;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n + m; i++) bit[i] = 0;
        int i = 1, x;
        for (; i <= n; i++) a[i] = n + 1 - i;
        for (; i <= n + m; i++) {
            scanf("%d", &x);
            printf("%d ", i - a[x] - 1 - query(i) + query(a[x]));
            update(a[x]);
            a[x] = i;
        }
        puts("");
    }
    return 0;
}

13556번: 증가하는 부분 수열 2

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

$O(kn\lg n)$

dp[i][j]: 길이 i이고 a[j]로 끝나며 dp[i][1...j-1]에 포함되지 않는 증가 부분 수열 개수
dp[i][j] = sum(k<j, a[k]<a[j])(dp[i-1][k]) - sum(k<j,a[k]=a[j])(dp[i][k])
fenwick tree를 이용한다.

#include<cstdio>
#include<cstring>
#define mod 5000000
int n, k, bit[100001], a[100000], dp[100000], t[100001];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i), dp[i] = !t[a[i]]++;
    for (int i = 2; i <= k; i++) {
        memset(bit, 0, sizeof(bit));
        memset(t, 0, sizeof(t));
        for (int j = 0; j < n; j++) {
            for (int h = a[j]; h <= 1e5; h += h&-h) bit[h] = (bit[h] + dp[j]) % mod;
            dp[j] = mod - t[a[j]];
            for (int h = a[j] - 1; h; h -= h&-h) dp[j] = (dp[j] + bit[h]) % mod;
            t[a[j]] = (t[a[j]] + dp[j]) % mod;
        }
    }
    int s = 0;
    for (int i = 0; i < n; i++) s = (s + dp[i]) % mod;
    printf("%d", s);
    return 0;
}

13555번: 증가하는 부분 수열

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


$O(kn\lg n)$

dp[i][j]: 길이가 i이고 j번째에 끝나는 증가 부분 수열의 개수
dp[i][j]=sum(k<j, a[k]<a[j])(dp[i-1][k])
fenwick tree를 사용한다.

#include<cstdio>
#include<cstring>
#define mod 5000000
int n, k, bit[100001], a[100000], dp[100000];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i), dp[i] = 1;
    for (int i = 2; i <= k; i++) {
        memset(bit, 0, sizeof(bit));
        for (int j = 0; j < n; j++) {
            for (int h = a[j]; h <= 1e5; h += h&-h) bit[h] = (bit[h] + dp[j]) % mod;
            dp[j] = 0;
            for (int h = a[j] - 1; h; h -= h&-h) dp[j] = (dp[j] + bit[h]) % mod;
        }
    }
    int s = 0;
    for (int i = 0; i < n; i++) s = (s + dp[i]) % mod;
    printf("%d", s);
    return 0;
}

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;
}

11591번: VUDU

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


$O(n\lg n)$

s[i]: a[1]+a[2]+...+a[i]

(s[i]-s[j])/(i-j)>=p (j<i) 에서
s[j]-pj<=s[i]-pi

매 i마다 위 조건을 만족하는 j는 펜윅 트리로 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 1e6;
int n, sz, bit[MXN + 2];
ll s[MXN + 1], idx[MXN + 1], p, r;
int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", s + i), s[i] += s[i - 1];
        scanf("%lld", &p);
        for (int i = 0; i <= n; i++) idx[i] = s[i] - i*p;
        sort(idx, idx + 1 + n);
        sz = unique(idx, idx + 1 + n) - idx;
        for (int i = 0; i <= n; i++) {
                int t = lower_bound(idx, idx + sz, s[i] - i*p) - idx + 1;
                for (int h = t; h; h -= h&-h) r += bit[h];
                for (int h = t; h <= sz; h += h&-h) bit[h]++;
        }
        printf("%lld", r);
        return 0;
}

5962번: Generic Cow Protests

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


$O(n\lg n)$

s[i]: 1...i 번째 수들의 합
t[i]: 1...i 번째 수들로 그룹을 짓는 경우의 수
t[i]=sum(s[j]<=s[i])(t[j])
조건을 만족하는 j에 대한 t[j]의 합은 펜윅 트리로 빠르게 구할 수 있다.

#include<cstdio>
#include<algorithm>
#define mod 1000000009
using namespace std;
const int MXN = 1e5;
int idx[MXN + 1], s[MXN + 1], bit[MXN + 2], sz = 1, n, p, t;
void update(int h, int x) {
    for (; h <= sz; h += h&-h) bit[h] = (bit[h] + x) % mod;
}
int query(int h) {
    int s = 0;
    for (; h; h -= h&-h) s = (s + bit[h]) % mod;
    return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", s + i), idx[sz++] = s[i] += s[i - 1];
    sort(idx, idx + sz);
    sz = unique(idx, idx + sz) - idx;
    update(lower_bound(idx, idx + sz, 0) - idx + 1, 1);
    for (int i = 1; i <= n; i++) {
        p = lower_bound(idx, idx + sz, s[i]) - idx + 1;
        t = query(p);
        update(p, t);
    }
    printf("%d", t);
    return 0;
}

11658번: 구간 합 구하기 3

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


$O((n^2+m){\lg n}^2)$

2D 펜윅 트리를 구현한다.

#include<cstdio>
int n, m, mx[1025][1025], bit[1025][1025];
void update(int x, int y, int s) {
    for (; x <= n; x += x&-x)
        for (int j = y; j <= n; j += j&-j) bit[x][j] += s;
}
int sum(int x, int y) {
    int s = 0;
    for (; x; x -= x&-x)
        for (int j = y; j; j -= j&-j) s += bit[x][j];
    return s;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) scanf("%d", mx[i] + j), update(i, j, mx[i][j]);
    for (int i = 0, w, a, b, c, d; i < m; i++) {
        scanf("%d%d%d%d", &w, &a, &b, &c);
        if (w) {
            scanf("%d", &d);
            printf("%d\n", sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1));
        }
        else update(a, b, c - mx[a][b]), mx[a][b] = c;
    }
    return 0;
}

3006번: 터보소트

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

#include<cstdio>
const int MXN = 1e5;
int ubit[MXN + 1], dbit[MXN + 1], r[MXN], idx[MXN + 1], n;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0, p; i < n; i++) {
        if (i & 1) {
            p = idx[n - i / 2];
            r[i] = n - p;
            for (int j = p; j <= n; j += j&-j) r[i] -= ubit[j];
        }
        else {
            p = idx[i / 2 + 1];
            r[i] = p - 1;
            for (int j = p; j; j -= j&-j) r[i] -= dbit[j];
        }
        for (int j = p; j; j -= j&-j) ubit[j]++;
        for (int j = p; j <= n; j += j&-j) dbit[j]++;
    }
    for (int i = 0; i < n; i++) printf("%d\n", r[i]);
    return 0;
}

1517번: 버블 소트

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


$O(n\lg n)$

버블 정렬시 swap 이 일어나는 경우는 i<j 일때 a[i]>a[j]인 경우이다.
이 개수는 bit를 이용해 쉽게 구할 수 있다.

#include<cstdio>
#include<algorithm>
int n, idx, cnt, bit[500001];
long long r, a[500000];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i<n; i++) scanf("%d", a + i), a[i] = a[i] * n + i;
    std::sort(a, a + n);
    for (int i = 0; i<n; i++) {
        for (int j = a[i] % n + 1; j <= n; j += j&-j) r += bit[j];
        for (int j = a[i] % n + 1; j; j -= j&-j) bit[j]++;
    }
    printf("%lld", r);
    return 0;
}

2268번: 수들의 합

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


$O(mlgn)$

bit를 구현한다.

#include<cstdio>
typedef long long lint;
const int MAX_N = 1e6;
int n, m, a[MAX_N + 1];
lint bit[MAX_N + 1];
void f(int x, int y) {
    for (int j = x; j <= n; j += j&-j) bit[j] += y;
}
lint g(int x) {
    lint r = 0;
    for (int j = x; j; j -= j&-j) r += bit[j];
    return r;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        if (x) f(y, z - a[y]), a[y] = z;
        else printf("%lld\n", z>y ? g(z) - g(y - 1) : g(y) - g(z - 1));
    }
    return 0;
}

2820번: 자동차 공장

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


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

노란 책에도 비슷한게 있는 유명한 문제

#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_N = 5e5;
int n, m, d[MAX_N + 1], u[MAX_N + 1], cnt, w[MAX_N + 1], s[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void dfs(int h) {
    d[h] = ++cnt;
    for (auto it : adj[h]) dfs(it);
    u[h] = cnt;
}
void update(int h, int x) { for (; h <= n; h += h&-h) s[h] += x; }
int query(int h) {
    int r = 0;
    for (; h; h -= h&-h) r += s[h];
    return r;
}
int main() {
    scanf("%d %d %d", &n, &m, w + 1);
    for (int i = 2, p; i <= n; i++) scanf("%d %d", w + i, &p), adj[p].push_back(i);
    dfs(1);
    for (int i = 1; i <= n; i++) update(d[i], w[i]), update(d[i] + 1, -w[i]);
    for (int i = 0, a, b; i < m; i++) {
        char c;
        scanf(" %c", &c);
        if (c == 'p') {
            scanf("%d %d", &a, &b);
            update(d[a] + 1, b);
            update(u[a] + 1, -b);
        }
        else {
            scanf("%d", &a);
            printf("%d\n", query(d[a]));
        }
    }
    return 0;
}

7585번: 공장

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


$O(n\lg n)$

아래 기계를 하나씩 추가하되 위쪽에 연결된 기계도 하나씩 추가해보자.
교차점의 개수는 추가하는 기계와 연결되어 있는 위쪽의 기계 뒤에 있는 기계들의 수를 누적한 값이다.
이 문제를 빠르게 해결하기 위해 bit를 사용한다.
처음 위 기계들의 번호를 입력받을 때 순서대로 그 기계 번호에 몇 번째로 입력받은 기계인지 저장해놓는다.
아래 기계들의 번호를 입력받을 때는 해당 기계와 연결된 기계 번호 & bit를 적절히 사용하여 문제를 해결한다.

#include<stdio.h>
const int MAX_N = 5e5, MAX_L = 1e6;
int bit[MAX_N + 1], idx[MAX_L + 1], n;
long long r;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        for (int j = idx[x]; j <= n; j += j&-j) r += bit[j];
        for (int j = idx[x]; j; j -= j&-j) bit[j]++;
    }
    printf("%lld", r);
    return 0;
}

2042번: 구간 합 구하기

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


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

bit를 사용해서 해결하자.
참고로 채점 데이터에 b,c 값이 long long 범위인 경우가 있는 것 같으니 유의하자.

#include<stdio.h>
const int MAX_N = 1e6;
typedef long long ll;
ll bit[MAX_N + 1], a[MAX_N + 1];
int n, m, k;
void update(int h, ll x) {
    for (int i = h; i <= n; i += i&-i) bit[i] += x;
}
ll query(int h) {
    ll r = 0;
    for (int i = h; i; i -= i&-i) r += bit[i];
    return r;
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), update(i, a[i]);
    ll x, y, z;
    for (int i = 0; i < m + k; i++) {
        scanf("%lld %lld %lld", &x, &y, &z);
        if (x == 1) update(y, z - a[y]), a[y] = z;
        else printf("%lld\n", query(z) - query(y - 1));
    }
    return 0;
}