BZOJ 4154 kd-tree dfs序 + 二维空间的区间(矩阵)更新单点查找
2024-08-26 10:42:07
一开始没思路 感觉像是一个树形dp 然而不会
然后看了一眼题解就明白了
一个点的子树 用dfs序表示肯定是一个连续的区间 并且由于有子树的距离限制 可以转化为一个深度的区间
于是每个点都会有一个在二维平面上的标号(x,y) == (编号,深度)
并且每次进行更新一个节点的子树的时候就可以得到一个x的区间和一个y的区间 (实际上这些x是独一无二的 y更像是一个限制的条件)
这样就可以转化成一个二维的平面 每次选择一个矩阵进行颜色的统一更新 询问单点的颜色 做一个延时标记
询问单点的时候可以每次找啊找直到找到这个点 也可以判断一下mark mark一定是最新的历史 如果这个点在这个区间里面并且这个区间有修改历史 那么ans就是mark
不过加了这个优化速度并没有提升多少
在这里kd-tree很像线段树 区别就是维度不同
找了一个小bug就直接a掉了 开心!
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<queue>
#include<string>
using namespace std;
#define L long long
const L INF = 999999999 ;
const L maxn = 100050 ;
const L mod = 1000000007;
/**
用dfs序设定每个点的子树的标号区间
存下每个点的deep
则每个点在二维平面的x为它的标号 y为它的深度 (如果仅要表示这个点主码x就可以了)
利用kdtree来进行区间修改单点查询
如果区间满足 Max[0] Min[0] 属于 x1 x2 && Max[1] Min[1] 属于 y11 y2 就直接修改这个区间的颜色 设置一个延时标记
x1 x2 == l[a] r[a] y11 y2 == deep[a] deep[a] + l
单点查询直接进行一个logn的查询
*/
L n , c , q ;
L deep[maxn] ;
vector<L >vec[maxn] ;
L l[maxn] , r[maxn] ;
L cnt ;
void dfs(L u , L dep) {
deep[u] = dep ;
l[u] = ++ cnt ;
for(L i = 0; i < vec[u].size(); i ++ ){
L v = vec[u][i] ;
dfs(v,dep + 1) ;
}
r[u] = cnt ;
}
L root , cmp_d ;
struct node {
L l , r ;
L d[2] , Max[2] , Min[2] ;
L c ;
L mark ;
}a[maxn];
bool cmp(node a,node b){return ((a.d[cmp_d] < b.d[cmp_d])||(a.d[cmp_d] == b.d[cmp_d] && a.d[!cmp_d] < b.d[!cmp_d])) ;} ;
void up(L p , L k ){
if(a[k].Max[0] > a[p].Max[0]) a[p].Max[0] = a[k].Max[0] ;
if(a[k].Max[1] > a[p].Max[1]) a[p].Max[1] = a[k].Max[1] ;
if(a[k].Min[0] < a[p].Min[0]) a[p].Min[0] = a[k].Min[0] ;
if(a[k].Min[1] < a[p].Min[1]) a[p].Min[1] = a[k].Min[1] ;
}
void down(L p) {
if(a[p].mark == 0)return ;
L newc = a[p].mark ;
a[p].mark = 0 ;
if(a[p].r) {
L rr = a[p].r ;
a[rr].c = newc ;
a[rr].mark = newc ;
}
if(a[p].l) {
L ll = a[p].l ;
a[ll].c = newc ;
a[ll].mark = newc ;
}
return ;
}
L build(L l, L r , L D) {
L mid = (l+r)/2 ;
cmp_d = D;
nth_element(a+1+l,a+1+mid,a+1+r,cmp) ;
a[mid].Max[0] = a[mid].Min[0] = a[mid].d[0] ;
a[mid].Max[1] = a[mid].Min[1] = a[mid].d[1] ;
a[mid].c = 1 ;
a[mid].mark = 0 ;
if(l != mid)a[mid].l = build(l,mid-1,D^1); else a[mid].l = 0;
if(r != mid)a[mid].r = build(mid+1,r,D^1); else a[mid].r = 0;
if(a[mid].l)up(mid,a[mid].l) ;
if(a[mid].r)up(mid,a[mid].r) ;
return mid ;
}
void upda(L p , L x1 , L y11 , L x2 , L y2 , L newc ) {
if(a[p].Max[0] < x1 || a[p].Min[0] > x2 || a[p].Max[1] < y11 || a[p].Min[1] > y2) {
return ;
}
if(a[p].Min[0] >= x1 && a[p].Max[0] <= x2 && a[p].Max[1] <= y2 && a[p].Min[1] >= y11) {
a[p].c = newc ;
a[p].mark = newc ;
return ;
}
down(p) ;
if(a[p].d[0] >= x1 && a[p].d[0] <= x2 && a[p].d[1] >= y11 && a[p].d[1] <= y2) {
a[p].c = newc ;
}
if(a[p].l) {
upda(a[p].l , x1, y11 , x2 , y2 , newc) ;
}
if(a[p].r) {
upda(a[p].r , x1, y11 , x2 , y2 , newc) ;
}
}
L ans ;
void ask(L p , L x, L y) {
if(a[p].d[0] == x && a[p].d[1] == y) {
ans = a[p].c ;
return ;
}
if(a[p].mark != 0) {
ans = a[p].mark ;
return ;
}
down(p) ;
if(a[p].l) {
L ll = a[p].l ;
if(x >= a[ll].Min[0] && x <= a[ll].Max[0] && y >= a[ll].Min[1] && y <= a[ll].Max[1]) {
ask(ll , x , y) ;
}
}
if(a[p].r) {
L ll = a[p].r ;
if(x >= a[ll].Min[0] && x <= a[ll].Max[0] && y >= a[ll].Min[1] && y <= a[ll].Max[1]) {
ask(ll , x , y) ;
}
}
}
int main(){
L t ;
scanf("%lld",&t);
while(t-- ){
scanf("%lld%lld%lld",&n,&c,&q) ;
for(L i = 1; i <= n ; i ++ )vec[i].clear() ;
for(L i = 2; i <= n ; i ++ ){
L fa ;
scanf("%lld",&fa) ;
vec[fa].push_back(i) ;
}
cnt = 0 ;
dfs(1,1) ;
for(L i = 1; i <= n; i ++ ){
a[i].l = a[i].r = 0;
a[i].d[0] = l[i] ;
a[i].d[1] = deep[i] ;
}
root = build(1,n,0) ;
L sum = 0;
for(L i = 1; i <= q; i ++ ){
L aa , ll , cc ;
scanf("%lld%lld%lld",&aa,&ll,&cc);
L x1 = l[aa] ;
L x2 = r[aa] ;
L y11 = deep[aa] ;
L y2 = deep[aa] + ll ;
if(cc != 0) {
upda(root , x1 , y11 , x2 , y2 , cc) ;
}
else {
ans = -1 ;
L x = l[aa] ;
L y = deep[aa] ;
ask(root, x , y) ;
sum += ans * i ;
sum %= mod ;
}
}
printf("%lld\n",sum) ;
}
}
最新文章
- AngularJS动画
- 为什么匿名内部类和局部内部类只能访问final变量
- DWR的Reverse Ajax技术实现
- missing sdkl in .NET Core 1.0.1 - VS 2015 Tooling Preview 2
- Linux下拷贝目录和删除
- php模拟用户自动在qq空间发表文章的方法
- CAShapeLayer--备用
- javascript中的正则匹配函数exec(),test(),match()
- FACE++学习一、detect接口
- Libevent 反应堆的初始化
- javaScript函数参数
- 邓_html_选项卡
- jquery 跨域请求数据问题
- RTMPdump（libRTMP）源代码分析 4： 连接第一步——握手（Hand Shake）
- （原创）cocos lua 热更新从零开始（一）最简单demo
- Favorite Donut（HDU 5442）最小表示法+二分
- vue day6 分页显示
- cmd返回上一级和根目录
- LeetCode（7）：颠倒整数
- .net中的集合