[USACO10FEB]慢下来Slowing down

线段树树的dfs序

来自洛谷 P1982 的翻译

by GeneralLiu

来自 jzyz 的翻译 %mzx

线段树 dfs序

数据结构的应用

“数据结构是先有需求再有应用” by mzx

那么按照这个思路

先看看针对这道题有什么需求

再考虑用什么数据结构去解决

以及怎么用该数据结构

这是一个树上的题

某个人进了寝室

只会影响到他子树的答案

因为只有他的子树回寝室时

要经过他得slowing down对吧

这时要对他的子树的答案全部区间+1

这是对dfs序的需求

需要 dfs序将树转换成区间

区间修改单点查询又是对线段树的需求

需要线段树的高效维护

如有dalao有更高效的方法请博客留言

我目前只学了线段树这个家伙啦

具体应用

dfs序

void dfs(int u){

    dfn[u]=++cnt;//dfn[]为树转换为dfs序中的下标

    size[u]=1;//u为根的子树大小

    int v;

    for(int i=head[u];i;i=next[i]){

        v=to[i];

        if(dfn[v])continue;

        dfs(v);

        size[u]+=size[v];

    }

}

这样一棵子树就对应了 dfn[]数组的一段区间

　以点k为根的区间

　　左端点是 dfn[k],

　　右端点是 dfn[k] + size [k] - 1 。

线段树

main() 函数中的代码

for(int k,i=1;i<=n;i++){

      k=read();

      //单点查询

      printf("%d\n",query(dfn[k],root));

      //区间修改

      update(dfn[k],dfn[k]+size[k]-1,root);

}

其他函数

void pushdown(int rt){//懒标记下传

    if(!add[rt])return;

    add[rt<<1]+=add[rt];

    add[rt<<1|1]+=add[rt];

    add[rt]=0;

}

void update(int x,int y,int l,int r,int rt){

    if(x<=l&&r<=y){

        add[rt]++;//区间修改时 针对本题 懒标记+1

        return;

    }

    pushdown(rt);

    int mid=(l+r)>>1;

    if(x<=mid)update(x,y,lson);

    if(mid<y)update(x,y,rson);

}

int query(int k,int l,int r,int rt){

    //单点查询 所以线段树只用 懒标记add[]数组 即可

    if(l==r)return add[rt];

    pushdown(rt);

    int mid=(l+r)>>1;

    if(k<=mid)return query(k,lson);

    return query(k,rson);

}

这样就滋瓷了本题的修改与查询操作

完

总代码

#include<bits/stdc++.h>

using namespace std;

#define N 100015

#define root 1,n,1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

int n,cnt;

int head[N],next[N<<1],to[N<<1];

int dfn[N],size[N];

int add[N<<2];

int read(){

    int ans=0;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar());

    for(;isdigit(ch);ch=getchar())

        ans=(ans<<3)+(ans<<1)+ch-'0';

    return ans;

}

void ad(int from,int too){

    next[++cnt]=head[from];

    to[cnt]=too;

    head[from]=cnt;

}

void dfs(int u){

    dfn[u]=++cnt;//dfn[]为树转换为dfs序中的下标

    size[u]=1;//u为根的子树大小

    int v;

    for(int i=head[u];i;i=next[i]){

        v=to[i];

        if(dfn[v])continue;

        dfs(v);

        size[u]+=size[v];

    }

}

void pushdown(int rt){//懒标记下传

    if(!add[rt])return;

    add[rt<<1]+=add[rt];

    add[rt<<1|1]+=add[rt];

    add[rt]=0;

}

void update(int x,int y,int l,int r,int rt){

    if(x<=l&&r<=y){

        add[rt]++;//区间修改时 针对本题 懒标记+1

        return;

    }

    pushdown(rt);

    int mid=(l+r)>>1;

    if(x<=mid)update(x,y,lson);

    if(mid<y)update(x,y,rson);

}

int query(int k,int l,int r,int rt){

    //单点查询 所以线段树只用 懒标记add[]数组 即可

    if(l==r)return add[rt];

    pushdown(rt);

    int mid=(l+r)>>1;

    if(k<=mid)return query(k,lson);

    return query(k,rson);

}

int main(){

    n=read();

    for(int x,y,i=1;i<n;i++){

        x=read(),y=read();

        ad(x,y);

        ad(y,x);

    }

    cnt=0;

    dfs(1);

    for(int k,i=1;i<=n;i++){

        k=read();

        //单点查询

        printf("%d\n",query(dfn[k],root));

        //区间修改

        update(dfn[k],dfn[k]+size[k]-1,root);

    }

    return 0;

}

巴特西

[USACO10FEB]慢下来Slowing down

最新文章

热门文章