13510번: 트리와 쿼리 1

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

HLD를 구현한다.

시간복잡도는 $O((n+m)\lg n)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int last[100001], idx[100001], cnt[100001], par[100001], tree[400000], c;
int n, m, u[100000], v[100000], w[100000];
vector<int> adj[100001];
void count(int h, int p) {
    for (int it : adj[h]) if (it^p) count(it, h), cnt[h] += cnt[it];
    cnt[h]++;
}
void build(int h, int p) {
    int t = 0;
    for (int it : adj[h]) if (it^p && cnt[t] < cnt[it]) t = it;
    for (int it : adj[h]) if (it^p && it^t) build(it, h);
    if (!last[h]) last[h] = h;
    if (t) last[t] = last[h], build(t, h);
    par[h] = p;
    idx[h] = ++c;
}
void update(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) tree[h] = x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, g, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
        tree[h] = max(tree[h * 2 + 1], tree[h * 2 + 2]);
    }
}
int query(int h, int l, int r, int gl, int gr) {
    if (gr < l || r < gl) return 0;
    if (gl <= l&&r <= gr) return tree[h];
    return max(query(h * 2 + 1, l, (l + r) / 2, gl, gr), query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int lca(int x, int y) {
    int ret = 0;
    while (last[x] ^ last[y]) {
        if (cnt[last[x]] > cnt[last[y]]) swap(x, y);
        ret = max(ret, query(0, 1, n, idx[x], idx[last[x]]));
        x = par[last[x]];
    }
    if (cnt[x] > cnt[y]) swap(x, y);
    return max(ret, query(0, 1, n, idx[x], idx[y] - 1));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", u + i, v + i, w + i);
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    count(1, 0);
    build(1, 0);
    for (int i = 1; i < n; i++) {
        if (par[v[i]] == u[i]) swap(u[i], v[i]);
        update(0, 1, n, idx[u[i]], w[i]);
    }
    scanf("%d", &m);
    for (int i = 0, q, x, y; i < m; i++) {
        scanf("%d%d%d", &q, &x, &y);
        if (q == 1) update(0, 1, n, idx[u[x]], y);
        else printf("%d\n", lca(x, y));
    }
    return 0;
}

4223번: Mummy Madness

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


시간복잡도는 테스트 케이스마다 $O(n\lg L * (\lg L+\lg n))$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 1e6;
struct st {
    int x, l, r, c;
}line[200000];
int n, x[100000], y[100000], len[MX * 8], cnt[MX * 8];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l&&r <= gr) cnt[h] += x;
    else update(h * 2 + 1, l, (l + r) / 2, gl, gr, x), update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    len[h] = cnt[h] ? r - l + 1 : l^r ? len[h * 2 + 1] + len[h * 2 + 2] : 0;
}
bool f(int t) {
    int sz = 0;
    for (int i = 0; i < n; i++) {
        int sx = max(x[i] - t, MX - t), ex = min(x[i] + t, MX + t),
            sy = max(y[i] - t, MX - t), ey = min(y[i] + t, MX + t);
        if (sx > ex || sy > ey) continue;
        line[sz++] = { sx,sy,ey,1 };
        line[sz++] = { ex + 1,sy,ey,-1 };
    }
    sort(line, line + sz, [](st i, st j) {return i.x < j.x; });
    long long area = 0;
    for (int i = 0; i < sz; i++) {
        if (i) area += 1LL * len[0] * (line[i].x - line[i - 1].x);
        update(0, 0, MX * 2 + 1, line[i].l, line[i].r, line[i].c);
    }
    return area < 4LL * t*t + 4 * t + 1;
}
int main() {
    for (int t = 1; scanf("%d", &n), ~n; t++) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", x + i, y + i);
            x[i] += MX;
            y[i] += MX;
        }
        int low = 0, up = MX, mid;
        while (low <= up) {
            mid = (low + up) / 2;
            f(mid) ? low = mid + 1 : up = mid - 1;
        }
        printf("Case %d: ", t);
        low > MX ? puts("never") : printf("%d\n", low);
    }
    return 0;
}

1666번: 최대 증가 직사각형 집합

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


$O(n\lg n)$

시작점과 끝점의 y 성분을 가지고 최댓값을 리턴하는 세그먼트 트리를 만들 것이다.
시작점과 끝점을 x를 기준으로 오름차순 정렬한 다음 앞에서부터 본다. 같은 x 값이면 시작점이 끝점보다 앞서야 한다.
i) 시작점
세그먼트 트리에서 현재 점의 y 좌표보다 작은 구간에 대해 최댓값을 구한다.
해당 값 + 1은 현재 직사각형을 포함하고 현재 점보다 왼쪽 아래에 있는 직사각형들을 포함한 집합 L의 최대 크기가 된다.
이를 따로 저장해놓는다.
ii) 끝점
앞서 시작점을 스위핑하면서 구한 최댓값+1을 세그먼트 트리에서 현재 점 y 좌표에 갱신해준다.

답은 저장해놓은 L의 최대 크기가 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, c[MXN], tree[MXN * 4], y[MXN], res;
struct st {
    int x, y, t, idx;
}p[MXN * 2];
void update(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    tree[h] = max(tree[h], x);
    if (l^r) {
        update(h * 2 + 1, l, (l + r) / 2, g, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    }
}
int query(int h, int l, int r, int g) {
    if (g < l) return 0;
    if (r <= g) return tree[h];
    return max(query(h * 2 + 1, l, (l + r) / 2, g), query(h * 2 + 2, (l + r) / 2 + 1, r, g));
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i + n].x, &p[i + n].y);
        p[i].idx = p[i + n].idx = i;
        p[i].t = 1;
        y[i] = p[i + n].y;
    }
    sort(p, p + 2 * n, [](st i, st j) {return i.x<j.x || i.x == j.x&&i.t>j.t; });
    sort(y, y + n);
    for (int i = 0; i < 2 * n; i++) {
        int lb = lower_bound(y, y + n, p[i].y) - y;
        if (p[i].t) res = max(res, c[p[i].idx] = query(0, 0, n - 1, lb - 1) + 1);
        else update(0, 0, n - 1, lb, c[p[i].idx]);
    }
    printf("%d", res);
    return 0;
}

5480번: Battleship

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


$O(t(k+l)\lg(k+l))$

세그먼트 트리를 이용해 각 전함마다 맞은 첫 레이저를 찾고
해당 레이저에 격추시킨 전함 무게의 최댓값을 갱신해준다.

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int MX = 1e5;
int t, k, m, a[MX][5], b[MX][2], tx[MX * 12], ty[MX * 12];
void update(int *arr, int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    arr[h] = min(arr[h], x);
    if (l^r) update(arr, h * 2 + 1, l, (l + r) / 2, g, x), update(arr, h * 2 + 2, (l + r) / 2 + 1, r, g, x);
}
int query(int *arr, int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return m;
    if (gl <= l&&r <= gr) return arr[h];
    return min(query(arr, h * 2 + 1, l, (l + r) / 2, gl, gr), query(arr, h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int main() {
    for (scanf("%d", &t); t--;) {
        map<int, int> mpx, mpy;
        int szx = 0, szy = 0, res[MX] = {};
        scanf("%*d%d%d", &k, &m);
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 5; j++) scanf("%d", a[i] + j);
            mpx[a[i][0]] = mpx[a[i][2]] = mpy[a[i][1]] = mpy[a[i][3]] = 0;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d", b[i], b[i] + 1);
            b[i][1] ? mpx[b[i][0]] = 0 : mpy[b[i][0]] = 0;
        }
        for (auto &it : mpx) it.second = szx++;
        for (auto &it : mpy) it.second = szy++;
        fill(tx, tx + szx * 4, m);
        fill(ty, ty + szy * 4, m);
        for (int i = 0; i < m; i++)
            b[i][1] ? update(tx, 0, 0, szx - 1, mpx[b[i][0]], i) : update(ty, 0, 0, szy - 1, mpy[b[i][0]], i);
        for (int i = 0; i < k; i++) {
            int n = min(query(tx, 0, 0, szx - 1, mpx[min(a[i][0], a[i][2])], mpx[max(a[i][0], a[i][2])]),
                query(ty, 0, 0, szy - 1, mpy[min(a[i][1], a[i][3])], mpy[max(a[i][1], a[i][3])]));
            if (n < m) res[n] = max(res[n], a[i][4]);
        }
        for (int i = 0; i < m; i++) printf("%d\n", res[i]);
    }
    return 0;
}

14181번: 함수와 쿼리

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

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

f(x,y)를 쉽게 생각해보자.
a[y]
a[y] a[y-1]
a[y] a[y-1] a[y-2]
...
a[y] a[y-1] a[y-2] ... a[y-x+2] a[y-x+1]
이런 삼각형 모양의 배열의 맨 위에 포인터 p가 있다하자.
p는 바로 아래 혹은 아래 오른쪽으로 움직인다.
맨 위에서 아래까지 움직일 때 p가 지나간 항들 합의 최소가 f(x,y)이다.

편의상 t=y-x+1, s[i]=a[1]+a[2]+...+a[i]라 하자.
잘 생각해보면 대각선으로만 움직이다 아래로만 내려가는 경로 중에 최적루트가 있다.
이때, 도착지점이 a[i]라 하면 a[i+1...y]>a[i]이다. ... (*)
즉, f(x,y)=min(t<=i<=t)(s[y]-s[i]+a[i]*(i-t+1))
min 안을 정리해서 다시 쓰면
-a[i]*t+(i+1)*a[i]-s[i]+s[y]
(*)에 의해 [t,y]에 있고 -a[i]가 단조 감소인 i에 대해 (기울기, y절편)=(-a[i],(i+1)*a[i]-s[i]) 직선들을 생각할 수 있다.
이들을 이용해 최솟값을 이루는 convex hull을 만들어 x=t인 지점의 함수값을 구하면 f(x,y)를 구할 수 있다.

다수의 쿼리 빠르게 처리하기 위해 세그먼트 트리를 이용한다.
트리의 [l,r] 구간에 해당하는 convex hull을 미리 만들어 놓고 쿼리 (a,b)가 들어오면 이에 해당하는 구간들의 x=a에서 함수값 중 최솟값을 출력한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
typedef pair<double, double> line;
int n, m, sz[MXN * 4], a[MXN + 1], s[MXN + 1];
vector<line> v[MXN * 4];
vector<double> x[MXN * 4];
double cross(line i, line j) { return (i.second - j.second) / (j.first - i.first); }
void add(int h, int l, int r, int g, line t) {
    if (r < g || g < l) return;
    if (l^r) {
        add(h * 2 + 1, l, (l + r) / 2, g, t);
        add(h * 2 + 2, (l + r) / 2 + 1, r, g, t);
    }
    v[h].resize(r - l + 1);
    x[h].resize(r - l + 1);
    while (sz[h] && v[h][sz[h] - 1].first <= t.first || sz[h] > 1 && cross(v[h][sz[h] - 2], t)>cross(v[h][sz[h] - 1], t)) sz[h]--;
    if (sz[h]) x[h][sz[h] - 1] = cross(v[h][sz[h] - 1], t);
    v[h][sz[h]++] = t;
}
int query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1e9;
    if (gl <= l&&r <= gr) {
        int p = lower_bound(x[h].begin(), x[h].begin() + sz[h] - 1, gl) - x[h].begin();
        return v[h][p].first*gl + v[h][p].second;
    }
    return min(query(h * 2 + 1, l, (l + r) / 2, gl, gr), query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        s[i] = s[i - 1] + a[i];
        add(0, 1, n, i, { -a[i],(i + 1)*a[i] - s[i] });
    }
    scanf("%d", &m);
    for (int i = 0, u, v; i < m; i++) {
        scanf("%d%d", &u, &v);
        printf("%d\n", query(0, 1, n, v - u + 1, v) + s[v]);
    }
    return 0;
}

1849번: 순열

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


$O(n\lg n)$

순서대로 남은 x+1번째 idx를 구한다. 이는 bit나 세그먼트 트리 등을 사용해 해결할 수 있다.

#include<cstdio>
const int MXN = 1e5;
int n, t[MXN * 4], a[MXN];
int kth(int h, int l, int r, int x) {
    t[h]++;
    if (l == r) return l;
    int m = (l + r) / 2;
    return x <= m - l + 1 - t[h * 2 + 1] ? kth(h * 2 + 1, l, m, x) :
        kth(h * 2 + 2, m + 1, r, x + t[h * 2 + 1] - m + l - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), a[kth(0, 0, n - 1, x + 1)] = i;
    for (int i = 0; i < n; i++) printf("%d\n", a[i]);
    return 0;
}

11962번: Counting Haybales

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


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

해당 구간의 건초 더미 합, 각각에 더해져야할 값, 최댓값을 가지고 세그먼트 트리를 구성한다.

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n, q;
struct st {
    ll s, p, m;
}tree[800000];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) {
        tree[h].p += x;
        tree[h].m += x;
        return;
    }
    tree[h].s += (ll)x*(min(gr, r) - max(gl, l) + 1);
    update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
    update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    tree[h].m = min(tree[h * 2 + 1].m, tree[h * 2 + 2].m) + tree[h].p;
}
ll queryM(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1e18;
    if (gl <= l && r <= gr) return tree[h].m;
    return min(queryM(h * 2 + 1, l, (l + r) / 2, gl, gr), queryM(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr)) + tree[h].p;
}
ll queryS(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return tree[h].p*(r - l + 1) + tree[h].s;
    return queryS(h * 2 + 1, l, (l + r) / 2, gl, gr) + queryS(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr) + tree[h].p*(min(gr, r) - max(l, gl) + 1);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        update(0, 1, n, i, i, x);
    }
    int a, b, c;
    char op;
    while (q--) {
        scanf(" %c%d%d", &op, &a, &b);
        if (op == 'M') printf("%lld\n", queryM(0, 1, n, a, b));
        else if (op == 'P') scanf("%d", &c), update(0, 1, n, a, b, c);
        else printf("%lld\n", queryS(0, 1, n, a, b));
    }
    return 0;
}

10070번: 벽

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


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

본 문제를 세그먼트 트리에서 lazy propagation을 이용하여 해결할 수 있도록 결합법칙이 성립하는 연산 @를 정의해보자.

트리의 각 노드는 (low,up)을 가지는데 이것은 해당 구간의 벽 높이가 [low,up] 범위 안이라는 의미이다.
s1=[l1,u1], s2=[l2,r2]일 때 s1 @ s2 는
u1<l2이면 [l1,l1]
r2<l1이면 [r2,r2]
그 이외 $s1 \cap s2$
라고 정의하자. 이 때, 연산 순서는 자식 @ 부모 방향이다.
이렇게 정의한 연산은 결합 법칙이 성립한다. 즉, (A@B)@C = A@(B@C)
이제 lazy propagation을 이용할 수 있다.
op=1이면 [h,inf]를 @시켜주고
op=2이면 [0,h]를 @시켜준다.
최종 답은 리프노드부터 루트노드까지 @시켜주면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 2e6, inf = 1e5;
int n, k;
struct st {
    int low, up;
    st operator+(st i) {
        return{ min(max(low,i.low),i.up),min(max(up,i.low),i.up) };
    }
}tree[MXN * 4];
void update(int h, int l, int r, int gl, int gr, st x) {
    if (r < gl || gr < l) return;
    if (l^r) {
        tree[h * 2 + 1] = tree[h * 2 + 1] + tree[h];
        tree[h * 2 + 2] = tree[h * 2 + 2] + tree[h];
        tree[h] = { 0,inf };
    }
    if (gl <= l&&r <= gr) tree[h] = tree[h] + x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
}
st query(int h, int l, int r, int g) {
    if (r < g || g < l) return{ 0,inf };
    if (l == r) return tree[h];
    return query(h * 2 + 1, l, (l + r) / 2, g) + query(h * 2 + 2, (l + r) / 2 + 1, r, g) + tree[h];
}
int main() {
    for (scanf("%d%d", &n, &k); k--;) {
        int op, l, r, h;
        scanf("%d%d%d%d", &op, &l, &r, &h);
        if (op == 1) update(0, 0, n - 1, l, r, { h, inf });
        else update(0, 0, n - 1, l, r, { 0,h });
    }
    for (int i = 0; i < n; i++) printf("%d\n", query(0, 0, n - 1, i).up);
    return 0;
}

7626번: 직사각형

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


$O(n\lg n)$

http://codedoc.tistory.com/421

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 2e5;
int n, idx[MXN * 2], e, lt[MXN * 8], ct[MXN * 8];
ll res;
struct st {
    int x, y1, y2, t;
}line[MXN * 2];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return;
    if (gl <= l && r <= gr) ct[h] += x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
    if (ct[h]) lt[h] = idx[r + 1] - idx[l];
    else lt[h] = l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x1, x2, y1, y2; i < n; i++) {
        scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
        line[i] = { x1,y1,y2,1 };
        line[i + n] = { x2,y1,y2,-1 };
        idx[i] = y1;
        idx[i + n] = y2;
    }
    sort(line, line + 2 * n, [](st i, st j) {return i.x < j.x; });
    sort(idx, idx + 2 * n);
    e = unique(idx, idx + 2 * n) - idx;
    for (int i = 0; i < 2 * n; i++) {
        if (i) res += (ll)lt[0] * (line[i].x - line[i - 1].x);
        update(0, 0, e - 1, lower_bound(idx, idx + e, line[i].y1) - idx,
            lower_bound(idx, idx + e, line[i].y2) - idx - 1, line[i].t);
    }
    printf("%lld", res);
    return 0;
}

10922번: 말

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

대회 당시 인터렉티브 문제로 출제되었으므로 입력을 미리 받아야 쓸 수 있는 풀이는 자제하자.


$O(n\lg n+m\lg (n+m)\lg X)$ // X는 X[i],Y[i]의 최댓값

X[i], Y[i]가 수정될 수 있을 때, f(x)=X[0]*X[1]*...*X[x]*Y[x]의 최댓값을 구하는 문제이다.
단순히 구간 갱신 쿼리를 관리하는 문제로 바꿔 풀면 누적되는 수가 너무 커질 수 있다.
X[i], Y[i]가 자연수이며 10억 이하인 점을 주목하자.
f(x)가 x=i일 때 최댓값을 가진다고 해보자.
그렇다면 X[j]>1 (j>i)를 만족하는 j는 30개 보다 작아야 한다.
그렇지 않으면,
f(n)/f(i) = X[i+1]*X[i+2]*...*X[n]*Y[n]/X[i] <= 1이어야 하는데
10^9 < 2^30 <= X[i+1]*X[i+2]*...*X[n] <= X[i]/Y[n] <= 10^9 이므로 모순이기 때문이다.

X[x]>1인 x를 내림차순 정렬한 수열을 {x_i}라 하자.(x_0=n, 예외로 이 수열의 마지막 항은 항상 0이다.)
X[1]*x[2]*...*X[i]*Y[k] (k는 x_i<=j<x_i-1일 때 최대 Y[j]를 만드는 j)
i<=30에 대한 k가 최대 f(x)를 만드는 x의 후보가 될 수 있다. xi는 우선순위 큐를 이용해 관리할 수 있을 것이다.

최댓값은 x[1]*x[2]*...*x[i]와 y[i...j]의  최댓값을 구하는 세그먼트 트리를 활용하여 구할 수 있다.

#include<cstdio>
#include<queue>
#include<algorithm>
#define mod 1000000007
using namespace std;
const int MXN = 5e5;
int n, m, x[MXN], tmul[MXN * 4], tmax[MXN * 4];
priority_queue<int> pq;
void upmax(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) {
        tmax[h] = x;
        return;
    }
    upmax(h * 2 + 1, l, (l + r) / 2, g, x);
    upmax(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    tmax[h] = max(tmax[h * 2 + 1], tmax[h * 2 + 2]);
}
int qmax(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1;
    if (gl <= l&&r <= gr) return tmax[h];
    return max(qmax(h * 2 + 1, l, (l + r) / 2, gl, gr), qmax(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
void upmul(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) {
        tmul[h] = x;
        return;
    }
    upmul(h * 2 + 1, l, (l + r) / 2, g, x);
    upmul(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    tmul[h] = (long long)tmul[h * 2 + 1] * tmul[h * 2 + 2] % mod;
}
int qmul(int h, int l, int r, int g) {
    if (g < l) return 1;
    if (r <= g) return tmul[h];
    return (long long)qmul(h * 2 + 1, l, (l + r) / 2, g)*qmul(h * 2 + 2, (l + r) / 2 + 1, r, g) % mod;
}
void res() {
    int last = n, use[30], ucnt = 0;
    long long maxi = 1;
    for (int i = 0; i < 30 && maxi <= 1e9; i++) {
        while (!pq.empty() && (x[pq.top()] == 1 || pq.top() == last)) pq.pop();
        if (pq.empty()) break;
        maxi = max(maxi, 1LL * qmax(0, 0, n - 1, pq.top(), last - 1));
        maxi *= x[pq.top()];
        use[ucnt++] = last = pq.top();
        pq.pop();
    }
    if (pq.empty()) maxi = max(maxi, 1LL * qmax(0, 0, n - 1, 0, last - 1)), last = 0;
    printf("%lld\n", maxi%mod*qmul(0, 0, n - 1, last - 1) % mod);
    while (ucnt--) pq.push(use[ucnt]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", x + i);
        pq.push(i);
        upmul(0, 0, n - 1, i, x[i]);
    }
    for (int i = 0, y; i < n; i++) {
        scanf("%d", &y);
        upmax(0, 0, n - 1, i, y);
    }
    scanf("%d", &m);
    res();
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1) {
            pq.push(b);
            upmul(0, 0, n - 1, b, x[b] = c);
        }
        else upmax(0, 0, n - 1, b, c);
        res();
    }
    return 0;
}

4002번: 닌자배치

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


$O(n{lgn}^2)$

i번 닌자를 매니저로 정할 때, i번 닌자의 자손들 중 예산 안에서 월급이 작은 닌자부터 차례대로 고용하는 것이 최선이다.
이 때 고용된 닌자들 집합을 Ai라 하자.
i번 닌자의 자식들을 sj라 하면
언제나 Asj들을 만들 때 제외된 닌자들은 Ai에 존재할 수 없다.(귀류법으로 증명할 수 있다.)
따라서 자식들의 Asj 합집합 + i번 닌자에서 예산이 넘치는 만큼 월급이 큰 닌자부터 제외시킨 집합이 Ai가 된다.
값이 큰 원소부터 제외하는 연산은 우선순위 큐로 구현할 수 있고, 이들을 합칠 때 사이즈가 큰 큐쪽으로 합치면 총 O(nlgn)의 연산횟수에 문제를 해결할 수 있다.

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MXN = 1e5;
int n, m, p[MXN + 1];
ll c[MXN + 1], l[MXN + 1], r;
priority_queue<int> pq[MXN + 1];
vector<int> adj[MXN + 1];
void f(int h) {
    p[h] = h;
    pq[h].push(c[h]);
    for (auto it : adj[h]) {
        f(it);
        if (pq[p[h]].size() < pq[p[it]].size()) swap(p[h], p[it]);
        while (!pq[p[it]].empty()) pq[p[h]].push(pq[p[it]].top()), pq[p[it]].pop();
        c[h] += c[it];
    }
    while (c[h] > m) c[h] -= pq[p[h]].top(), pq[p[h]].pop();
    r = max(r, (ll)pq[p[h]].size()*l[h]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d%lld%lld", &x, c + i, l + i);
        adj[x].push_back(i);
    }
    f(1);
    printf("%lld", r);
    return 0;
}

$O(nlgn)$

처음 아이디어는 위와 같다.
트리를 순회하면서 번호를 매기면 어떤 정점의 자손들이 모두 인접한 번호를 가지고 있게 할 수 있다.
세그먼트 트리를 이용해 해당 구역에서 월급이 가장 큰 닌자를 O(lgn)에 찾고 제거할 수 있다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 1e5;
int n, m, l[MXN + 1], p[MXN + 1], cnt;
ll c[MXN + 1], r;
pair<int, int> tree[MXN * 4];
vector<int> adj[MXN + 1];
void insert(int h, int s, int e, int g, int x) {
    if (e < g || g < s) return;
    if (s == e) {
        tree[h] = { x,g };
        return;
    }
    insert(h * 2 + 1, s, (s + e) / 2, g, x);
    insert(h * 2 + 2, (s + e) / 2 + 1, e, g, x);
    tree[h] = max(tree[h * 2 + 1], tree[h * 2 + 2]);
}
pair<int, int> find(int h, int s, int e, int gs, int ge) {
    if (ge < s || e < gs) return{ 0,0 };
    if (gs <= s&&e <= ge) return tree[h];
    return max(find(h * 2 + 1, s, (s + e) / 2, gs, ge), find(h * 2 + 2, (s + e) / 2 + 1, e, gs, ge));
}
void f(int h) {
    int s = cnt;
    p[h]++;
    insert(0, 0, n - 1, cnt++, c[h]);
    for (auto it : adj[h]) {
        f(it);
        c[h] += c[it];
        p[h] += p[it];
    }
    while (c[h] > m) {
        pair<int, int> t = find(0, 0, n - 1, s, cnt - 1);
        insert(0, 0, n - 1, t.second, 0);
        c[h] -= t.first;
        p[h]--;
    }
    r = max(r, (ll)p[h] * l[h]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d%lld%d", &x, c + i, l + i);
        adj[x].push_back(i);
    }
    f(1);
    printf("%lld", r);
    return 0;
}

13544번: 수열과 쿼리 3

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


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

세그먼트 트리를 이용한다.(bit를 이용해도 된다.)
구간 [l,r]에 해당하는 서브트리의 루트 노드를 h라 하면
h는 [l,(l+r)/2], [(l+r)/2+1,r] 구간에 해당하는 서브트리의 루트 노드를 자식으로 가지며 수열 a[l...r]을 오름차순 정렬하여 가지게 만든다.
(i,j,k) 쿼리가 들어 오면
해당 구간의 노드마다 upper_bound를 이용하여 k보다 큰 원소의 개수를 합해준다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, m;
vector<int> t[400000];
void insert(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    t[h].push_back(x);
    if (l^r) insert(h * 2 + 1, l, (l + r) / 2, g, x), insert(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
}
int count(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return t[h].end() - upper_bound(t[h].begin(), t[h].end(), x);
    return count(h * 2 + 1, l, (l + r) / 2, gl, gr, x) + count(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), insert(0, 1, n, i, x);
    for (int i = 0; i < n * 4; i++) sort(t[i].begin(), t[i].end());
    scanf("%d", &m);
    for (int i = 0, x, y, z, r = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        r = count(0, 1, n, x^r, y^r, z^r);
        printf("%d\n", r);
    }
    return 0;
}

13537번: 수열과 쿼리 1

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


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

세그먼트 트리를 이용한다.(bit를 이용해도 된다.)
구간 [l,r]에 해당하는 서브트리의 루트 노드를 h라 하면
h는 [l,(l+r)/2], [(l+r)/2+1,r] 구간에 해당하는 서브트리의 루트 노드를 자식으로 가지며 수열 a[l...r]을 오름차순 정렬하여 가지게 만든다.
(i,j,k) 쿼리가 들어 오면
해당 구간의 노드마다 upper_bound를 이용하여 k보다 큰 원소의 개수를 합해준다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 1e5;
int n, m;
vector<int> t[MX * 4];
void insert(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    t[h].push_back(x);
    if (l^r) insert(h * 2 + 1, l, (l + r) / 2, g, x), insert(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
}
int count(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return t[h].end() - upper_bound(t[h].begin(), t[h].end(), x);
    return count(h * 2 + 1, l, (l + r) / 2, gl, gr, x) + count(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), insert(0, 1, n, i, x);
    for (int i = 0; i < n * 4; i++) sort(t[i].begin(), t[i].end());
    scanf("%d", &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        printf("%d\n", count(0, 1, n, x, y, z));
    }
    return 0;
}

$O((n+m)lgK)$

persistent segment tree를 이용한다.
tree[i]: 수열의 1~i번째 항에서 [l,r] 구간에 포함된 항의 개수

효율적으로 활용하기 위해선 추가로 좌표압축이 필요할 것 같다. 이 경우 시간복잡도는 $O((n+m)lg(n+m))$

#include<cstdio>
int n, m;
struct st {
    st *left = 0, *right = 0;
    int s = 0;
}*tree[100001];
st *update(st *now, int l, int r, int g) {
    if (r < g || g < l) return now;
    st *ret = new st();
    if (l == r) ret->s = now->s + 1;
    else {
        if (!now->left) now->left = new st;
        if (!now->right) now->right = new st;
        ret->left = update(now->left, l, (l + r) / 2, g);
        ret->right = update(now->right, (l + r) / 2 + 1, r, g);
        ret->s = ret->left->s + ret->right->s;
    }
    return ret;
}
int query(st *now, int l, int r, int g) {
    if (r <= g || !now) return 0;
    if (g < l) return now->s;
    return query(now->left, l, (l + r) / 2, g) + query(now->right, (l + r) / 2 + 1, r, g);
}
int main() {
    scanf("%d", &n);
    tree[0] = new st;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        tree[i] = update(tree[i - 1], 1, 1e9, x);
    }
    scanf("%d", &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        printf("%d\n", query(tree[y], 1, 1e9, z) - query(tree[x - 1], 1, 1e9, z));
    }
    return 0;
}

2601번: 도서실카펫

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


$O(nlgln)$ // 좌표압축을 통해 O(nlgn)으로 해결 가능

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5, MAX_L = 1e6;
int dx, dy, ux, uy, l, n, scnt, r, sum[MAX_L * 4], maxi[MAX_L * 4];
struct st {
    int y, x1, x2, t;
    bool operator<(st i) const {
        return y < i.y || y == i.y&&t<i.t;
    }
}s[MAX_N * 2];
void push(int x1, int y1, int x2, int y2) {
    x2 = max(x2, l - 1);
    y2 = max(y2, l - 1);
    if (x1>x2 || y1>y2) return;
    s[scnt++] = { y1,x1,x2,1 };
    s[scnt++] = { y2 + 1,x1,x2,-1 };
}
void query(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l && r <= gr) sum[h] += x;
    else {
        query(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
    maxi[h] = l == r ? sum[h] : sum[h] + max(maxi[h * 2 + 1], maxi[h * 2 + 2]);
}
int main() {
    scanf("%d %d %d %d %d %d", &dy, &ux, &uy, &dx, &l, &n);
    for (int i = 0, x, y, z, w; i < n; i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        push(y - 1, z - 1, w + l - 1, x + l - 1);
    }
    sort(s, s + scnt);
    for (int i = 0; i < scnt; i++) {
        query(0, dx, ux, s[i].x1, s[i].x2, s[i].t);
        r = max(r, maxi[0]);
    }
    printf("%d", r);
    return 0;
}

10999번: 구간 합 구하기 2

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


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

lazy propagation, bit 같이 방법은 많은데 세그먼트 트리에서 변수 두개를 이용하여 해결하는 방법에 대해서만 쓰겠다.
세그먼트 트리를 이용할 때 변수 하나만으로는 문제를 해결하기 어렵다고 느낄 것이다.
변수를 하나만 사용할 경우, 구간 갱신시에 찾는 구간에 해당하는 노드들에 합을 누적시킨다해도 구간 쿼리 처리시 범위에 따라 이전에 저장한 값에 접근하지 못할 수 있다.
이런 문제점을 해결하기 위해 변수를 두 개 사용하여 하나는 자식들을 탐색하지 않고도 해당 노드의 구간에 해당하는 값에 접근할 수 있도록 하고, 다른 하나는 루트로 부터 내려올때마다 어떠한 값을 저장시켜 해당 구간의 부분 구간에 저장될 값들을 접근할 수 있도록 해야한다.
이러한 점을 고려하여 각 노드는 구간의 전체 합, 구간의 각 위치에 동일하게 더해야 하는 값을 저장하는 두 가지의 변수를 가지게 한다. 이를 각각 t1,t2라 하자.
업데이트시
만족하는 구간을 찾으면 그 노드의 t2에 d를 누적한다.
루트로부터 만족하는 구간을 찾을 때까지 거쳐오는 노드들의 각 t1에 자신의 구간 중 찾는 구간에 더해질 값들을 누적한다.
쿼리처리시
만족하는 구간을 찾으면 그 노드의 t1값을 누적한다.
루트로부터 만족하는 구간을 찾을 때까지 거쳐오는 노드들마다 t2*(자신의 구간 중 찾는 구간 크기)를 누적한다.

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e6;
typedef long long ll;
int n, m, k;
ll t1[MAX_N * 4], t2[MAX_N * 4];
void update(int h, int l, int r, int gl, int gr, ll x) {
    if (r < gl || gr < l) return;
    t1[h] += (min(r, gr) - max(l, gl) + 1)*x;
    if (gl <= l && r <= gr) {
        t2[h] += x;
        return;
    }
    update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
    update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
}
ll query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return t1[h];
    return query(h * 2 + 1, l, (l + r) / 2, gl, gr)
        + query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr)
        + (min(r, gr) - max(l, gl) + 1)*t2[h];
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), update(0, 1, n, i, i, x);
    ll w;
    for (int i = 0, x, y, z; i < m + k; i++) {
        scanf("%d", &x);
        if (x == 1) {
            scanf("%d %d %lld", &y, &z, &w);
            update(0, 1, n, y, z, w);
        }
        else {
            scanf("%d %d", &y, &z);
            printf("%lld\n", query(0, 1, n, y, z));
        }
    }
    return 0;
}