题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4154
题意：给定一棵以 1 为根的有根树，初始所有节点颜色为 1，每次将距离节点 a 不超过 l 的 a 的子节点染成 c，或询问点 a 的颜色。
震惊！l1ll5 竟未想到 KDtree 可以做这样的事！....
发现子树内对应 dfs 序上的一段连续区间，距离不超过 l 对于深度的一段连续区间，所以树上的一个点可以转换为二维平面上的一个的，矩形 cover 和单点查询可以用 kdt 实现，复杂度\(O(n \sqrt n)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define ll long long #define mod 1000000007 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to; }edge[N]; int head[N],cnt=1; void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } int deep[N],tim[N],dfn,sz[N]; void dfs(int x) { sz[x]=1; tim[x]=++dfn; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; deep[to]=deep[x]+1; dfs(to); sz[x]+=sz[to]; } } ll ans; int Testcase; int n,c,q,D; struct node { int d[2],mn[2],mx[2],col,tag,l,r; int& operator [](int x) {return d[x];} friend bool operator <(node a,node b) {return a[D]==b[D]?(a[D^1]<b[D^1]):(a[D]<b[D]);} }tr[N],p[N],T; int root; void pushup(int x) { node l=tr[tr[x].l],r=tr[tr[x].r]; for(int i=0;i<2;i++) { if(tr[x].l)tr[x].mn[i]=min(tr[x].mn[i],l.mn[i]),tr[x].mx[i]=max(tr[x].mx[i],l.mx[i]); if(tr[x].r)tr[x].mn[i]=min(tr[x].mn[i],r.mn[i]),tr[x].mx[i]=max(tr[x].mx[i],r.mx[i]); } } void pushdown(int x) { if(tr[x].tag) { tr[tr[x].l].tag=tr[tr[x].r].tag=tr[tr[x].l].col=tr[tr[x].r].col=tr[x].tag; tr[x].tag=0; } } int build(int l,int r,int now) { if(l>r)return 0; int mid=(l+r)>>1; D=now; nth_element(p+l,p+mid,p+r+1); tr[mid]=p[mid]; for(int i=0;i<2;i++) tr[mid].mn[i]=tr[mid].mx[i]=p[mid][i]; tr[mid].l=build(l,mid-1,now^1); tr[mid].r=build(mid+1,r,now^1); pushup(mid); return mid; } bool sqr_inside(node x,node y)//y inside x { for(int i=0;i<2;i++) if(!(x.mn[i]<=y.mn[i]&&y.mx[i]<=x.mx[i]))return 0; return 1; } bool outside(node x,node y) { for(int i=0;i<2;i++) if(x.mn[i]>y.mx[i]||x.mx[i]<y.mn[i])return 1; return 0; } bool pt_inside(node x,node y) { for(int i=0;i<2;i++) if(!(x.mn[i]<=y[i]&&y[i]<=x.mx[i]))return 0; return 1; } void cover(int x,int v) { if(!x)return ; if(outside(T,tr[x]))return ; if(sqr_inside(T,tr[x])) { tr[x].tag=tr[x].col=v; return ; } pushdown(x); if(pt_inside(T,tr[x]))tr[x].col=v; cover(tr[x].l,v),cover(tr[x].r,v); } int ask(int x,int now) { if(tr[x][0]==T[0]&&tr[x][1]==T[1])return tr[x].col; pushdown(x); if(T[now]<tr[x][now]||(T[now]==tr[x][now]&&T[now^1]<tr[x][now^1]))return ask(tr[x].l,now^1); else return ask(tr[x].r,now^1); } int main() { Testcase=read(); while(Testcase--) { memset(head,0,sizeof(head)); cnt=1;ans=dfn=0; memset(tr,0,sizeof(tr)); n=read(),read(),q=read(); for(int i=2;i<=n;i++) add(read(),i); dfs(1); for(int i=1;i<=n;i++)p[i][0]=tim[i],p[i][1]=deep[i]; root=build(1,n,0); tr[root].col=tr[root].tag=1; for(int i=1;i<=q;i++) { int a=read(),l=read(),c=read(); if(c==0) { T[0]=tim[a],T[1]=deep[a]; ans+=(ll)i*ask(root,0),ans%=mod; } else { T.mn[0]=tim[a],T.mx[0]=tim[a]+sz[a]-1; T.mn[1]=deep[a],T.mx[1]=deep[a]+l; cover(root,c); } } printf("%lld\n",ans); } } |
Comments | NOTHING