Generating Synergy bzoj-4154 Ipsc-2015

题目大意：给定一棵n个节点树，m个操作，支持：将一个点周围所有距该点距离不超过l的子结点的颜色改成另一种颜色；查询单点颜色。每个点的颜色开始都是1。

注释：$1\le n,m\le 10^5$

---

想法：这就是一个典型的不是KD-Tree裸题，我们需要将它转化成点。

首先，我们先拉出整棵树的dfs序。

每个节点，我们设横坐标就是dfs序上的下标，纵坐标就是深度。我们发现，一个点的子树是一段连续的区间，然后当深度确定是，我们发现这就是矩阵赋值，加上pushdown操作即可。

单点查询遍历即可。不要忘记query的时候也要pushdown

另外没有插入操作，就不用重构了。

最后，附上丑陋的代码... ...

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 100010using namespace std;int head[N],to[N],nxt[N],cnt,deep[N],pos[N],last[N],tot,d,root;struct data{	int p[2],mx[2],mn[2],c[2],w,tag;	bool operator <(const data &a) const	{		return p[d]==a.p[d]?p[d^1]
         
          
           r) return 0; int mid=(l+r)>>1; d=now,nth_element(a+l,a+mid,a+r+1); a[mid].w=1,a[mid].tag=0; a[mid].c[0]=build(l,mid-1,now^1); a[mid].c[1]=build(mid+1,r,now^1); pushup(mid); return mid;}inline void pushdown(int x){ if(a[x].tag) { int l=a[x].c[0],r=a[x].c[1]; a[l].w=a[l].tag=a[r].w=a[r].tag=a[x].tag; a[x].tag=0; }}void update(int bx,int ex,int by,int ey,int v,int x){ if(!x||a[x].mx[0]
           
            ex||a[x].mx[1]
            
             ey)return; if(a[x].mn[0]>=bx&&a[x].mx[0]<=ex&&a[x].mn[1]>=by&&a[x].mx[1]<=ey) { a[x].w=a[x].tag=v; return; } pushdown(x); if(a[x].p[0]>=bx&&a[x].p[0]<=ex&&a[x].p[1]>=by&&a[x].p[1]<=ey)a[x].w=v; update(bx,ex,by,ey,v,a[x].c[0]),update(bx,ex,by,ey,v,a[x].c[1]);}int query(int px,int py,int x){ d^=1; if(a[x].p[0]==px&&a[x].p[1]==py) return a[x].w; pushdown(x); if(d) { if(py
             
            
           
          
         
        
       
      
     

小结：KD-Tree这种题还是挺好玩的..