BOJ 14898 - 서로 다른 수와 쿼리 2

문제 링크 : www.acmicpc.net/problem/14898

문제 태그 

 persistent segment tree

문제 풀이

꽤나 오래 고민했지만, 풀이가 감이 안잡혔다. 그래서 힌트를 받았고 [1,i] 구간이라는 힌트를 얻게 되었다. 

모든 [1,i]구간에 대해서 서로 다른 수의 개수를 가지고 있는 것은 어렵지 않게 해낼 수 있다. 하지만 우리가 필요한 것은 [i,j] 구간에 대한 서로 다른 수의 개수다. 

여기서 한가지 아이디어를 생각해냈다. [1,i] 구간에서 각 수별로 가장 오른쪽에 있는 수들만 가지고 있는 것이다. 즉, [1,i] 구간에서 가장 오른쪽에 있는 1, 가장 오른쪽에 있는 2, ... 들을 가지고 있는 것이다. 
이렇게 되면 쿼리로 [a,b] 에 대한 질문이 들어오면, [1,b] 구간을 저장하고 있는 것을 확인하고, [a,b] 구간에 몇 개가 저장되어 있는지를 확인하면 된다.

좀 더 생각을 해보자. 모든 [1,i]에 대해서 다 가장 오른쪽에 처음 나오는 수들의 위치를 알아야 한다. 이것을 어떻게 저장하고 있을지를 생각해보자. [1,i]에 대해서 저장한 것을 $S_i$ 라고 하자. 그러면 $S_{i+1}$은 i+1 위치의 수만 추가하면 된다. 그러면 i+1와 같은 가장 오른쪽의 숫자가 사라지고 그 것을 i+1로 옮기기만 하면 된다는 것이다. 이것을 세그로 관리하면 두 번의 업데이트 만으로 다음 저장을 만들 수 있다.
이렇게 만든 세그 트리에 구간에 대해서 그 구간에 남아있는 수의 갯수를 노드에 가지고 있으면, 어떤 구간에 대해서 서로 다른 수의 개수를 구할 수 있다.

이 문제는 온라인이기 때문에 모든 세그트리를 다 저장하고 있어야 한다. 하지만 n개의 세그트리를 모두 저장하고 있으면, 공간복잡도 상의 문제가 생기게 된다. [1,i]와 [1,i+1]의 세그트리는 두번의 업데이트를 통해서 바꿀 수 있는 관계이므로, persistent segment tree를 사용하면 이 문제를 해결할 수 있다.

구현 과정에서 mle를 잘 신경써야 된다. 

코드

 

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back
#define ff first 
#define ss second
 
struct node{
    ll l,r,val;
};
 
vector<node> tree;
void mak(){
    tree.pb({-1,-1,0});
}
 
 
void init(ll s,ll e,ll nod){
    if(s==e) return;
    mak();
    tree[nod].l=tree.size()-1;
 
    mak();
 
    tree[nod].r=tree.size()-1;
 
    init(s,(s+e)/2,tree[nod].l);
    init((s+e)/2+1,e,tree[nod].r);
}
 
void upt(ll idx,ll val,ll s,ll e,ll nod1,ll nod2){
    //printf("%lld %lld %lld %lld %lld %lld %d %lld %lld %lld %lld\n",idx,val,s,e,nod1,nod2,tree.size(),tree[nod1].l,tree[nod1].r,tree[nod2].l,tree[nod2].r);
    
    if(idx<s||idx>e){
        tree[nod2].l=tree[nod1].l;
        tree[nod2].r=tree[nod1].r;
        tree[nod2].val=tree[nod1].val;
        return;
    }
 
    tree[nod2].val=tree[nod1].val+val;
    if(s==e) return;
 
    if(idx<=(s+e)/2){
        tree[nod2].r=tree[nod1].r;
        mak();
        tree[nod2].l=tree.size()-1;
 
        //printf("lgo %lld %lld %lld %lld %lld %lld %d %lld %lld %lld %lld\n",idx,val,s,e,nod1,nod2,tree.size(),tree[nod1].l,tree[nod1].r,tree[nod2].l,tree[nod2].r);
        upt(idx,val,s,(s+e)/2,tree[nod1].l,tree[nod2].l);
    }
    else{
        tree[nod2].l=tree[nod1].l;
        mak();
        tree[nod2].r=tree.size()-1;
 
        //printf("rgo %lld %lld %lld %lld %lld %lld %d %lld %lld %lld %lld\n",idx,val,s,e,nod1,nod2,tree.size(),tree[nod1].l,tree[nod1].r,tree[nod2].l,tree[nod2].r);
        upt(idx,val,(s+e)/2+1,e,tree[nod1].r,tree[nod2].r);
    }
}
 
ll sol(ll l,ll r,ll s,ll e,ll nod){
    //printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",l,r,s,e,nod,tree[nod].val,tree[nod].l,tree[nod].r);
    if(e<l||r<s) return 0;
    if(l<=s&&e<=r) return tree[nod].val;
    return sol(l,r,s,(s+e)/2,tree[nod].l)+sol(l,r,(s+e)/2+1,e,tree[nod].r);
}
 
ll arr[1010101];
vector<ll> v[1000101];
vector<ll> num;
 
int main(){
    ll i,j,k,l,m,n;      
    scanf("%d",&n);
    tree.reserve(12500000);
    for(i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        num.pb(arr[i]);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()),num.end());
 
    for(i=1;i<=n;i++)
        arr[i]=lower_bound(num.begin(), num.end(),arr[i])-num.begin();
    for(i=0;i<=n;i++)
        v[i].pb(0);
 
    for(i=1;i<=n;i++)
        v[arr[i]].pb(i);
 
    for(i=0;i<=n;i++)
        for(j=1;j<v[i].size();j++)
            arr[v[i][j]]=v[i][j-1];
 
    ll cnt=0;
 
    for(i=0;i<=2*n;i++)
        mak();
    init(1,n,0);
 
    for(i=1;i<=n;i++){
        if(arr[i]) {
            cnt++;
            upt(arr[i],-1,1,n,cnt-1,cnt);
        }
        cnt++;
        upt(i,1,1,n,cnt-1,cnt);
        v[i][0]=cnt;
    }
 
   // for(i=0;i<=2*n;i++)
    //    printf("%d %d\n",i,tree[i].val);
 
    ll q;
    ll las=0;
    scanf("%lld",&q);
    sol(1,1,1,n,2);
   
    while(q--){
        ll a,b;
        scanf("%d %d",&a,&b);
 
      //  printf("%lld %lld\n",a+las,b);
        las=sol(a+las,b,1,n,v[b][0]);
        printf("%d\n",las);
    }
    
}