[백준]퀘스트 중인 모험가(15816)

문제 링크 : [백준]퀘스트 중인 모험가(15816)

15816번: 퀘스트 중인 모험가

 

문제 설명

-1,000,000,000 ~ 1,000,000,000 까지의 수의 범위 중에서 아래와 같은 쿼리가 주어집니다.

• 1 x : x값이 채워짐
• 2 x y : x ~ y 사이에서 채워지지 않은 값의 갯수를 출력

 

입력

N(최초에 채워진 수의  갯수, 1 <= N <= 1,000,000)

V_i(채워진 값, -1,000,000,000 <= V_i <= 1,000,000,000)

M(쿼리의 갯수, 1 <= M <= 1,000,000)

O_i A_i B_i(쿼리 정보) 

3
1 10 20
4
2 1 20
1 5
2 1 20
2 1 1

 

출력

17
16
0

 

카테고리

#오프라인쿼리 #세그먼트트리 #펜윅트리 #좌표압축

 

시간 복잡도 상한

O(QlogQ)

 

해결 방법

1. 퀘스트 달성 쿼리가 오면 해당 퀘스트 인덱스를 1로 변경합니다.
2. 조회 쿼리가 주어지면 해당 범위 내에서 채워진 수의 갯수를 세면 됩니다.
3. 빈번한 업데이트와 구간 합을 구하기 때문에, 세그먼트 트리나 펜윅트리를 이용하면 됩니다.
4. 그러나 값의 범위가 매우 넓기 때문에 그대로 사용하면 안됩니다.
5. 나타날 수 있는 인덱스의 범위는 최초 주어지는 수 1,000,000개와 쿼리에서 오는 갯수 1,000,000개, 총 2,000,000개입니다.
6. 입력받은 인덱스를 정렬하여 새로운 인덱스로 변경하여 사용합니다.
7. 이후에는 일반 세그먼트 트리와 동일한 문제입니다.
8. 최초에 좌표압축을 트리맵으로 사용했더니 타임아웃이 났습니다. 아무래도 vector의 정렬과 erase, unique를 사용하도록 해야겠습니다.
9. 나머지는 upper, lower bound 사용을 잘못하여 틀렸습니다ㅠ
10. 좌표 매핑은 항상 조심해야 합니다.

시간복잡도

O(Qlog(Q+N))

코드

#include<iostream>
#include<vector>
#include<algorithm>
#define N 2000010
using namespace std;
int n,q,d[N],t[N],i,u[N][3],k,v[N],x,y;
vector<int>m;
void a(int p){
    if(v[p])return;
    v[p]=1;
    while(p<=k)t[p]++,p+=p&-p;
}
int in(int p){
    int s=0;
    while(p)s+=t[p],p-=p&-p;
    return s;
}
int p(int x){
    return lower_bound(m.begin(),m.end(),x)-m.begin()+2;
}
int p2(int x){
    return upper_bound(m.begin(),m.end(),x)-m.begin()+2;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(;i<n;i++)cin>>d[i],m.push_back(d[i]);
    cin>>q;
    for(i=0;i<q;i++){
        cin>>u[i][0]>>u[i][1];
        if(u[i][0]&1)m.push_back(u[i][1]);
        else cin>>u[i][2];
    }
    sort(m.begin(),m.end());
    m.erase(unique(m.begin(),m.end()),m.end());
    k=m.size()+2;
    for(i=0;i<n;i++)a(p(d[i]));
    for(i=0;i<q;i++){
        x=p(u[i][1]);
        if(u[i][0]&1)a(x);
        else cout<<u[i][2]-u[i][1]+1-in(p2(u[i][2])-1)+in(p(u[i][1])-1)<<"\n";
    }
}