[백준 BOJ 17668] 시험 | 퍼피가 PS하는 블로그

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

17668번: 시험

문제 요약

학생 $N$명의 시험 점수 $S_{i}, T_{i}$와 $X, Y, Z$로 구성된 $Q$개의 쿼리가 주어진다.

각 쿼리에 대해 $S_{i} \geq X, T_{i} \geq Y, (S_{i}+T_{i}) \geq Z$ 를 만족하는 학생의 수를 출력하라.

풀이

학생의 점수 $(S_{i}, T_{i}, (S_{i}+T_{i}))$를 하나의 구조체로 만들어 줍시다.

 

학생 점수의 순서를 임의로 나열해도 학생의 수를 구하는 데에는 지장이 없습니다. 각 학생의 점수를 $S_{i}$에 대해 정렬합니다($O(NlogN)$).

 

Table 1부터 이어질 예시에서는 $X = 20, Y = 20, Z = 65$를 기준으로 하겠습니다.

 

Table 1. $S_{i}$ 순서대로 학생의 성적을 정렬한 결과

$S_{i}$가 단조 증가하는 순서로 정렬했기 때문에, $S_{i} \geq X $를 만족하는 $i$의 최솟값 $m$를 구하면 $m$ 이상의 index에 위치한 학생만 첫 번째 조건을 만족합니다. $m$를 lower_bound 함수를 통해 구할 수 있습니다($O(QlogN)$).

 

예시에서 $m=2$입니다. Table 2는 $i < m$인 경우를 제외해 준 모습을 나타낸 것입니다.

 

Table 2. $i < m$인 경우를 제외한 결과

이제 $m \leq i \leq n$에서 나머지 두 조건을 만족하는 학생의 수를 구해 봅시다. 두 조건을 식으로 나타내면 다음과 같습니다.

 

$T_{i} \geq Y$

$(S_{i}+T_{i}) \geq Z$

 

두 가지 식이 굉장히 유사합니다. 식을 다음과 같이 변형해봅시다.

 

$(S_{i}+T_{i}) \geq (Y+S_{i})$

$(S_{i}+T_{i}) \geq Z$

 

이제 두 식을 하나로 합칠 수 있습니다.

 

$(S_{i}+T_{i}) \geq max((Y+S_{i}), Z)$

 

$max((Y+S_{i}), Z)$의 값을 생각해봅시다. 각각의 쿼리에 대해 $Y, Z$가 고정되어 있으므로

 

$S_{i} \geq (Z-Y)$에서 $max((Y+S_{i}), Z)=(Y+S_{i})$

$S_{i} \leq (Z-Y)$에서 $max((Y+S_{i}), Z)=Z$ 가 됩니다.

 

$S_{i}$가 정렬되어 있으므로 $S_{i} \geq (Z-Y)$를 만족하는 $i$의 최솟값 $pv$를 lower_bound 함수를 통해 구할 수 있습니다($O(QlogN)$).

 

예시에서 $Z - Y = 45$이므로 $pv = 5$이며, 이를 기준으로 두 가지 구간으로 분할한 모습이 Table 3에 나타나 있습니다.

 

Table 3. $pv$를 기준으로 두 가지 구간으로 분할한 결과

$pv \leq i$에서는 $T_{i} \geq Y$를, $i < pv$에서는 $(S_{i}+T_{i}) \geq Z$를 만족하면 충분합니다.

 

Table 3에서 $2 \leq i < 5$이면서 $(S_{i}+T_{i}) \geq 65$를 만족하는 $i$와,

$5 \leq i \leq 8$이면서 $T_{i} \geq 20$를 만족하는 $i$가 세 조건을 모두 만족합니다. 이는 Table 4에 나타나 있습니다.

 

Table 4. 세 조건을 모두 만족하는 $i$만 남긴 결과

 

정리하면 각각의 쿼리에서는

$m \leq i \leq pv-1$에서 $(S_{i}+T_{i}) \geq Z$를 만족하는 $i$의 개수 + $pv \leq i \leq n$에서 $T_{i} \geq Y$를 만족하는 $i$의 개수

를 출력하면 됩니다. 많이 익숙한 수열과 쿼리 문제가 되었습니다.

 

수열과 쿼리 1: https://www.acmicpc.net/problem/13537

 

해당 값은 merge sort tree를 이용하여 $O((N+Q)logN)$에 구할 수 있습니다.

$T_{i}와 (S_{i}$ + $T_{i})$에 대한 merge sort tree를 각각 만들어 주고 쿼리를 수행하면 됩니다.

 

마지막으로 $pv<m$인 경우($(Z-Y)<X$일 때 만들어질 수 있는 상황)를 예외처리해야 합니다. 이 경우 $i<m$의 범위까지 카운팅하여 답이 더 크게 출력될 수 있습니다. $m \leq i \leq n$에서 $T_{i} \geq Y$를 만족하는 $i$의 개수를 출력하면 됩니다.

Time Complexity

$O((N+Q)logN)$

Code

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
int n, q, k;
struct sta //학생 성적
{
    int s, t, sum; //sum = s + t
    bool operator<(sta a)
    {
        return s<a.s;
    }
}st[100010];
int a[100010];
//Merge Sort Tree
vector<int> tree[1<<18], tree2[1<<18]; //tree는 t의 merge sort tree, tree2는 sum의 merge sort tree
void init(int s, int e, int node)
{
    if(s==e){
        tree[node].push_back(st[s].t);
        tree2[node].push_back(st[s].sum);
        return;
    }
    init(s, (s+e)/2, 2*node);
    init((s+e)/2+1, e, 2*node+1);
    tree[node].resize(tree[2*node].size()+tree[2*node+1].size());
    tree2[node].resize(tree2[2*node].size()+tree2[2*node+1].size());
    merge(all(tree[2*node]), all(tree[2*node+1]), tree[node].begin());
    merge(all(tree2[2*node]), all(tree2[2*node+1]), tree2[node].begin());
}
int query(int s, int e, int node, int val, int l, int r) //tree 쿼리
{
    if(l>r) return 0;
    if(e<l||s>r) return 0;
    if(l<=s&&e<=r){
        int m = lower_bound(all(tree[node]), val)-tree[node].begin();
        return (e-s+1)-m;
    }
    int x = query(s, (s+e)/2, 2*node, val, l, r);
    int y = query((s+e)/2+1, e, 2*node+1, val, l, r);
    return x+y;
}
int query2(int s, int e, int node, int val, int l, int r) //tree2 쿼리
{
    if(l>r) return 0;
    if(e<l||s>r) return 0;
    if(l<=s&&e<=r){
        int m = lower_bound(all(tree2[node]), val)-tree2[node].begin();
        return (e-s+1)-m;
    }
    int x = query2(s, (s+e)/2, 2*node, val, l, r);
    int y = query2((s+e)/2+1, e, 2*node+1, val, l, r);
    return x+y;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>st[i].s>>st[i].t;
        st[i].sum = st[i].s + st[i].t;
    }
    sort(st+1, st+n+1);
    for(int i=1;i<=n;i++) a[i]=st[i].s; //lower_bound 계산을 위해 s값만 나열하여 보조배열을 만듦
    init(1, n, 1);
    while(q--){
        int x, y, z;
        cin>>x>>y>>z;
        int m = lower_bound(a+1, a+n+1, x) - a;
        int pv = lower_bound(a+1, a+n+1, z-y) - a;
        if(m<=pv){
            int u = query2(1, n, 1, z, m, pv-1); //sum>=z인 학생의 수
            int v = query(1, n, 1, y, pv, n); //t>=y인 학생의 수
            cout<<u+v<<'\n';
        }
        else{
            int u = query(1, n, 1, y, m, n); //t>=y인 학생의 수
            cout<<u<<'\n';
        }
    }
    return 0;
}