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