Codeforces 343D Water Tree

题目链接http://codeforces.com/contest/343/problem/D

题意:给一棵树,三种操作:1.u及其祖先染白;2.u及其儿子染黑;3.询问u的颜色.

思路:树剖以后线段树当然能做,不过是为了练习ODT,所以就用ODT写了,虽然题目没说数据随机,但还是过了,可见这种暴力还是有点用的,1,2都是区间推平操作,操作3你直接split出来就可以了。

ODT

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=500000+10;
int n,q,i,c,u,v,dfs_clock,dep[N],sz[N],fa[N],son[N],L[N],R[N],bel[N];
vector<int>G[N];
#define IT set<Node>::iterator
struct Node{
    int l,r;
    mutable int v;
    Node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const Node&rhs)const{
        return l<rhs.l;
    }
};
set<Node>S;
IT split(int pos){
    IT it=S.lower_bound(Node(pos));
    if (it!=S.end() && it->l==pos) return it;
    --it;
    int l=it->l,r=it->r,v=it->v;
    S.erase(it);
    S.insert(Node(l,pos-1,v));
    return S.insert(Node(pos,r,v)).first;
}
void assign(int l,int r,int val){
    IT itr=split(r+1),itl=split(l);
    S.erase(itl,itr);
    S.insert(Node(l,r,val));
}
int query(int x){return split(x)->v;}
void dfs(int u,int f){
    sz[u]=1,son[u]=-1,fa[u]=f,dep[u]=dep[f]+1;
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f;L[u]=R[u]=++dfs_clock;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
    R[u]=dfs_clock;
}
void modify(int u,int v){
    while (bel[u]!=bel[v]){
        if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
        assign(L[bel[u]],L[u],0);
        u=fa[bel[u]];
    }
    if (L[u]>L[v]) swap(u,v);
    assign(L[u],L[v],0);
}
int main(){
    read(n);
    for (i=1;i<n;++i){
        read(u),read(v);
        G[u].PB(v);
        G[v].PB(u);
    }
    dfs(1,0),dfs2(1,1);
    S.insert(Node(1,n,0));
    for (read(q);q--;){
        read(c),read(v);
        if (c==1) assign(L[v],R[v],1);
        else if (c==2) modify(1,v);
        else printf("%d\n",query(L[v]));
    }
    return 0;
}

线段树

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=500000+10;
int n,q,i,c,u,v,dfs_clock,dep[N],sz[N],fa[N],son[N],L[N],R[N],bel[N];
vector<int>G[N];
int val[N<<2],tag[N<<1];
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
void pushdown(int root){
    if (tag[root]!=-1){
        val[root<<1]=val[root<<1|1]=tag[root];
        tag[root<<1]=tag[root<<1|1]=tag[root];
        tag[root]=-1;
    }
}
void build(int root,int l,int r){
    val[root]=0,tag[root]=-1;
    if (l==r) return;
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
}
void update(int root,int l,int r,int L,int R,int v){
    if (L<=l && r<=R){
        val[root]=v;
        tag[root]=v;
        return;
    }
    pushdown(root);
    int mid=l+((r-l)>>1);
    if (L<=mid) update(lson,L,R,v);
    if (mid<R) update(rson,L,R,v);
}
int query(int root,int l,int r,int pos){
    if (l==r) return val[root];
    pushdown(root);
    int mid=l+((r-l)>>1);
    if (pos<=mid) return query(lson,pos);
    else return query(rson,pos);
}
void dfs(int u,int f){
    sz[u]=1,son[u]=-1,fa[u]=f,dep[u]=dep[f]+1;
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f;L[u]=R[u]=++dfs_clock;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
    R[u]=dfs_clock;
}
void modify(int u,int v){
    while (bel[u]!=bel[v]){
        if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
        update(1,1,n,L[bel[u]],L[u],0);
        u=fa[bel[u]];
    }
    if (L[u]>L[v]) swap(u,v);
    update(1,1,n,L[u],L[v],0);
}
int main(){
    read(n);
    for (i=1;i<n;++i){
        read(u),read(v);
        G[u].PB(v);
        G[v].PB(u);
    }
    dfs(1,0),dfs2(1,1);
    build(1,1,n);
    for (read(q);q--;){
        read(c),read(v);
        if (c==1) update(1,1,n,L[v],R[v],1);
        else if (c==2) modify(1,v);
        else printf("%d\n",query(1,1,n,L[v]));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注