2019.01.19 codeforces343D.Water Tree（树剖+ODT）

传送门

ODTODTODT板子题。

支持子树01覆盖，路径01覆盖，询问一个点的值。

思路：当然可以用树剖+线段树，不过树剖+ODTODTODT也可以很好的水过去。

注意修改路径时每次跳重链都要修改。

不会ODTODTODT的点这里

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
const int N=5e5+5;
int top[N],hson[N],siz[N],dep[N],num[N],fa[N],tot=0,n;
vector<int>e[N];
struct Node{
    int l,r;
    mutable bool v;
    Node(int l,int r=-1,bool v=0):l(l),r(r),v(v){}
    friend inline bool operator<(const Node&a,const Node&b){return a.l<b.l;}
};
set<Node>S;
typedef set<Node>::iterator It;
inline 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;
    bool v=it->v;
    return S.erase(it),S.insert(Node(l,pos-1,v)),S.insert(Node(pos,r,v)).first;
}
inline void assign(int l,int r,bool v){
    It R=split(r+1),L=split(l);
    S.erase(L,R),S.insert((Node){l,r,v});
}
inline bool query(int pos){
    It it=S.lower_bound(Node(pos));
    if(it!=S.end()&&it->l==pos)return it->v;
    return --it,it->v;
}
void dfs1(int p){
    siz[p]=1;
    for(ri i=0,v;i<e[p].size();++i){
        if((v=e[p][i])==fa[p])continue;
        dep[v]=dep[p]+1,fa[v]=p,dfs1(v),siz[p]+=siz[v];
        if(siz[v]>siz[hson[p]])hson[p]=v;
    }
}
void dfs2(int p,int tp){
    top[p]=tp,num[p]=++tot;
    if(!hson[p])return;
    dfs2(hson[p],tp);
    for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v);
}
inline void change(int x){
    while(top[x]^1)assign(num[top[x]],num[x],0),x=fa[top[x]];
    assign(1,num[x],0);
}
int main(){
    S.insert(Node(1,n=read(),0));
    for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    dfs1(1),dfs2(1,1);
    for(ri tt=read(),op,x;tt;--tt){
        op=read(),x=read();
        switch(op){
            case 1:assign(num[x],num[x]+siz[x]-1,1);break;
            case 2:change(x);break;
            default:cout<<query(num[x])<<'\n';
        }
    }
    return 0;
}

巴特西

2019.01.19 codeforces343D.Water Tree（树剖+ODT）

最新文章

热门文章