BZOJ 4154 [Ipsc2015]Generating Synergy

题目大意

给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色。

DFS序一维，深度一维，建立二维KD-Tree,之后跑一下就好了.

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000000
#define MO 1000000007
#define R register
#define ls p[pos].c[0]
#define rs p[pos].c[1]
int to[N+1],nex[N+1],head[N+1],tot;
long long ans;
int cnt,id[N+1],depth[N+1],siz[N+1],rt,ref[N+1];
int md;
struct node
{
    int c[2],v[2],mx[2],mn[2],cl,lz,fa,ref;
    bool operator<(const node &tg)const
    {
        if(v[md]==tg.v[md]) return v[md^1]<tg.v[md^1];
        return v[md]<tg.v[md];
    }
}p[N+1];
char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int RI()
{
    R int ret=0;R char tmp=nc();
    while(!isdigit(tmp)) tmp=nc();
    while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
    return ret;
}
inline void AE(int tx,int ty){to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}
void DFS(int pos)
{
    siz[pos]=1;
    id[pos]=++cnt;
    for(int i=head[pos];i;i=nex[i])
    {
        depth[to[i]]=depth[pos]+1;
        DFS(to[i]);
        siz[pos]+=siz[to[i]];
    }
}
inline void pushup(int pos)
{
    p[pos].mx[0]=max(p[pos].v[0],max(p[ls].mx[0],p[rs].mx[0]));
    p[pos].mx[1]=max(p[pos].v[1],max(p[ls].mx[1],p[rs].mx[1]));
    p[pos].mn[0]=min(p[pos].v[0],min(p[ls].mn[0],p[rs].mn[0]));
    p[pos].mn[1]=min(p[pos].v[1],min(p[ls].mn[1],p[rs].mn[1]));
}
inline void pushdown(int pos)
{
    if(p[pos].lz) p[ls].cl=p[rs].cl=p[ls].lz=p[rs].lz=p[pos].lz,p[pos].lz=0;
}
int build(int l,int r,int now)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    md=now;
    nth_element(p+l,p+mid,p+r+1);
    p[mid].c[0]=build(l,mid-1,now^1),p[p[mid].c[0]].fa=mid;
    p[mid].c[1]=build(mid+1,r,now^1),p[p[mid].c[1]].fa=mid;
    pushup(mid);
    return mid;
}
void color(int pos,int w,int a,int s,int d,int tg)
{
    if(!pos||p[pos].mx[0]<a||p[pos].mn[0]>d||p[pos].mn[1]>w||p[pos].mx[1]<s) return;
    if(p[pos].mn[0]>=a&&p[pos].mx[0]<=d&&p[pos].mx[1]<=w&&p[pos].mn[1]>=s)
    {
        p[pos].cl=p[pos].lz=tg;
        return;
    }
    pushdown(pos);
    if(p[pos].v[0]>=a&&p[pos].v[0]<=d&&p[pos].v[1]>=s&&p[pos].v[1]<=w) p[pos].cl=tg;
    color(p[pos].c[0],w,a,s,d,tg);
    color(p[pos].c[1],w,a,s,d,tg);
}
int query(int pos)
{
    if(p[pos].fa) query(p[pos].fa);
    pushdown(pos);
    return p[pos].cl;
}
int main()
{
    R int T;
    T=RI();
    while(T--)
    {
        cnt=ans=tot=0;memset(head,0,sizeof head),memset(siz,0,sizeof siz);
        R int n=RI(),c=RI(),q=RI(),ix,iy,iz;
        for(int i=0;i<=n;++i)
            p[i].mx[0]=p[i].mx[1]=-0x3f3f3f3f,p[i].mn[0]=p[i].mn[1]=0x3f3f3f3f,p[i].cl=1,p[i].fa=p[i].lz=0;
        for(int i=2;i<=n;++i) AE(RI(),i);
        DFS(1);
        for(int i=1;i<=n;++i) p[i].v[0]=id[i],p[i].v[1]=depth[i],p[i].ref=i;
        rt=build(1,n,0);
        for(int i=1;i<=n;++i) ref[p[i].ref]=i;
        for(int i=1;i<=q;++i)
        {
            ix=RI(),iy=RI(),iz=RI();
            if(!iz) ans=(ans+1ll*i*query(ref[ix]))%MO;
            else color(rt,depth[ix]+iy,id[ix],depth[ix],id[ix]+siz[ix]-1,iz);
        }
        printf("%lld\n",ans);
    }
    return 0;
}