珂朵莉树是基于set的数据结构，与线段树、平衡树等树形结构类似，珂朵莉树是用来解决区间问题的很暴力的树形结构该数据结构支持区间推平，即将区间\([l,r]\)赋值为同一个值1.前置知识setset本质是平衡树，所以不会出现重复的元素且会自动排序，部分函数：set<Node>t;//定

颜色段均摊反正ODT！对于ODT来说，其区间推平的复杂度是\(O((n+m)\logn)\)的，十分的优秀，但是对于查询来说，我们需要通过分块或者线段进行辅助，从而达到正确的复杂度。有一种特殊情况例外：如果推平和查询同时发生，意味着推平时对于每一段查询的复杂度是没有问题的！判断是否

lxl学长讲课笔记常数种可能性的状态通过预先处理多种状态的信息，从而快速的转换状态。经典操作：flip。分析信息的思路利用线段树利用线段树的时候，如何合并两个分支区间的信息，我们需要有如下注意：答案-依赖的信息，继续的依赖，这样就能找到需要维护的东西。这终会产生闭包

珂朵莉树的复杂度分析CF896C珂朵莉树起源题LG4979矿洞：坍塌珂朵莉树可以在区间覆盖时顺便把左右的同色段合并了，这样任意时刻相邻的两段都不同色本题询问时判断\([l,r]\)是否同色就可以通过判断\([l,r]\)是否在同一段实现了https://www.luogu.com.cn/problem/P8146

UOJ191Unknown你需要维护一个向量序列，支持如下操作：在末尾加入一个向量\((u,v)\)。删除末尾的向量。询问\([l,r]\)内的向量与\((x,y)\)叉积的最大值。\(n,m\le5e5\)。这个东西我们首先一眼用李超树或者维护凸包来做全局询问最大值的子问题。考虑怎么把\([l,r]\)

GSS4-CanyouanswerthesequeriesIV操作\(1\)：\(a_i=\sqrt{a_i},i\in[l,r]\)操作\(2\)：询问\(\sum_{i=l}^ra_i\)开根号无法使用tag的方式维护，因为开根号后不确定减去多少，无法维护\(\suma_i\)。\(a_i=2^{\loga_i}\)，每次开根号后\(\loga_i\)会减半，操作\(\log\l

首先有一个结论，树中存在一个深度\(dep\)，使得深度小于等于\(dep\)的点只需\(dep\)次覆盖完，而大于\(dep\)的除最后一次外其他每次都可以填充\(k\)次。证明：在\(dep

7.30~7.50啥也不会，摆大烂。8.00~8.30T3应该是经典容斥，但是转移顺序怪怪的。似乎走到每个点的组合唯一，然后组成新的坐标系就能做了。8.30~9.50细节比较多，调了半天。1

朴素分析直接暴力统计计算次数。摊还分析聚合分析核心思想：算出总复杂度然后均摊。例：1.“栈”：维护一个栈，支持栈顶插入和一次弹出所有元素。显然\(n\)次

1.CF1774F1考虑一个repeat操作发生了甚么：假设现在全局一共扣除了\(m\)的血量，现在所拥有的猪的集合\(S\)那么操作相当于把所有\(S\)中的猪的血量去掉\(m\)扔进

一。专业术语本金利息利率等额本息：利息均摊，先息后本，每个月固定等额本金：长期利息少，按剩余本金均摊二。项目介绍P2P借贷平台 

珂朵莉树，又名ODT。暴力数据结构。前置芝士会用STL的set就行。原理珂朵莉树把一个区间看做一个节点扔到set里来保证随机情况下的复杂度。所以这玩意其实叫颜色段均摊。