e[树上主席树] | Hexo

归档于 2019-10-12 20:58

主席树掌握不牢啊

之前那棵树继承父亲的树就行了

挺难打的，细节很多，具体还是看代码

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls(x) tr[x].son[0]
#define rs(x) tr[x].son[1]
#define A 1111111
ll head[A],ver[A],nxt[A],a[A],f[A][25],dep[A],rt[A],r[A],k[A];
ll q,n,type,t,anspre,ansnxt,maxx=0,tot=1;
void add(ll x,ll y){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;
}
struct node{
    ll son[2],sz;
}tr[A*8];
void insert(ll &x,ll v,ll num,ll l,ll r){
    if(!x) x=++tot;
    if(l==r){
        tr[x].sz=tr[v].sz+1;
        return ;
    }
    ll mid=(l+r)>>1;
    ll opt=num>mid,L,R;
    tr[x].son[opt^1]=tr[v].son[opt^1];
    if(opt) L=mid+1,R=r;
    else L=l,R=mid;
    insert(tr[x].son[opt],tr[v].son[opt],num,L,R);
    tr[x].sz=tr[ls(x)].sz+tr[rs(x)].sz;
}
ll lca(ll x,ll y){
    if(dep[x]>dep[y]) swap(x,y);
    for(ll i=t;i>=0;i--){
        if(dep[x]==dep[y]) break;
        if(dep[x]<=dep[f[y][i]]) y=f[y][i];
    }
    if(x==y) return x;
    for(ll i=t;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];y=f[y][i];
        }
    }
    return f[x][0];
}
void dfs(ll x,ll pre){
    insert(rt[x],rt[pre],a[x],1,maxx);
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        f[y][0]=x;
        dep[y]=dep[x]+1;        
        dfs(y,x);
    }
}
void findpre(ll x,ll v,ll l,ll r){
//    printf("tr[x].sz=%lld v.sz=%lld x=%lld v=%lld\n",tr[x].sz,tr[v].sz,x,v);
    if(!(tr[x].sz-tr[v].sz)) return ;
    if(l==r){
//        printf("***l=%lld r=%lld\n",l,r);
        anspre=max(l,anspre);
        return ;
    }
    ll mid=(l+r)>>1;
//    printf("pre x.sz=%lld .sz=%lld rs.sz=%lld .sz=%lld l=%lld r=%lld mid+1=%lld r=%lld\n",tr[x].sz,tr[v].sz,tr[rs(x)].sz,tr[rs(x)].sz,l,r,mid+1,r);
    if(tr[rs(x)].sz-tr[rs(v)].sz) /*printf("findr\n"),*/findpre(rs(x),rs(v),mid+1,r);
    else if(tr[ls(x)].sz-tr[ls(v)].sz) /*printf("findl\n"),*/findpre(ls(x),ls(v),l,mid);
}
void findnxt(ll x,ll v,ll l,ll r){
    if(!(tr[x].sz-tr[v].sz)) return ;
    if(l==r) {
//        printf("*********l=%lld r=%lld\n",l,r);
        ansnxt=min(l,ansnxt);
        return ;
    }
    ll mid=(l+r)>>1;
//    printf("nxt x.sz=%lld .sz=%lld rs.sz=%lld .sz=%lld l=%lld mid=%lld mid+1=%lld r=%lld\n",tr[x].sz,tr[v].sz,tr[rs(x)].sz,tr[rs(x)].sz,l,mid,mid+1,r);
    if(tr[ls(x)].sz-tr[ls(v)].sz) findnxt(ls(x),ls(v),l,mid);
    else if(tr[rs(x)].sz-tr[rs(v)].sz) findnxt(rs(x),rs(v),mid+1,r);
}
void chosepre(ll x,ll v,ll ql,ll qr,ll l,ll r){
//    printf("l=%lld r=%lld ql=%lld qr=%lld\n",l,r,ql,qr);
//    printf("l=%lld r=%lld\n",l,r);
    if(l>=ql&&r<=qr){
//        printf("chose l=%lld r=%lld\n",l,r);
        findpre(x,v,l,r);
        return ;
    }
    ll mid=(l+r)>>1;
//    printf("l=%lld r=%lld mid=")
    if(mid>=ql) chosepre(ls(x),ls(v),ql,qr,l,mid);
    if(mid<qr) chosepre(rs(x),rs(v),ql,qr,mid+1,r);
}
void chosenxt(ll x,ll v,ll ql,ll qr,ll l,ll r){
    if(l>=ql&&r<=qr){
        findnxt(x,v,l,r);
        return ;
    }
    ll mid=(l+r)>>1;
    if(mid>=ql) chosenxt(ls(x),ls(v),ql,qr,l,mid);
    if(mid<qr) chosenxt(rs(x),rs(v),ql,qr,mid+1,r);
}
ll lsh[A];
vector <ll> que[A];
int main(){
//    freopen("da.in","r",stdin);
//    freopen("ans.sol","w",stdout);
    scanf("%lld%lld%lld",&n,&q,&type);
    t=log(n)/log(2)+1;
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]),lsh[++lsh[0]]=a[i];
    for(ll i=1;i<n;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);
    }
    for(ll i=1;i<=q;i++){
        scanf("%lld%lld",&r[i],&k[i]);
        que[i].push_back(0);
        for(ll j=1;j<=k[i];j++){
            ll d;scanf("%lld",&d);
            que[i].push_back(d);
        }
        lsh[++lsh[0]]=r[i];
//        printf("i=%lld q=%lld\n",i,q);
    }
    sort(lsh+1,lsh+lsh[0]+1);
    ll len=unique(lsh+1,lsh+lsh[0]+1)-lsh-1;
    for(ll i=1;i<=n;i++){
//        printf("pre a[i]=%lld\n",a[i]);
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
//        printf("a[i]=%lld\n",a[i]);
    }
    for(ll i=1;i<=q;i++){
//        printf("pre r[i]=%lld\n",r[i]);
        r[i]=lower_bound(lsh+1,lsh+len+1,r[i])-lsh;
//        printf("r[i]=%lld\n",r[i]);
    }
    maxx=len;
    dep[1]=1;
    dfs(1,0);f[1][0]=0;
    for(ll j=1;j<=t;j++)
        for(ll i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
    ll lastans=0;    
//    printf("lsh[0]=%lld\n",lsh[0]);
    for(ll i=1;i<=q;i++){
        for(ll j=1;j<=k[i];j++)
            que[i][j]=(que[i][j]-1+lastans*type)%n+1;
        ll publiclca=que[i][k[i]];
        for(ll j=1;j<k[i];j++)
            publiclca=lca(publiclca,que[i][j]);
        ansnxt=0x7ffffffff,anspre=0;
        ll fa=f[publiclca][0];
//        printf("lca=%lld\n",publiclca);
        for(ll j=1;j<=k[i];j++){
//            printf("rt[%lld]=%lld rt[%lld]=%lld\n",que[j],rt[que[j]],fa,rt[fa]);
            chosepre(rt[que[i][j]],rt[fa],1,r[i],1,maxx);
            chosenxt(rt[que[i][j]],rt[fa],r[i],maxx,1,maxx);
        }
    //    lastans=min(abs(lsh[ansnxt]-lsh[r[i]]),abs(lsh[anspre]-lsh[r[i]]));
//        printf("ansnxt=%lld anspre=%lld\n",ansnxt,anspre);
//        printf("lsh[ansnxt]=%lld lsh[]=%lld\n",lsh[ansnxt],lsh[anspre]);
        if(anspre==0){
//            printf("*********\n");
            printf("%lld\n",abs(lsh[ansnxt]-lsh[r[i]]));
            lastans=abs(lsh[ansnxt]-lsh[r[i]]);
        }
        else if(ansnxt==0x7ffffffff){
            printf("%lld\n",abs(lsh[anspre]-lsh[r[i]]));
            lastans=abs(lsh[anspre]-lsh[r[i]]);
        }
        else printf("%lld\n",min(abs(lsh[ansnxt]-lsh[r[i]]),abs(lsh[anspre]-lsh[r[i]]))),lastans=min(abs(lsh[ansnxt]-lsh[r[i]]),abs(lsh[anspre]-lsh[r[i]]));
    }
}

View Code