线段树题单记录线段树的题都很板的，模板敲上去再改改就行有的题你用的线段树可能都可以删除一部分并正常使用TODO【模板】线段树1【模板】线段树2[JSOI2008]最大数[ABC357F]TwoSequenceQueries方差[COCI2010-2011#6]STEP贪婪大陆全村最

首先我们亲爱的zyr同学在2道几乎一样的括号序列题上面用了2种不同的方式来维护pushup，而这和每道题题解的趋势几乎一致。但是我直接交的他的代码。所以写一下zyr队爷的思路。以下直接设(为\(1\)，)为\(-1\)。一、结论法答案为右最大前缀和-左最小后缀和。（跨越

过程线段树分裂是线段树合并的逆操作，即将一个区间信息分裂到新的树中，新的树一般需要新建。注意当分裂和合并都存在时，我们在合并的时候必须回收节点，以避免分裂时会可能出现节点重复占用的问题。时间复杂度显然\(\mathcal{O}(\logn)\)。实现//将x分裂出[p,q]到now上v

//Problem://P1712[NOI2016]区间////Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1712//MemoryLimit:250MB//TimeLimit:1000ms////PoweredbyCPEditor(https://cpeditor.org)#include<iostream>#include<algorithm

前言:为什么把他们放在一起?因为我发现把pushup向上回溯放结构体类型函数里比较方便并且这两题确实也有相同思想山海经这题分三种情况左子树前缀和+右子树前缀和2.右子树后缀和与右总区间+左子树3.左区间最大子段与右区间最大子段与左后缀与右前缀特别要注意

01trie定义01-trie是字符集为0，1的trie，可以维护异或极值，维护异或和实现主体仍然是trie，维持\(t\)数组记录儿子不变。需要因为异或的性质，所以只需要维护加入0/1边的奇偶性即可，所以添加\(w\)数组记录父节点到该节点的边数。此外因为要统计异或和，所以要在树上统计，用\(xorv

可以通过这道题#include<bits/stdc++.h>#defineRregisterint#defineIinlinevoid#defineGif(++ip==ie)if(fread(ip=buf,1,SZ,stdin))#definelcc[x][0]#definercc[x][1]usingnamespacestd;constintSZ=1<<19,N=3e5+9;charbuf[SZ],*ie=buf+SZ,*ip=

Splay树定义Splay是一种高效的BST，平摊复杂度为\(O(\logn)\)，可以快速访问热数据rotate+splay精华部分splay双旋一字旋：先fa再x之字旋：先x再fa旋根操作：最麻烦的地方，注意y每次循环要给他赋值voidrotate(intx){ inty=t[x].fa,z=t[y].fa,k=t[y].son[1]==x; t[y].son[k

居然差一点场切了。首先可以将两棵树上对应的点看作一个点的两个不同状态考虑一个类似最短路的东西：设\(dis_{i,j,0/1,0/1}\)为树上\(0/1\)状态的\(i\)点到\(0/1\)状态的最短路。考虑怎样维护这个值。由于是树上路径问题，容易发现设\(k\)为树上\((i,j)\)路径上任意一

这是本蒟蒻写的第一篇题解（写不好请指出）很明显他是一道dp题，因为第i本书放哪里只跟前i-1本树的放法有关系。我们可以是定义f[i][j]表示放了i本书，最后一层书架是以第j本书开始的。那么有动态转移方程：\(f[i][i]=min(f[i-1][j])+hi,w[j]+...+w[i-1]<=L\)\(f[i][j]=f[i-1][j]+max(0

标记永久化：要求修改必须顺序无关满足区间贡献独立多标记好像也不适用如果对于指定区间的修改可以在与当前区间仅仅是相交而不是包含的情况下可以直接完成，就不需要pushup

前言我们都知道动态开点权值线段树的空间复杂度是\(O(n\logV)\)的，但是很多题目中这样的空间是会被卡的，那我们能不能优化呢？实现看看下面这一棵树：在上图中，红色节点使我们平常会开的点。但是我们发现，其实只要维护绿色的点和红色的叶子结点。其实，绿色节点就是所有叶子结点

来一发\(O(\logn)\)线性空间的解法。考虑通过只维护线段树叶子节点的虚树的方法压缩空间，考虑记录下每个节点的编号，然后通过异或完求最低位的\(1\)的方式求出LCA的深度，然后记录下LCA右端点的编号。在回收节点的时候可以释放储存右端点编号的空间，但是这里为了方便就不这样

前情提要前言相信大家都听说过\(\text{Splay}\)的常数大。相信大家都听说过\(\text{FHQ-Treap}\)的常数小。但是现在我要说的是：你说得对，但是你说得不对。所谓常

一种更简单的想法，只用用分块思想（或者根号分治？）不用分块。先考虑暴力怎么做：修改直接改，查询不停跳下一个点。但这样会被卡到\(O(n^2)\)。考虑分块思想优化：如果保证每次至少

题目链接题目描述：给定一个长度为\(~\)n\(~\)的字符序列\(~\)a，初始时序列中全部都是字符\(~\)L。有\(~\)q\(~\)次修改，每次给定一个\(~\)x，做出如下变化：\(~~\)1.a\(_

题目链接题目大意：\(~~\)初始给定一个长度为n的字符序列a,初始序列中全是\(~\)L\(~~\)共有q次修改，修改a\(_{x}\)为：L\(\rightarrow\)\(~~\)or\(~~\)R\(\rightarrow\)L\(