【BZOJ4154】[Ipsc2015]Generating Synergy
Description
Input
Output
Sample Input
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0
Sample Output
HINT
题解:想了半天奇怪的做法,正解居然是KDtree?
KDtree的第一维是DFS序,第二维是深度,区间修改用打标记实现,查询时下传标记,剩下的就不用说了吧?
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll P=1000000007;
const int maxn=100010;
int n,m,D,rt,cnt;
ll ans;
int to[maxn],next[maxn],head[maxn],p[maxn],q[maxn],fa[maxn],L[2],R[2],dep[maxn],st[maxn],pos[maxn];
struct kd
{
int ls,rs,fa,tag,col,org,v[2],sm[2],sn[2];
kd(){}
kd(int a,int b,int c){sm[0]=sn[0]=v[0]=a,sm[1]=sn[1]=v[1]=b,org=c,ls=rs=fa=0,tag=0,col=1;}
}t[maxn];
bool cmp(const kd &a,const kd &b)
{
return (a.v[D]==b.v[D])?(a.v[D^1]<b.v[D^1]):(a.v[D]<b.v[D]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
inline void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
p[x]=++p[0];
for(int i=head[x];i!=-1;i=next[i]) dep[to[i]]=dep[x]+1,dfs(to[i]);
q[x]=p[0];
}
inline void pushup(int x,int y)
{
t[x].sm[0]=max(t[x].sm[0],t[y].sm[0]);
t[x].sn[0]=min(t[x].sn[0],t[y].sn[0]);
t[x].sm[1]=max(t[x].sm[1],t[y].sm[1]);
t[x].sn[1]=min(t[x].sn[1],t[y].sn[1]);
}
inline void pushdown(int x)
{
if(t[x].tag)
{
if(t[x].ls) t[t[x].ls].col=t[t[x].ls].tag=t[x].tag;
if(t[x].rs) t[t[x].rs].col=t[t[x].rs].tag=t[x].tag;
t[x].tag=0;
}
}
int build(int l,int r,int d)
{
if(l>r) return 0;
int mid=(l+r)>>1;
D=d,nth_element(t+l,t+mid,t+r+1,cmp),pos[t[mid].org]=mid;
t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);
if(t[mid].ls) t[t[mid].ls].fa=mid,pushup(mid,t[mid].ls);
if(t[mid].rs) t[t[mid].rs].fa=mid,pushup(mid,t[mid].rs);
return mid;
}
void updata(int x,int y)
{
if(!x||t[x].sn[0]>R[0]||t[x].sm[0]<L[0]||t[x].sn[1]>R[1]||t[x].sm[1]<L[1]) return ;
pushdown(x);
if(t[x].sm[0]<=R[0]&&t[x].sn[0]>=L[0]&&t[x].sm[1]<=R[1]&&t[x].sn[1]>=L[1])
{
t[x].tag=t[x].col=y;
return ;
}
if(t[x].v[0]<=R[0]&&t[x].v[0]>=L[0]&&t[x].v[1]<=R[1]&&t[x].v[1]>=L[1]) t[x].col=y;
updata(t[x].ls,y),updata(t[x].rs,y);
}
inline int query(int x)
{
st[st[0]=1]=x;
while(t[st[st[0]]].fa) st[st[0]+1]=t[st[st[0]]].fa,st[0]++;
while(st[0]) pushdown(st[st[0]]),st[0]--;
return t[x].col;
}
void work()
{
n=rd(),rd(),m=rd();
memset(head,-1,sizeof(head)),cnt=0,ans=0;
int i,a,b,c;
for(i=2;i<=n;i++) fa[i]=rd(),add(fa[i],i);
dep[1]=1,dfs(1);
for(i=1;i<=n;i++) t[i]=kd(p[i],dep[i],i);
rt=build(1,n,0);
for(i=1;i<=m;i++)
{
a=rd(),b=rd(),c=rd();
if(!c) ans=(ans+(ll)i*query(pos[a]))%P;
else L[0]=p[a],R[0]=q[a],L[1]=dep[a],R[1]=dep[a]+b,updata(rt,c);
}
printf("%lld\n",ans);
}
int main()
{
int T=rd();
while(T--) work();
return 0;
}//1 4 3 7 1 2 2 3 0 0 2 1 3 3 0 0 1 0 2 2 0 0 4 1 1 4 0 0
【BZOJ4154】[Ipsc2015]Generating Synergy KDtree的更多相关文章
-
【bzoj4154】[Ipsc2015]Generating Synergy KD-tree
题目描述 给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色 输入 第一行一个数T,表示数据组数 接下来每组数据的第一行三个数n,c,q表示结 ...
-
【bzoj 4154】[Ipsc2015]Generating Synergy
题目 大概已经掌握熟练码出\(kdt\)的技能了 发现距离子树根节点\(x\)不超过\(l\)的点可以用两种方式来限制,首先\(dfs\)序在\([dfn_x,dfn_x+sum_x)\)中,深度自然 ...
-
【bzoj4154】(dfs序+kd-tree)
传送门 题意: 给出一颗以\(1\)为根的有根树,初始所有结点的颜色为\(1\). 之后有两个操作,一种是每次将距离\(a\)结点距离不超过\(l\)的所有儿子结点颜色染为\(c\):另一种是询问结点 ...
-
BZOJ 4154: [Ipsc2015]Generating Synergy KDtree+dfs序
多组数据真tm恶心~ 把 $dfs$序和深度分别看作横纵坐标,然后用 $KDtree$ 数点就可以了~ #include <cstdio> #include <cstring> ...
-
BZOJ4154:[IPSC2015]Generating Synergy
浅谈\(K-D\) \(Tree\):https://www.cnblogs.com/AKMer/p/10387266.html 题目传送门:https://lydsy.com/JudgeOnline ...
-
【BZOJ4155】[Ipsc2015]Humble Captains 最小割+DP
[BZOJ4155][Ipsc2015]Humble Captains Description 每天下午放学时都有n个zky冲出教室去搞基.搞基的zky们分成两队,编号为1的zky是1号队的首领,编号 ...
-
【BZOJ4066】简单题(KD-Tree)
[BZOJ4066]简单题(KD-Tree) 题面 BZOJ 题解 如果这题不卡空间,并且不强制在线的话 显然可以用\(CDQ\)分治做 但是它又卡空间又强制在线,于是我们欢快的来用\(KD-Tree ...
-
【BZOJ2648】SJY摆棋子 KDtree
[BZOJ2648]SJY摆棋子 Description 这天,SJY显得无聊.在家自己玩.在一个棋盘上,有N个黑色棋子.他每次要么放到棋盘上一个黑色棋子,要么放上一个白色棋子,如果是白色棋子,他会找 ...
-
【kd-tree】bzoj4154 [Ipsc2015]Generating Synergy
区间修改的kd-tree,打标记,下传. 每次询问的时候,从询问点向上找到根,然后依次下传下来,再回答询问. #include<cstdio> #include<algorithm& ...
随机推荐
-
【基础】Html跨域跳转问题整理
今天遇到一个问题,是有关 跨域跳转问题,涉及到知识比较基础. 具体问题是: A站点的 PageA (Post数据)到 B站点的 PageB,PageB接受到后Redirect到B站的 PageC: ...
-
SQLServer处理行转列和列转行
掌握SQL Server 行转列和列转行 1.列转行 数据经过计算加工后会直接生成前端图表需要的数据源,但是程序里又需要把该数据经过列转行写入中间表中,下次再查询该数据时直接从中间表查询数据. 1.1 ...
-
关于HBase的概述
1.hbase的特点 ->数据存储量可以达到亿级别数据维持在秒级 ->按列存储的数据库 ->能够存储上百万列 ->hbase的底层存储依赖于HDFS ->如何扩展hbas ...
-
XAMPP 在windows下无法启动Apache解决方案
XAMPP 在windows下无法启动Apache解决方案 一.现象 XAMPP 点击Start Apache时出现如下错误 20:41:12 [Apache] Error: Apache shut ...
-
Java7新特性(一)Coin
1.语法糖 数字下划线 2.switch语句中的String 3.multicatch 4.final重抛 对比上份代码 5.try-with-resources(TWR) AutoC ...
-
ContentProvider总结(Android)
ContentProvider 1.适用场景 1) ContentProvider为存储和读取数据提供了统一的接口 2) 使用ContentProvider,应用程序能够实现数据共享 3) andro ...
-
Python-web应用 +HTTP协议 +web框架
web架构 # web应用 架构# C/S 架构 | B/S 架构# client server: 客户端服务器架构,C++# browser server:浏览器服务器架构,Java.Python ...
-
flask中如何生成迁移文件
在flask网站开发中,如果直接对数据库进行修改的话,风险比较高,最好的是由迁移文件生成,这样确保了数据的误操作. 在Flask中可以使用Flask-Migrate扩展,来实现数据迁移.并且集成到Fl ...
-
I/O dempo
标准读取写入 package io_stream; import java.io.BufferedInputStream; import java.io.BufferedOutputStream; i ...
-
【摘录】在Windows平台上使用Objective-C
虽然到目前为止最好的Objective-C 编码平台来自苹果公司,但它们绝不仅适用于苹果公司的平台.Objective-C 在Linux.BSD 甚至Windows 等其他平台都有相当久远的历史.根据 ...