新闻详情

新闻详情

首页 / 资讯中心 / 详情

P9527 [JOIST 2022] 洒水器 / Sprinkler 题解

发布时间:2026/11/16 8:19:23来源:尧图网络
P9527 [JOIST 2022] 洒水器 / Sprinkler 题解
P9527 [JOIST 2022] 洒水器 / Sprinkler 题解注意力惊人思路首先我们注意到Dk≤40D_k\le40Dk​≤40所以考虑暴力一些的解法。每次直接遍历所有相邻的点肯定是不行的但我们注意到与每个节点距离不超过DkD_kDk​的祖先至多有DkD_kDk​个所以考虑对祖先进行操作。考虑操作一个点会对哪些点产生影响。首先肯定会对子树内的点产生影响设tagx,itag_{x,i}tagx,i​表示对xxx的子树内与xxx距离不超过iii的点的标记那么直接对tagx,dtag_{x,d}tagx,d​加标记即可。然后考虑对祖先及其子树内节点的影响。注图片及后文的ddd是指当次修改的范围DkD_kDk​。如图所示我们只需要对tagfx,d−(depx−depfx)tag_{fx,d-(dep_x-dep_{fx})}tagfx,d−(depx​−depfx​)​乘上WWW并对tagy,d−(depx−depfx)−1tag_{y,d-(dep_x-dep_{fx})-1}tagy,d−(depx​−depfx​)−1​除去WWW即可。然后每次查询就只需要暴力往上跳祖先累计答案即可。但是此时有个严峻的问题就是题目没有保证模数一定与WWW互质那么我们就无法使用逆元了而且常数还很大所以我们要找到一种方法每次修改查询只用乘。我们注意似乎每次打标记都会打很多重复的标记考虑修改xxx时我们每次修改它的祖先每个祖先yyy除根节点外都会被修改两次一次是给以它为根的子树打上标记一次是给它父节点去掉x−fxx-fxx−fx的标记。第一次修改的是将tagy,d−(depx−depy)tag_{y,d-(dep_x-dep_y)}tagy,d−(depx​−depy​)​乘WWW第二次修改的是将tagy,d−(depx−depfx)−1tag_{y,d-(dep_x-dep_{fx})-1}tagy,d−(depx​−depfx​)−1​即tagy,d−(depx−depy)−2tag_{y,d-(dep_x-dep_y)-2}tagy,d−(depx​−depy​)−2​除WWW这似乎像一个前缀和形式于是此时我们去掉重复修改的部分即[0,d−(depx−depy)−2][0,d-(dep_x-dep_y)-2][0,d−(depx​−depy​)−2]惊人的发现此次修改只对yyy的子树中与yyy的距离在[d−(depx−depy)−1,d−(depx−depy)][d-(dep_x-dep_y)-1,d-(dep_x-dep_y)][d−(depx​−depy​)−1,d−(depx​−depy​)]的节点有影响而且对于xxx本身也是符合这个条件的所以我们将tagx,itag_{x,i}tagx,i​的状态改为对xxx的子树内与xxx距离恰好为iii的点的标记那么每次修改时只需要把xxx及其祖先的tagy,d−(depx−depy)tag_{y,d-(dep_x-dep_y)}tagy,d−(depx​−depy​)​和tagy,d−(depx−depy)−1tag_{y,d-(dep_x-dep_y)-1}tagy,d−(depx​−depy​)−1​改一下即可。需要注意的是对于根节点由于它没有父节点所以他的标记还是距离为[1,d−(depx−depy)][1,d-(dep_x-dep_y)][1,d−(depx​−depy​)]的所以对于根节点要全部距离≤d−(depx−depy)\le d-(dep_x-dep_y)≤d−(depx​−depy​)的tagrttag_{rt}tagrt​都要修改一遍。查询就暴力往上跳ddd个祖先yyy每次记录一下tagy,depx−depytag_{y,dep_x-dep_y}tagy,depx​−depy​​即可。由于d≤40d\le 40d≤40每次跳的祖先不超过 40对于修改的根节点最多只有一个最多改ddd个距离的标记所以单次修改和查询的时间复杂度都为O(d)O(d)O(d)总时间复杂度为O(nqd)O(nqd)O(nqd)。代码#includebits/stdc.husingnamespacestd;typedeflonglongll;intn,mod;//节点数量及模数vectorintG[200010];ll h[200010]/*初始每个点的高度*/,tag[200010][42]/*题解中的tag数组*/;intfa[200010];//每个点的父节点voiddfs(intx,intxfa){//记录每个节点的父节点fa[x]xfa;for(inty:G[x])if(y!xfa){dfs(y,x);}}voidsolve(intX,intd,intval){//修改intxX;while(d0x){tag[x][d]tag[x][d]*val%mod;//修改tag[y][d-(dep[x]-dep[y])]if(d-10)tag[x][d-1]tag[x][d-1]*val%mod;//修改tag[y][d-(dep[x]-dep[y])-1]if(!fa[x])for(inti0;id-2;i)tag[x][i]tag[x][i]*val%mod;//特判根节点的情况xfa[x];//往上跳d--;}}llquery(intx){//查询ll ansh[x];for(inti0;i40x;i){//往上跳40个祖先ansans*tag[x][i]%mod;//记录当前祖先对x的标记xfa[x];//往上跳}returnans;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinnmod;for(inti1,x,y;in;i){cinxy;G[x].push_back(y);G[y].push_back(x);}dfs(1,0);for(inti1;in;i)cinh[i];for(inti1;in;i)for(intj0;j40;j)tag[i][j]1;//记得初始化为1intQ;cinQ;while(Q--){intop;cinop;if(op1){intx,d,v;cinxdv;solve(x,d,v);}else{intx;cinx;coutquery(x)\n;}}return0;}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/14 10:11:15

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/15 4:06:36

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉