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

LGP5494 [LG TPLT] 线段树分裂 学习笔记

LGP5494 [LG TPLT] 线段树分裂 学习笔记

\(\texttt{Luogu Link}\)

前言

\(\texttt{Q:}\) 有什么数据结构是支持用合并&分裂查询答案信息的呢?
\(\texttt{A:}\) \(\text{FHQ-Treap}\)
\(\texttt{Q:}\) 还有吗?
\(\texttt{A:}\) 线段树。

—— \(\texttt{cyffff}\)

所以,来都来了,练了线段树合并,就也写一下线段树分裂吧。

因为实际上,一个能合并能分裂的 \(\text{SegTrees}\) 在功能上与一棵 \(\text{FHQ-Treap}\) 确实就相差的不太多了(来源请求)。

题意简述

给出一个可重集,编号为 \(1\),请支持以下五种操作:

  • 0 p x y:将 \(p\) 号可重集中所有 \([x,y]\) 范围的值移到一个新可重集(其编号等于之前生成过的可重集数量加一)中。
  • 1 p t:将 \(t\) 号可重集中的所有数放入 \(p\) 号可重集中,删除 \(t\)
  • 2 p x k:往 \(p\) 号可重集中加入 \(x\) 个数字 \(k\)
  • 3 p x y:查询 \(p\) 号可重集中值域在 \([x,y]\) 范围的数的个数。
  • 4 p k:查询 \(p\) 号可重集中第 \(k\) 小的数,若不存在则输出 -1

\(n,x,y,k,q,m\le 2\times 10^5\)。保证数据合法。

做法解析

如果没有 \(0\) 操作就是线段树合并(或平衡树)板子。所以这里只讲解 \(0\) 操作。

其实也很简单。我们把一只线段树按值域分成两半是很容易的,那把 \([x,y]\)split 出去也不难,就是劈两刀再把两边的拼回去。

哦为了空间不爆炸,记得回收用完的结点。

直接看代码吧。

代码实现

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=2e5+5;
int N,M,X,Opt,Y,Z;
int srt[MaxN],tcnt;
struct SegTrees{lolo sum[MaxN<<5];int ls[MaxN<<5],rs[MaxN<<5],tot;int pol[MaxN<<5],pcnt;void init(int n){for(int i=1;i<=n;i++)srt[i]=++tot;}int newnode(){return pcnt?pol[pcnt--]:++tot;}void delnode(int u){pol[++pcnt]=u,ls[u]=rs[u]=sum[u]=0;}void pushup(int u){sum[u]=sum[ls[u]]+sum[rs[u]];}void modify(int &u,int cl,int cr,int dd,int x){if(!u)u=newnode();if(cl==cr){sum[u]+=x;return;}int cmid=(cl+cr)>>1;if(dd<=cmid)modify(ls[u],cl,cmid,dd,x);else modify(rs[u],cmid+1,cr,dd,x);pushup(u);}lolo getsum(int u,int cl,int cr,int dl,int dr){if(dl<=cl&&cr<=dr)return sum[u];int cmid=(cl+cr)>>1;lolo res=0;if(dl<=cmid)res+=getsum(ls[u],cl,cmid,dl,dr);if(dr>cmid)res+=getsum(rs[u],cmid+1,cr,dl,dr);return res;}int qkth(int u,int cl,int cr,lolo k){if(cl==cr)return cl;int cmid=(cl+cr)>>1;if(sum[ls[u]]>=k)return qkth(ls[u],cl,cmid,k);else return qkth(rs[u],cmid+1,cr,k-sum[ls[u]]);}int merge(int u,int v){if(!u||!v)return u|v;sum[u]+=sum[v];ls[u]=merge(ls[u],ls[v]);rs[u]=merge(rs[u],rs[v]);delnode(v);return u;}void split(int u,int &v,lolo ck){if(!u)return;v=newnode();lolo lk=sum[ls[u]];if(ck>lk)split(rs[u],rs[v],ck-lk);else swap(rs[u],rs[v]);if(ck<lk)split(ls[u],ls[v],ck);sum[v]=sum[u]-ck,sum[u]=ck;}
}SgS;
int main(){readis(N,M);SgS.init(N),tcnt=1;for(int i=1;i<=N;i++)readi(X),SgS.modify(srt[1],1,N,i,X);for(int i=1;i<=M;i++){readi(Opt);if(Opt==0){readis(X,Y,Z);int tmp=0;lolo s1=Y>1?SgS.getsum(srt[X],1,N,1,Y-1):0;lolo s2=SgS.getsum(srt[X],1,N,Y,Z);SgS.split(srt[X],srt[++tcnt],s1);SgS.split(srt[tcnt],tmp,s2);srt[X]=SgS.merge(srt[X],tmp);}if(Opt==1)readis(X,Y),srt[X]=SgS.merge(srt[X],srt[Y]);if(Opt==2)readis(X,Y,Z),SgS.modify(srt[X],1,N,Z,Y);if(Opt==3)readis(X,Y,Z),writil(SgS.getsum(srt[X],1,N,Y,Z));if(Opt==4)readis(X,Y),writil(SgS.sum[srt[X]]>=Y?SgS.qkth(srt[X],1,N,Y):-1);}return 0;
}
http://www.hskmm.com/?act=detail&tid=36863

相关文章:

  • 股票操作统计分析报告 - 2025-10-22
  • 随笔测试
  • 文档智能信息抽取技术在金融财税领域的应用研究与发展前景
  • 今日策略:年化436%,回撤7%,夏普比5.28, deap因子挖掘重构,附python代码 - 详解
  • 51单片机实践之数码管电子时钟/时间呈现及其设置
  • vue2:v-if和v-show的区别以及造成的影响
  • P6845 题解
  • LGP3694 邦邦的大合唱站队 学习笔记
  • 2025.10.22学习记录
  • 衡量效率,质量,运维的效率指标
  • LeeCode_101对称二叉树
  • TRAE 设计团队如何玩转 Vibe Coding(上)|高美感页面生成篇
  • LeeCode_226反转二叉树
  • 2025多校冲刺CSP模拟赛7 总结
  • 详细介绍:wpf之 Popup
  • 结对项目-生成四则运算
  • ? #4
  • CSS3 超实用属性:pointer-events (可穿透图层的鼠标事件)
  • 类和对象
  • 取证-windbg和dmp,以及文件分析基本流程
  • 【比赛记录】2025CSP+NOIP 冲刺模拟赛合集Ⅱ
  • 羊驼二次免疫的六大风险:纳米抗体制备不可忽视的 “隐形陷阱”
  • 完整教程:C++项目:仿muduo库高并发服务器-------connection模块
  • 深入解析:线性代数 SVD | 令人困扰的精度 1
  • 营销数字化专家要求
  • 小程序反编译包的架构文件
  • 10.22 CSP-S模拟37/2025多校冲刺CSP模拟赛7 改题记录
  • [题解]P11126 [ROIR 2024] 三等分的数组 (Day 2)
  • Acrobat Pro DC 2025下载及破解安装教程,附永久免费免激活中文版Acrobat Pro DC安装包(稳定版)
  • VSLAM 十四讲--阅读中知识点记录