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

珂朵莉树 ODT

能干什么/局限性

高效处理区间平推(区间赋值)的问题。

在随机数据下飞快。

如果没有区间平推,或者区间平推的操作数量可以被卡得很少甚至没有,就不适用。

前置知识

  • set

没了。

建点

每个点要维护一个区间,以及这个区间的信息。表示这个区间的信息都是相等的。

所有的点维护的区间都没有交集,且并集就是的区间就是 \(1\sim n\)

struct node{int l,r; //维护的区间mutable int val; //维护的信息//mutable 表示可以直接在 set 中修改node(int L,int R=-1,int VAL=0){l=L,r=R,val=VAL;}bool operator<(const node&other)const{return l<other.l;}
};
set<node> odt;

分裂(split)

传进去一个参数 \(pos\),表示把包含 \(pos\) 的区间 \([l,r]\),分裂成 \([l,pos-1]\)\([pos,r]\),并返回后一个区间的迭代器。

特别地,若 \(pos\) 所在的区间的左端点就是 \(pos\),那么不分裂直接返回这个区间。

auto split(int pos){auto it=odt.lower_bound(node(pos));if(it!=odt.end() && it->l==pos) return it; //特判it--;int l=it->l,r=it->r,val=it->val;odt.erase(it);odt.insert(node(l,pos-1,val)); //每个点维护的区间信息都是相同的return odt.insert(node(pos,r,val)).first;
}

平推(assgin)

如果只分裂那肯定是不行的,复杂度只会越来越高。

平推就是可以把一堆区间赋值成相同的,就可以合并起来。这也是 ODT 必须要有的平推操作,而且这也关乎到复杂度。

void assgin(int l,int r,int k){auto itr=split(r+1),itl=split(l);odt.erase(itl,itr);odt.insert(node(l,r,k));
}

所有的 ODT 的题必须要有的操作就这俩。

剩下的就全看实际题目了。

http://www.hskmm.com/?act=detail&tid=24315

相关文章:

  • 2025多校CSP模拟赛2
  • 详细介绍:深入了解linux网络—— 基于UDP实现翻译和聊天功能
  • Rewind: Codeforces Round 1055 (Div.1+Div.2)
  • 10.4模拟赛总结
  • 01.linux基础
  • 英语完形填空
  • 2025整体橱柜厂家TOP企业品牌推荐排行榜,云南昆明整体橱柜全瓷砖,开放式厨房,经济型,一站式无烟柴火灶,嵌入式,智能,多功能,全屋无烟柴火灶整体橱柜公司推荐
  • Centos7安装mysql8
  • vite-vue3脚手架(参考帝莎编程-后台管理系统开发)
  • 上传文件的后端程序handleFileUpload()、getOriginalFilename()、UUID
  • 从模拟入侵到渗透测试:我摸清了黑客的套路,也懂了企业的软肋 - 详解
  • 同样的Python代码,在Windows上运行没有错误,在Linux Centos上运行出行错误。
  • FreeBSD 14发布后的技术问题解析
  • handleFileUpload()
  • 实用指南:Typescript高级类型详解
  • 集合幂级数,FMT 与 FWT 学习笔记
  • 2025多校CSP模拟赛1
  • 上传文件前端需要注意的三个点:
  • AT_arc189_b [ARC189B] Minimize Sum
  • Jenkins安装与配备
  • 2025-10-04 60S读世界
  • 适合新手的PPT模板网站,简单操作但效果好!
  • 2025多校冲刺CSP模拟赛2 总结
  • pip list 可以查到某个包,但是,import某个包,出现 ModuleNotFoundError: No module named
  • 详细介绍:conda使用指南
  • 探索 Docker/K8s 部署 MySQL 的创新实践与优化技巧 - 详解
  • 基于Registry搭建docker加速镜像服务
  • mssql 无锁读取
  • 2025年四川大学计算机学院专硕考研经验分享
  • 基础数学拾遗