关键词：
「模板」 树套树
线段树套 SBT。
有生以来写过的最长代码。
虽然能过，但我删除 SBT 点的时候没回收内存！写了就 RE！
先放上来吧，回收内存调出来了再修改qwq。
#include <algorithm>
#include <climits>
#include <cstdio>
using std::max;
using std::min;
const int MAXN=50010;
int n,m;
class SegmentTree
private:
int a[MAXN];
class SBT
private:
struct Node
int v,size;
Node *c[2];
Node(int v):v(v),size(1)
c[0]=c[1]=nullptr;
~Node(void)
if(c[0]!=nullptr)
delete c[0];
if(c[1]!=nullptr)
delete c[1];
int Size(bool p)
return c[p]!=nullptr ? c[p]->size : 0;
int SubSize(bool p,bool q)
return c[p]!=nullptr ? c[p]->Size(q) : 0;
void Update(void)
size=Size(0)+Size(1)+1;
*rt;
void Rotate(Node* &i,bool p)
Node *t=i->c[!p];
i->c[!p]=t->c[p];
t->c[p]=i;
i->Update();
(i=t)->Update();
void Maintain(Node* &i,bool p)
int t=i->Size(!p);
if(t<i->SubSize(p,p))
Rotate(i,!p);
else if(t<i->SubSize(p,!p))
Rotate(i->c[p],p);
Rotate(i,!p);
else
return;
Maintain(i->c[0],0);
Maintain(i->c[1],1);
Maintain(i,0);
Maintain(i,1);
void Insert(Node* &i,int x)
if(i==nullptr)
i=new Node(x);
return;
bool p=x>i->v;
++i->size;
Insert(i->c[p],x);
Maintain(i,p);
void Delete(Node* &i,int x)
if(i==nullptr)
return;
if(x==i->v)
if(i->c[1]==nullptr)
Node *t=i->c[0];
delete i;
i=t;
return;
else
Node *t=i->c[1];
while(t->c[0]!=nullptr)
t=t->c[0];
i->v=t->v;
Delete(i->c[1],t->v);
else
Delete(i->c[x>i->v],x);
i->Update();
public:
SBT(int* a,int l,int r):rt(nullptr)
for(int i=l;i<=r;++i)
Insert(a[i]);
~SBT(void)
delete rt;
void Insert(int x)
Insert(rt,x);
void Delete(int x)
Delete(rt,x);
int Rank(int x)
int ans=1;
Node *i=rt;
while(i!=nullptr)
if(x>i->v)
ans+=i->Size(0)+1;
i=i->c[1];
else
i=i->c[0];
return ans-1;
int Prev(int x)
int ans=-INT_MAX;
Node *i=rt;
while(i!=nullptr)
if(x>i->v)
ans=max(ans,i->v);
i=i->c[1];
else
i=i->c[0];
return ans;
int Next(int x)
int ans=INT_MAX;
Node *i=rt;
while(i!=nullptr)
if(x<i->v)
ans=min(ans,i->v);
i=i->c[0];
else
i=i->c[1];
return ans;
;
struct Node
SBT *T;
int l,r;
Node *c[2];
Node(SBT* T,int l,int r):T(T),l(l),r(r)
c[0]=c[1]=nullptr;
~Node(void)
delete T;
if(c[0]!=nullptr)
delete c[0];
if(c[1]!=nullptr)
delete c[1];
*rt;
void Build(Node* &i,int l,int r)
i=new Node(new SBT(a,l,r),l,r);
if(l^r)
int mid=l+r>>1;
Build(i->c[0],l,mid);
Build(i->c[1],mid+1,r);
int Rank(Node* i,int l,int r,int k)
if(l==i->l && r==i->r)
return i->T->Rank(k);
int mid=i->l+i->r>>1;
if(r<=mid)
return Rank(i->c[0],l,r,k);
else if(l>mid)
return Rank(i->c[1],l,r,k);
else
return Rank(i->c[0],l,mid,k)+Rank(i->c[1],mid+1,r,k);
void Modify(Node* i,int pos,int k)
i->T->Delete(a[pos]);
i->T->Insert(k);
if(pos==i->l && pos==i->r)
return;
int mid=i->l+i->r>>1;
if(pos>mid)
Modify(i->c[1],pos,k);
else
Modify(i->c[0],pos,k);
int Prev(Node* i,int l,int r,int k)
if(l==i->l && r==i->r)
return i->T->Prev(k);
int mid=i->l+i->r>>1;
if(r<=mid)
return Prev(i->c[0],l,r,k);
else if(l>mid)
return Prev(i->c[1],l,r,k);
else
return max(Prev(i->c[0],l,mid,k),Prev(i->c[1],mid+1,r,k));
int Next(Node* i,int l,int r,int k)
if(l==i->l && r==i->r)
return i->T->Next(k);
int mid=i->l+i->r>>1;
if(r<=mid)
return Next(i->c[0],l,r,k);
else if(l>mid)
return Next(i->c[1],l,r,k);
else
return min(Next(i->c[0],l,mid,k),Next(i->c[1],mid+1,r,k));
public:
SegmentTree(int n):rt(nullptr)
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
Build(rt,1,n);
~SegmentTree(void)
delete rt;
void Rank(void)
int l,r,k;
scanf("%d %d %d",&l,&r,&k);
printf("%d\n",Rank(rt,l,r,k)+1);
void Find(void)
int l,r,k,left=0,right=int(1e8),mid;
scanf("%d %d %d",&l,&r,&k);
while(left<right)
int mid=left+right>>1;
if(k>Rank(rt,l,r,mid))
left=mid+1;
else
right=mid;
printf("%d\n",left-1);
void Modify(void)
int pos,k;
scanf("%d %d",&pos,&k);
Modify(rt,pos,k);
a[pos]=k;
void Prev(void)
int l,r,k;
scanf("%d %d %d",&l,&r,&k);
printf("%d\n",Prev(rt,l,r,k));
void Next(void)
int l,r,k;
scanf("%d %d %d",&l,&r,&k);
printf("%d\n",Next(rt,l,r,k));
;
int main(int argc,char** argv)
scanf("%d %d",&n,&m);
static SegmentTree *T=new SegmentTree(n);
for(int i=1,opt;i<=m;++i)
scanf("%d",&opt);
switch(opt)
case 1:
T->Rank();
break;
case 2:
T->Find();
break;
case 3:
T->Modify();
break;
case 4:
T->Prev();
break;
case 5:
T->Next();
break;
T->Print();
delete T;
return 0;
谢谢阅读。
bzoj3196树套树模板
然而我还是在继续刷水题。。。 终于解开了区间第k大的心结。。。 比较裸的线段树套平衡树，比较不好想的是求区间第k大时需要二分一下答案，然后问题就转化为了第一个操作。复杂度nlog3n。跑的比... 查看详情
luogu3380模板二逼平衡树（树套树）
#include<iostream>#include<cstdlib>#include<cstdio>#include<ctime>usingnamespacestd;intn,m,cnt,a[50005],rot[200005],opt,ans,uu,vv,ww;structNode{intl,r,siz,hav,val,rnd;}nd[40000 查看详情
树套树初探(代码片段)
最近学了学树套树，做了几道模板题。发现好像有点水咳咳咳。树套树，顾名思义，一个树套一个树。比如树状数组套平衡树，就是把树状数组的每一个结点作为一颗平衡树，线段树套权值线段树，就是一颗线段树，每一个结点... 查看详情
「luogu3380」模板二逼平衡树（树套树）(代码片段)
「luogu3380」【模板】二逼平衡树（树套树）传送门我写的树套树——线段树套平衡树。线段树上的每一个节点都是一棵( extFHQTreap)，然后我们就可以根据平衡树的基本操作以及线段树上区间信息可合并的性质来实现了，具体细节... 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情
洛谷p3380模板二逼平衡树（树套树，树状数组，线段树）(代码片段)
洛谷题目传送门emm。。。题目名写了个平衡树，但是这道题的理论复杂度最优解应该还是树状数组套值域线段树吧。就像dynamicranking那样（蒟蒻的Sol,放一个link骗访问量233）所有的值（包括初始a数组，操作1、3、4、5的k）全部先... 查看详情
模板二逼平衡树（树套树）(代码片段)
题面题解过年的假期里肯定要用硬核数据结构打发时间啊所以我大胆尝试，用了一种速度不能算最快但是码量绝对是很大的一种方法居然控制在了6KB以内线段树套红黑树（逃这是一次前所未有的尝试因为线段树套平衡树求区间第... 查看详情
树套树
树套树，顾名思义，就是用一颗树套在另外一组树之上。比方说我们有一颗树，假如它的每一个结点（抽象意义上，一株树由多个结点组成）也是一株树，那么这就形成了树套树。外部树和内部树可以是不同品种的。一般外... 查看详情
树套树(代码片段)
树套树一种思想，就是一棵树的节点是另一颗树。在外面的叫外层树，在里面的叫内层树。外层树一般是，树状数组，线段树内层树一般是平衡树，STL,线段树线段树套STL/**@Author:zhl*@Date:2020-11-1612:50:32*/#include<bits/stdc++.h>#define... 查看详情
[模板]洛谷t3380二逼平衡树线段树套splay
...攻克了二分求K大的难题。。。特此纪念10.3好好的树套树模板题怎么没有一份线段树套平衡树的“标准”题解呢。。。虽然这方法比较low，但我还是来贴一发。。。据说这题常数巨大，若干份线段树套BST的代码都被卡常了萌新我... 查看详情
树套树三题题解
...这题数据非常水……从O(nlogn)的主席树到O(nlog3n)的树套树+二分到O(nsqrt(n)log2n)的分块套二分套二分到O(n2)的暴力都能过……)鉴于这就是动态排名系统的静态版，就不说了，贴代码：线段树套平衡树：#include 查看详情
uvalive-6709树套树(代码片段)
...法：暴力可过，建n颗线段树暴力更新，但是正解应该是树套树，树套树需要注意的是当建树或修改时pushup操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过... 查看详情
树套树乱讲
树套树乱讲树状数组套线段树先学会主席树。主席树可以被理解为一个二维平面，其中n棵树可以视作横轴，每棵树中的坐标范围（也就是线段树的坐标范围）可以视作纵轴。这样一来就是用主席树维护了一些在二维平面上的点... 查看详情
树套树乱讲的代码(代码片段)
树套树乱讲的代码由于部分代码的完成时间较早所以码风可能有些差异，敬请谅解。动态区间Kth题面整体二分题解#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>usingnamespacestd;constintN=10005 查看详情
hdu4819mosaic树套树(代码片段)
...点变成这个矩形中最大值和最小值的平均数思路很显然的树套树啊就是一开始傻逼了没想到怎么去维护这个东西其实很简单对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度(O(log(n)))voidmodify_y(intt,intl... 查看详情
[bzoj720][jzyzoj2016]gty的妹子树强制在线树分块/树套树
jzyzoj的p2016先码着,强制在线的树分块或者树套树?关键是我树分块还在入门阶段树套树完全不会啊摔 http://blog.csdn.net/jiangyuze831/article/details/41445003果然我除了抄代码什么也不会......树分块之类的东西完全不会计算复杂度.....似... 查看详情
树套树day2
滚回来更新,,,在Day1我们学了最基本的线段树套平衡树Day2开始我们要学习一些黑科技（所以很大概率会出现Day3w1.线段树上的黑科技 这一段我们分几项来讲1.权值线段树 权值线段树以权值为下标建树（就像求逆序对时... 查看详情
bzoj2141排队[国家集训队2011]排队(魏铭)树套树线段树套替罪羊树
这个题就是动态偏序对，每次操作做两个删除两个插入就好了。#include<cstdio>#include<iostream>#include<cstring>#defineMAXN100010usingnamespacestd;typedeflonglongLL;typedefdoubleD;constDa=0.756;LLans;structScapeGoat 查看详情