13537 - 수열과 쿼리 1

step 1

원래 있는 수열을 쿼리로 변환해 봅시다.그럼 문제는 다음과 같이 바뀝니다.

 

길이 $N$인 수열이 주어집니다. 처음 수열의 값은 전부 0입니다.

• $1 i k$ : 수열 $i$번째 위치에 $k$를 추가합니다.
• $2 i j k$ : $A_i, A_{i+1}, ..., A_j$로 이루어진 부분 수열 중에서 $k$보다 큰 원소의 개수를 출력한다.

step 2

$2 i j k$를 봅시다. 수열에서 $k$ 이하인 숫자들은 아무 의미가 없습니다. $k$ 초과인 숫자들은 $k$보다 크다는 것이 중요하지 그 숫자의 값은 중요하지 않습니다.

그럼 이 쿼리들을 $k$가 큰 순서로, $k$가 같으면 2번 쿼리가 먼저 나오도록 정렬해 봅시다. 세그먼트 트리를 하나 만든 다음 1번 쿼리고 오면 $i$에 1 추가, 2번 쿼리가 오면 $i$부터 $j$ 사이에 있는 1의 개수를 카운트를 하면 이 문제를 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct data {
    int q, x, y, z,i;
    inline bool operator<(const data& temp)const {
        return z > temp.z || z == temp.z && q < temp.q;
    }
}b[300000];
int d[200000];
int it[400000], t = 1;
void up(int p) {
    it[p]++;
    while (p != 1) {
        p >>= 1;
        it[p]++;
    }
}
int find(int s, int e, int i, int x, int y) {
    if (x <= s && e <= y) return it[i];
    if (y<s || x>e) return 0;
    return find(s, (s + e) / 2, i * 2, x, y) + find((s + e) / 2 + 1, e, i * 2 + 1, x, y);
}
int main() {
    int n, i,m;
    scanf("%d", &n);
    for (i = 1;i <= n;i++) {
        scanf("%d", &b[i].z);
        b[i].x = i;
        b[i].q = 2;
    }
    while (t < n) t <<= 1;
    scanf("%d", &m);
    for (i = n+1;i <= n+m;i++) {
        scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
        b[i].q = 1;
        b[i].i = i - n;
    }
    sort(b + 1, b + n + m + 1);
    for (i = 1;i <= n + m;i++) {
        if (b[i].q == 1) {
            d[b[i].i] = find(1, t, 1, b[i].x, b[i].y);
        }
        else {
            up(t - 1 + b[i].x);
        }
    }
    for (i = 1;i <= m;i++) printf("%d\n", d[i]);
    return 0;
}