글 읽기 - persistent segment tree 관련 문제 질문드립니다.

smu201111192 6년 전 1

도무지 어떤부분이 틀렸는지 감이 안 와서

다른분 코드를 참고해 수정을 해서 ac를 받았습니다.

수정한 부분은 dfs 밖에 없는데 두 dfs의 차이를 잘 모르겠습니다.

수정 dfs는 bfs처럼 자식노드의 세그트리들을 거리 순서대로 차례대로 만들어주고 있고

제가 작선한 dfs는 방문순서대로 차례대로 세그트리를 만들어줬는데 wa가 나네요.ㅠ

어떤 차이가 있는걸까요?.

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int MAXN=100055;
int par[MAXN][18],dep[MAXN];
int n,m;
int cnt;
vector<int> adj[MAXN];
vector<int> v;
map<int,int> mp; //좌표 압축 번호
int recover[MAXN];
struct node{
    node *l,*r;
    int sum;
    node(){ l=r=NULL; sum=0; }
}*root[MAXN];

void init(node *cur,int l,int r){
    if(l==r){return;}
    cur->l=new node();
    cur->r=new node();
    int m=(l+r)/2;
    init(cur->l, l , m);
    init(cur->r,m+1 , r);
    
}

void add(int idx,int l,int r,node *cur,node *p){
    int mid=(l+r)/2;
    if(l==r){
        cur->sum=p->sum+1;
        return;
    }
    
    if(idx>=l && idx<=mid){
        cur->l=new node();
        cur->r=p->r;
        add(idx,l,mid,cur->l,p->l);
    }
    
    else{
        cur->r=new node();
        cur->l=p->l;
        add(idx,mid+1,r,cur->r,p->r);
    }
    cur->sum=    cur->l->sum    +    cur->r->sum;
}

queue<int> que,pque;


void dfs(int x,  int p){
    que.push(x);
    pque.push(0);
    while(!que.empty()){
        x = que.front();
        p = pque.front();
        que.pop(),  pque.pop();
        root[x] = new node();
        add(mp[v[x]],  1,  n,  root[x],  root[p]);
        par[x][0] = p;
        for(int i=1;  i<17;  i++){
            par[x][i] = par[par[x][i-1]][i-1];
        }
        for(int i=0;  i<adj[x].size();  i++){
            if(adj[x][i]  ==  p) continue;
            dep[adj[x][i]] = dep[x] + 1;
            que.push(adj[x][i]);
            pque.push(x);
        }
    }
}

/*
/////////////////////문제가 생긴 dfs/////////////
void dfs(int x,  int p){
    dep[x]=dep[p]+1;
    par[x][0]=p;
    root[x]=new node();
    add(mp[v[x]],1,n,root[x],root[p]); //(좌표압축번호,시작,끝,세그트리 x의 루트 포인터,세그트리 p의 루트포인터)
    for(auto there:adj[x]){
        if(there==p)continue;
        dfs(there,x);
    }
    for(int i=1;  i<17;  i++){
        par[x][i] = par[par[x][i-1]][i-1];
    }
}
///////////////////////////////////////////////
 */
int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    int dx = dep[b] - dep[a];
    for(int i=0; i<18; i++){
        if((dx >> i) & 1) b = par[b][i];
    }
    for(int i=17; i>=0; i--){
        if(par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    }
    if(a == b) return a;
    return par[a][0];
}


int track(int s,int e,node *a,node *b,node *c,node *d,int k){
    if(s==e)return s;
    int sm=  a->l->sum  +   b->l->sum  -   c->l->sum   -  d->l->sum;
    int mid=(s+e)/2;
    if(k<=sm){
        return track(s,mid,a->l,b->l,c->l,d->l,k);
    }
    else{
        return track(mid+1,e,a->r,b->r,c->r,d->r,k-sm);
    }
}
inline void fastRead_int(int *a)
{
    register char c=0;
    while (c<33) c=getchar_unlocked();
    *a=0;
    while (c>33)
    {
        *a=*a*10+c-'0';
        c=getchar_unlocked();
    }
}

inline void fastRead_string(char *str)
{
    register char c=0;
    register int i = 0;
    while (c < 33)
        c = getchar_unlocked();
    while (c > 65)
    {
        str[i] = c;
        c = getchar_unlocked();
        i = i + 1;
    }
    
    str[i] = '\0';
}int main(){
    cin>>n>>m;
    cnt=1;
    v.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        mp[v[i]];
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        recover[cnt]=it->first;
        it->second=cnt++;
    }
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    root[0]=new node();
    init(root[0],1,cnt-1);
    dfs(1,0);
    for(int i=0;i<m;i++){
        int u,v,k;
        fastRead_int(&u);
        fastRead_int(&v);
        fastRead_int(&k);
        int id=track(1,cnt-1,root[u],root[v],root[lca(u,v)],root[par[lca(u,v)][0]],k);
        printf("%d\n",recover[id]);
        //cout<<recover[id]<<"\n";
    }
    return 0;
}

ntopia 6년 전 1

par 배열을 계산하는것을 dfs함수 안에서 해서 그런 것 같네요

x의 par배열을 계산할 때 필요한 정보는 x의 조상의 par배열에서 갖고오는데

x의 조상의 par배열은 아직 계산되지 않은 상태입니다

koosaga 6년 전 1

87-89줄이 이상하네요. par[][] 배열이 dfs 재귀 스택을 빠져 나올 때 계산이 된다면, 만약에 자식이 부모 노드의 par[][] 배열을 참고하려고 할 때 배열에 저장된 값들은 어떻게 되나요?

(잡담입니다만, 제 코드가 도움이 됐다면 기쁘지만 저건 좀 너무 비슷한거 같아요 ㅠㅠ 개념 정립이 되었다면 자기 스타일로 처음부터 다시 짜는게 공부에 도움이 되지 않을까요)

smu201111192 6년 전 0

ㅠ/ㅠ 죄송합니다. 다시한번 제 스타일로 짜볼게요!!

두분 모두 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

persistent segment tree 관련 문제 질문드립니다.

smu201111192 6년 전 1

ntopia 6년 전 1

koosaga 6년 전 1

smu201111192 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말