SPOJ QTREE系列

375.QTREE

给你一棵n个点$n-1$条边的树,支持修改一条边的边权、查询两点之间路径上的最大边权。

树链剖分+线段树基础题


code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int H[10005],X[20005],P[20005],tot, w[20005],E[20005],num[20005];
inline void add(int x,int y,int z,int no){
    P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;num[tot]=no;
}
int mx[10005<<2];
int to[10005],tt,siz[10005],son[10005],top[10005],dep[10005],f[10005],tim;
void dfs1(int x,int fa){
    siz[x]=1;son[x]=0;top[x]=0;
    int mx=0;
    for(int i=H[x];i;i=X[i]){
        if(P[i]==fa) continue;
        f[P[i]]=x;
        dep[P[i]]=dep[x]+1;
        w[P[i]]=E[i];
        to[num[i]]=P[i];
        dfs1(P[i],x);
        siz[x]+=siz[P[i]];
        if(siz[P[i]]>mx){
            mx=siz[P[i]];
            son[x]=P[i];
        }
    }
}
void dfs2(int x,int fa){
    if(!top[x]) top[x]=x;
    num[x]=++tim;
    E[tim]=w[x];
    if(son[x])top[son[x]]=top[x],dfs2(son[x],x);
    for(int i=H[x];i;i=X[i]){
        if(P[i]!=son[x]&&P[i]!=fa){
            dfs2(P[i],x);
        }
    }
}
int _c,_l,_r;
void ask(int o,int l,int r){
    if(_l<=l&&r<=_r){
        _c=max(mx[o],_c);
        return ;
    }else{
        int mid=(l+r)>>1;
        if(_l<=mid) ask(o<<1,l,mid);
        if(_r>mid) ask(o<<1|1,mid+1,r);
    }
}
int ask(int l,int r){
    _c=0;
    _l=l,_r=r;
    ask(1,1,n);
    return _c;
}
int Ask(int a,int b){
    int ret=0;
    while(top[a]!=top[b]){
        int x=top[a],y=top[b];
        if(dep[x]<dep[y]) swap(x,y),swap(a,b);
        ret=max(ask(num[x],num[a]),ret);
        a=f[x];

    }
    if(a!=b){
        if(dep[a]>dep[b]) swap(a,b);
        ret=max(ret,ask(num[a]+1,num[b]));
    }
    return ret;
}
char s[50];
void change(int o,int l,int r,int p,int k){
    if(l==r){
        mx[o]=k;
    }else{
        int mid=(l+r)>>1;
        if(p<=mid) change(o<<1,l,mid,p,k);
        else change(o<<1|1,mid+1,r,p,k);
        mx[o]=max(mx[o<<1],mx[o<<1|1]);
    }
}
void bd(int o,int l,int r){
    if(l==r){
        mx[o]=E[l];
    }else{
        int mid=(l+r)>>1;
        bd(o<<1,l,mid);
        bd(o<<1|1,mid+1,r);
        mx[o]=max(mx[o<<1],mx[o<<1|1]);
    }
}
int main(){
    scanf("%d",&tt);
    while(tt--){
        tim=tot=0;
        memset(H,0,sizeof H);
        scanf("%d",&n);
        for(int i=1,a,b,c;i<n;i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c,i);
            add(b,a,c,i);
        }
        dep[1]=1;
        dfs1(1,-1);
        dfs2(1,-1);
        bd(1,1,n);
        int a,b;
        while(scanf("%s",s),s[0]!='D'){
            if(s[0]=='Q'){
                scanf("%d%d",&a,&b);
                printf("%d\n",Ask(a,b));
            }else{
                scanf("%d%d",&a,&b);
                change(1,1,n,num[to[a]],b);
            }
        }
    }
    return 0;
}

913.QTREE2

一棵树,两个操作。
1.询问a到b的最短路。
2.询问a到b的最短路上第k个点是啥。
倍增或者树链剖分。


code:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int tt;
int n;
typedef long long LL;
LL d[10005][16];
int f[10005][16],dep[10005];
int H[10005],X[20005],P[20005],tot,E[20005];
inline void add(int x,int y,int z){
    P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;
}
void dfs(int x){
    dep[x]=dep[f[x][0]]+1;
    for(int i=H[x];i;i=X[i]){
        if(P[i]!=f[x][0]){
            f[P[i]][0]=x;
            d[P[i]][0]=E[i];
            dfs(P[i]);
        }
    }
}
int lg;
char s[50];
LL dist(int x,int y){
    LL ret=0;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=lg;i>=0;i--) if(dep[f[x][i]]>=dep[y]) ret+=d[x][i],x=f[x][i];
    if(x==y) return ret;
    for(int i=lg;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            ret+=d[x][i]+d[y][i];
            x=f[x][i];
            y=f[y][i];
        }
    }
    return ret+d[x][0]+d[y][0];
}
int ask(int x,int y,int k){
    int lca=0,xx=x,yy=y;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=lg;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) lca=x;
    for(int i=lg;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    if(!lca) lca=f[x][0];
    x=xx,y=yy;
    if(-dep[lca]+dep[x]+1<k){
        k=-dep[lca]+dep[x]+1-dep[lca]+dep[y]-k+1;
        x=y;
    }
    k--;
    for(int i=0;i<=lg;i++) if((k>>i)&1) x=f[x][i];
    return x;
}
int main(){
    scanf("%d",&tt);
    while(tt--){
        tot=0;memset(H,0,sizeof H);
        memset(f,0,sizeof f);
        memset(d,0,sizeof d);
        memset(dep,0,sizeof dep);
        scanf("%d",&n);
        for(int i=1,x,y,z;i<n;i++){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        dfs(1);
        for(lg=0;(1<<lg)<=n;lg++) ;lg--;
        for(int j=0;j<=lg;j++){
            for(int i=1;i<=n;i++){
                if(f[i][j]){
                    f[i][j+1]=f[f[i][j]][j];
                    d[i][j+1]=d[i][j]+d[f[i][j]][j];
                }
            }
        }
        int a,b,k;
        while(scanf("%s",s),s[1]!='O'){
            if(s[0]=='D'){
                scanf("%d%d",&a,&b);
                printf("%lld\n",dist(a,b));
            }else{
                scanf("%d%d%d",&a,&b,&k);
                printf("%d\n",ask(a,b,k));
            }
        }
    }
    return 0;
}

2798.QTREE3

(partial)
给你一棵树,root是1,开始所有点是白色。
有两个操作:
1.把一个点v由白变黑,有黑边白。
2.问从root到点v第一个黑点是哪个,没有输出-1.


树链剖分+线段树。
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,q;
int H[100005],X[200005],P[200005],tot;
inline void add(int x,int y){
    P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
int siz[100005],top[100005],son[100005],to[100005],tim,f[100005],p[100005];
int sum[100005*4];
void dfs1(int x,int fa){
    siz[x]=1;
    int mx=0;
    for(int i=H[x];i;i=X[i]){
        if(P[i]!=fa){
            f[P[i]]=x;
            dfs1(P[i],x);
            siz[x]+=siz[P[i]];
            if(siz[P[i]]>mx){
                mx=siz[P[i]];
                son[x]=P[i];
            }
        }
    }
}
void dfs2(int x,int fa){
    if(!top[x]) top[x]=x;
    to[x]=++tim;
    p[tim]=x;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x],x);
    }
    for(int i=H[x];i;i=X[i]){
        if(P[i]!=fa&&P[i]!=son[x]){
            dfs2(P[i],x);
        }
    }
}
int _l,_r,_c;
void ask(int o,int l,int r){
    if(!sum[o]) return;
    if(_l<=l&&r<=_r){
        _c+=sum[o];
    }else{
        int mid=(l+r)>>1;
        if(_l<=mid) ask(o<<1,l,mid);
        if(_r>mid) ask(o<<1|1,mid+1,r);
    }
}
int ask(int l,int r){
    if(l>r) return 0;
    _c=0,_l=l,_r=r;
    ask(1,1,n);
    return _c;
}
void change(int o,int l,int r,int p){
    if(l==r){
        sum[o]^=1;
    }else{
        int mid=(l+r)>>1;
        if(p<=mid) change(o<<1,l,mid,p);
        else change(o<<1|1,mid+1,r,p);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
}
int ask(int k){
    int o=1,l=1,r=n;
    while(l!=r){
        int mid=(l+r)>>1;
        if(sum[o<<1]>=k) o<<=1,r=mid;
        else k-=sum[o<<1],o=o<<1|1,l=mid+1;
    }
    return p[l];
}
int Ask(int x){
    int last=0;
    while(1){
        //topx..x
        if(ask(to[top[x]],to[x])>0) last=x;
        if(top[x]==1) break;
        else x=f[top[x]];
    }
    if(!last) return -1;
    int sum=ask(1,to[top[last]]-1);
    return ask(sum+1);
}
int getint(){
    static char c;
    static int x;
    while(c=getchar(),c<'0'||c>'9');
    x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';
    return x;
}
int main(){
    //scanf("%d%d",&n,&q);
    n=getint();
    q=getint();
    for(int i=1,x,y;i<n;i++){
        x=getint();y=getint();
        add(x,y);add(y,x);
    }
    dfs1(1,0);dfs2(1,0);
    for(int i=0,x,y;i<q;i++){
        x=getint();y=getint();
        if(x){
            printf("%d\n",Ask(y));
        }else{
            change(1,1,n,to[y]);
        }
    }
    return 0;
}

1487.PT07J

Another QTREE3
给你一个有标号的有根树。
q(x,k) 询问在x的子树中,第k大的标号是哪个点。


首先离散化
树上k大,用dfs序+主席树维护。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int w[100005],H[100005],X[200005],P[200005],tot,to[100005],l[100005],r[100005],root[100005];
int sum[100005*50],ls[100005*50],rs[100005*50];
inline void add(int x,int y){
    P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
int n,cc,m;
int tim;
int add(int o,int l,int r,int pos){
    int p=++cc;
    sum[p]=sum[o]+1;
    if(l==r){
        return p;
    }else{
        int mid=(l+r)>>1;
        if(pos<=mid){
            ls[p]=add(ls[o],l,mid,pos);
            rs[p]=rs[o];
        }else{
            ls[p]=ls[o];
            rs[p]=add(rs[o],mid+1,r,pos);
        }
    }
    return p;
}
void dfs(int x,int fa){
    l[x]=++tim;
    root[tim]=add(root[tim-1],1,n,w[x]);
    for(int i=H[x];i;i=X[i]){
        if(P[i]==fa) continue;
        dfs(P[i],x);
    }
    r[x]=tim;
}
int ask(int o1,int o2,int l,int r,int k){
    if(l==r){
        return l;
    }else{
        int mid=(l+r)>>1;
        int tmp=sum[ls[o1]]-sum[ls[o2]];
        if(tmp>=k){
            return ask(ls[o1],ls[o2],l,mid,k);
        }else return ask(rs[o1],rs[o2],mid+1,r,k-tmp);
    }
}
int getint(){
    static char c;
    static int x;
    while(c=getchar(),c<'0'||c>'9');
    x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';
    return x;
}
int main(){
    n=getint();
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        to[i]=w[i];
    }
    sort(to+1,to+n+1);
    for(int i=1;i<=n;i++) w[i]=lower_bound(to+1,to+n+1,w[i])-to;
    for(int i=1;i<=n;i++) to[w[i]]=i;
    for(int i=1,x,y;i<n;i++){
        x=getint();y=getint();
        add(x,y);add(y,x);
    }
    dfs(1,0);
    m=getint();
    for(int i=0,x,k;i<m;i++){
        x=getint();k=getint();
        printf("%d\n",to[ask(root[r[x]],root[l[x]-1],1,n,k)]);
    }
    return 0;
}

2666.QTREE4

代填。


orz: http://www.cnblogs.com/fullpower/p/3869547.html

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框