当前位置: 首页 > news >正文

「LG7446-rfplca」题解

P7446 [Ynoi2007] rfplca

sol

考虑如何找 LCA,通常来说我们会使用倍增,然而这道题带修,因此倍增不可实现。

考虑对序列分块,每个点维护其父亲以及其最近的不与其在同一块中的祖先,散块重构是简单的,但貌似无法整块修改?不难发现,一个块被操作块长次后,其内每个点的父亲在块外了,因此每个整块前块长次操作暴力重构,后面直接维护 \(\sum x\) 这个标记,查询更新父亲即可。

令块长为 \(\sqrt n\),则复杂度为 \(O(n\sqrt n)\)

想到整块修改的处理方式之后就没什么了,但整块修改这个维护方式对于我这种不特别擅长分块的蒟蒻来说可能还是没那么好想。

code

const int N=4e5+5,B=640;int n,m;
int a[N],b[N];
int L[B],R[B],id[N];ll sum[B];
int tim[B];inline void Main(){cin>>n>>m;rep(i,2,n)cin>>a[i];rep(i,1,(n-1)/B+1){L[i]=(i-1)*B+1;R[i]=min(i*B,n);rep(j,L[i],R[i]){id[j]=i;b[j]=a[j];if(b[j]>=L[i])b[j]=b[b[j]];}}int ans=0;rep(t,1,m){int o;cin>>o;if(o==1){int l,r;ll x;cin>>l>>r>>x;l^=ans,r^=ans,x^=ans;if(id[l]==id[r]){int bd=id[l];rep(i,L[bd],R[bd])a[i]=max(1ll,a[i]-sum[bd]);sum[bd]=0;rep(i,l,r)a[i]=max(1ll,a[i]-x);rep(i,L[bd],R[bd]){b[i]=a[i];if(b[i]>=L[bd])b[i]=b[b[i]];}}else{int lb=id[l],rb=id[r];rep(i,L[lb],R[lb])a[i]=max(1ll,a[i]-sum[lb]);rep(i,L[rb],R[rb])a[i]=max(1ll,a[i]-sum[rb]);sum[lb]=sum[rb]=0;rep(i,l,R[lb]){a[i]=max(1ll,a[i]-x);b[i]=a[i];if(b[i]>=L[lb])b[i]=b[b[i]];}rep(i,L[rb],R[rb]){if(i<=r)a[i]=max(1ll,a[i]-x);b[i]=a[i];if(b[i]>=L[rb])b[i]=b[b[i]];}rep(bd,lb+1,rb-1)if(++tim[bd]<B){rep(i,L[bd],R[bd]){b[i]=a[i]=max(1ll,a[i]-x);if(b[i]>=L[bd])b[i]=b[b[i]];}}else sum[bd]+=x;}}else{int u,v;cin>>u>>v;u^=ans,v^=ans;if(tim[id[u]]>=B)b[u]=max(1ll,a[u]-sum[id[u]]);if(tim[id[v]]>=B)b[v]=max(1ll,a[v]-sum[id[v]]);while(b[u]!=b[v])if(b[u]>b[v]){u=b[u];if(tim[id[u]]>=B)b[u]=max(1ll,a[u]-sum[id[u]]);}else {v=b[v];if(tim[id[v]]>=B)b[v]=max(1ll,a[v]-sum[id[v]]);}while(u!=v)if(u>v)u=max(1ll,a[u]-sum[id[u]]);else v=max(1ll,a[v]-sum[id[v]]);put(ans=u);}}
}
http://www.hskmm.com/?act=detail&tid=36061

相关文章:

  • 图论刷题记录
  • 「LG6596-How Many of Them」题解
  • 骗我呢
  • 手写体识别
  • 你好,我是肆闲:C语言的学习,成长与分享旅程
  • AGC 合集 1.0
  • 20231302邱之钊密码系统设计实验一第二
  • 深入BERT内核:用数学解密掩码语言模型的工作原理
  • ZR 2025 NOIP 二十连测 Day 6
  • 20251021
  • [论文笔记] Precision-Guided Context Sensitivity for Pointer Analysis
  • 英语_备忘_疑难
  • 数学题刷题记录(数学、数论、组合数学)
  • 朋友圈文案不会写?这个AI指令可能帮得上忙
  • 「JOISC2020-掃除」题解
  • 结对作业
  • CF简单构造小计
  • 深入认识ClassLoader - 一次投产失败的复盘
  • python 包来源镜像
  • CSharp基础复习-1
  • Linux7种文件类型
  • 米理 课程描述/学习计划/Study program
  • 2025年线路调压器厂家推荐榜:10kv线路调压器/单相线路调压器/三相线路调压器/助力电网稳定运行,优选品牌指南
  • Day15
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳凭分区域光效领跑,生鲜 / 百货场景适配优选
  • 2025 艺考文化课推荐榜:济南震华学校 5 星领跑,全阶段体系适配基础补弱到高分冲刺
  • 2025 广州人力资源/派遣/劳务外包/人事代理/推荐榜:精典人才凭派遣合规 + 全场景适配领跑,企业用工优选
  • 2025 变电站厂家推荐榜最新资讯:撬装变电站/移动车载变电站/预制舱式变电站/移动变电站/预装式变电站/聚焦智能适配与可靠服务,这家企业成优选​
  • 题解:P12525 [Aboi Round 1] 私は雨
  • 完整教程:罗技G102有线鼠标自己维修教程