2020-2021:teams:hotpot:lotk_树套树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:lotk_树套树 [2020/05/08 16:18] lotk 创建 |
2020-2021:teams:hotpot:lotk_树套树 [2020/05/08 16:53] (当前版本) lotk [平衡树套线段树(替罪羊)] |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| 特别是涉及到区间翻转，分析后我们不难发现，在前驱后继，k在区间内的排名，排名为k的数的查询等操作，线段树套平衡树并不会比线段树套线段树更优。(查找排名为k的数由于二分甚至会多个$log$) | 特别是涉及到区间翻转，分析后我们不难发现，在前驱后继，k在区间内的排名，排名为k的数的查询等操作，线段树套平衡树并不会比线段树套线段树更优。(查找排名为k的数由于二分甚至会多个$log$) | ||
| - | 下面给出一道模板题[洛谷P3380 【模板】二逼平衡树（树套树）](https://www.luogu.com.cn/problem/P3380) | + | 下面给出一道模板题[[https://www.luogu.com.cn/problem/P3380|洛谷P3380 【模板】二逼平衡树（树套树）]] |
| 并没有找到带区间翻转和区间查询的题，读者如果有兴趣可以出一道（ | 并没有找到带区间翻转和区间查询的题，读者如果有兴趣可以出一道（ | ||
| 行 27: | 行 27: | ||
| 插入操作并没有什么难度，就是在插入的这个点的这条链上的平衡树都插入这个点，删除同理 | 插入操作并没有什么难度，就是在插入的这个点的这条链上的平衡树都插入这个点，删除同理 | ||
| - | ~~~cpp | + | <code cpp> |
| void insert(int x,int p,int w){ | void insert(int x,int p,int w){ | ||
| ins(tr[x].root,w); | ins(tr[x].root,w); | ||
| 行 42: | 行 42: | ||
| else Delete(x<<1|1,p,w); | else Delete(x<<1|1,p,w); | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===query=== | ===query=== | ||
| 行 48: | 行 48: | ||
| 关键的一步操作，我们将所要用到的平衡树的根放在一个vector里方便使用 | 关键的一步操作，我们将所要用到的平衡树的根放在一个vector里方便使用 | ||
| - | ~~~cpp | + | <code cpp> |
| vector<int> vec; | vector<int> vec; | ||
| void query(int x,int l,int r){ | void query(int x,int l,int r){ | ||
| 行 56: | 行 56: | ||
| query(x<<1|1,l,r); | query(x<<1|1,l,r); | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===pre/suc=== | ===pre/suc=== | ||
| 行 62: | 行 62: | ||
| 对于求前驱后继，我们就在每棵平衡树中求然后取最大最小即可。 | 对于求前驱后继，我们就在每棵平衡树中求然后取最大最小即可。 | ||
| - | ~~~cpp | + | <code cpp> |
| int Pre(int k){ | int Pre(int k){ | ||
| int ans=-INF; | int ans=-INF; | ||
| 行 75: | 行 75: | ||
| return ans; | return ans; | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===rank=== | ===rank=== | ||
| 行 81: | 行 81: | ||
| 每棵平衡树求rank相加 | 每棵平衡树求rank相加 | ||
| - | ~~~cpp | + | <code cpp> |
| int Rank(int k){ | int Rank(int k){ | ||
| int ans=0; | int ans=0; | ||
| 行 88: | 行 88: | ||
| return ans; | return ans; | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===kth=== | ===kth=== | ||
| 行 96: | 行 96: | ||
| 更重要的一点，要对一开始可能输入的值排序处理方便二分，不然二分增加的这个$log$偏大导致超时 | 更重要的一点，要对一开始可能输入的值排序处理方便二分，不然二分增加的这个$log$偏大导致超时 | ||
| - | ~~~cpp | + | <code cpp> |
| int calc1(int k){ | int calc1(int k){ | ||
| int ans=0; | int ans=0; | ||
| 行 118: | 行 118: | ||
| } | } | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===完整代码=== | ===完整代码=== | ||
| - | ~~~cpp | + | <code cpp> |
| #include<algorithm> | #include<algorithm> | ||
| #include<stack> | #include<stack> | ||
| 行 321: | 行 321: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ====平衡树套线段树(替罪羊)==== | ====平衡树套线段树(替罪羊)==== | ||
| 行 327: | 行 327: | ||
| 一开始想到平衡树套线段树会感到很奇怪，毕竟大部分的平衡树树形是会改变的，这样的话在改变的过程中同时维护线段树就很难实现。 | 一开始想到平衡树套线段树会感到很奇怪，毕竟大部分的平衡树树形是会改变的，这样的话在改变的过程中同时维护线段树就很难实现。 | ||
| - | ~~那么有没有这样一棵树，又能保持平衡，又能不轻易改变树形呢?~~ | + | <del>那么有没有这样一棵树，又能保持平衡，又能不轻易改变树形呢?</del> |
| 答案是有，替罪羊树完美保证了树形不轻易改变的性质，在重构的同时我们也重构我们的线段树，这样我们就能实现一种带插入的区间查询结构。能够实现插入删除以及区间k大(小)的查询。 | 答案是有，替罪羊树完美保证了树形不轻易改变的性质，在重构的同时我们也重构我们的线段树，这样我们就能实现一种带插入的区间查询结构。能够实现插入删除以及区间k大(小)的查询。 | ||
| 行 333: | 行 333: | ||
| 而替罪羊树上的每个点，都保存着它子树的权值线段树，一旦重构，便自底向上进行线段树合并。 | 而替罪羊树上的每个点，都保存着它子树的权值线段树，一旦重构，便自底向上进行线段树合并。 | ||
| - | 这里我们给出一道例题[洛谷P4278 带插入区间K小值](https://www.luogu.com.cn/problem/P4278) | + | 这里我们给出一道例题[[https://www.luogu.com.cn/problem/P4278|洛谷P4278 带插入区间K小值]] |
| 这道题由于出题人魔改了数据，这种做法只能得20分，其余点TLE+MLE，不过题目来源bzoj好像木了，仅供练习使用吧。 | 这道题由于出题人魔改了数据，这种做法只能得20分，其余点TLE+MLE，不过题目来源bzoj好像木了，仅供练习使用吧。 | ||
| 行 341: | 行 341: | ||
| 在插入替罪羊的同时我们插入线段树，同时用栈保留祖先关系(至于什么作用我们后面再说) | 在插入替罪羊的同时我们插入线段树，同时用栈保留祖先关系(至于什么作用我们后面再说) | ||
| - | ~~~cpp | + | <code cpp> |
| void ins(int x,int val){ | void ins(int x,int val){ | ||
| int p=root; | int p=root; | ||
| 行 361: | 行 361: | ||
| for(int i=top;i>=1;--i)pushup(sta[i]); | for(int i=top;i>=1;--i)pushup(sta[i]); | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===build=== | ===build=== | ||
| 行 367: | 行 367: | ||
| 这里也是替罪羊的rebuild部分，我们将重建的树所包含的点存好之后，对其重建并通过线段树合并整合信息。 | 这里也是替罪羊的rebuild部分，我们将重建的树所包含的点存好之后，对其重建并通过线段树合并整合信息。 | ||
| - | ~~~cpp | + | <code cpp> |
| void build(int &x,int l,int r){ | void build(int &x,int l,int r){ | ||
| if(l>r){x=0;return;} | if(l>r){x=0;return;} | ||
| 行 382: | 行 382: | ||
| insert(rt[x],w[x],0,70000,1); | insert(rt[x],w[x],0,70000,1); | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===merge=== | ===merge=== | ||
| 行 388: | 行 388: | ||
| 线段树合并 | 线段树合并 | ||
| - | ~~~cpp | + | <code cpp> |
| void Merge(int &x,int son0,int son1,int l,int r){ | void Merge(int &x,int son0,int son1,int l,int r){ | ||
| if(!x)x=newtr(); | if(!x)x=newtr(); | ||
| 行 397: | 行 397: | ||
| if(sum(rs(son0))|sum(rs(son1)))Merge(rs(x),rs(son0),rs(son1),mid+1,r); | if(sum(rs(son0))|sum(rs(son1)))Merge(rs(x),rs(son0),rs(son1),mid+1,r); | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===del=== | ===del=== | ||
| 行 403: | 行 403: | ||
| 在对树拍扁重建时对线段树上的点回收，否则消耗空间过于巨大 | 在对树拍扁重建时对线段树上的点回收，否则消耗空间过于巨大 | ||
| - | ~~~cpp | + | <code cpp> |
| void del(int &x){ | void del(int &x){ | ||
| if(!x)return; | if(!x)return; | ||
| 行 409: | 行 409: | ||
| Q.push(x);x=0; | Q.push(x);x=0; | ||
| } | } | ||
| - | ~~~ | + | </code> |
| 其余操作没什么好说的，基本就是线段树和替罪羊树的操作，这里根据题涉条件讲两个操作 | 其余操作没什么好说的，基本就是线段树和替罪羊树的操作，这里根据题涉条件讲两个操作 | ||
| 行 417: | 行 417: | ||
| 在替罪羊树上提取我们所需的点的区间，如果是完全包含，则保存这点的权值线段树，单点包含则保存该点并继续递归子树。 | 在替罪羊树上提取我们所需的点的区间，如果是完全包含，则保存这点的权值线段树，单点包含则保存该点并继续递归子树。 | ||
| - | ~~~cpp | + | <code cpp> |
| void query(int x,int l,int r){ | void query(int x,int l,int r){ | ||
| if(!x)return; | if(!x)return; | ||
| 行 430: | 行 430: | ||
| } | } | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ===关于得到答案=== | ===关于得到答案=== | ||
| 行 436: | 行 436: | ||
| 这里我们采取在区间上二分的方式，L、R应时刻保持与区间一致(否则会影响单点的判断) | 这里我们采取在区间上二分的方式，L、R应时刻保持与区间一致(否则会影响单点的判断) | ||
| - | ~~~cpp | + | <code cpp> |
| #define unt unsigned int | #define unt unsigned int | ||
| int solve(int l,int r,int k){ | int solve(int l,int r,int k){ | ||
| 行 459: | 行 459: | ||
| return L; | return L; | ||
| } | } | ||
| - | ~~~ | + | </code> |
| - | 下面给出~~TLE+MLE~~完整代码 | + | 下面给出<del>TLE+MLE</del>完整代码 |
| - | ~~~cpp | + | <code cpp> |
| #include<algorithm> | #include<algorithm> | ||
| #include<stack> | #include<stack> | ||
| 行 624: | 行 624: | ||
| query(root,l,r);k--; | query(root,l,r);k--; | ||
| int L=0,R=70000; | int L=0,R=70000; | ||
| - | unt n=vectr.size(); | ||
| while(L<R){ | while(L<R){ | ||
| int mid=(L+R)>>1; | int mid=(L+R)>>1; | ||
| 行 631: | 行 630: | ||
| for(auto x:vecp)if(L<=w[x]&&w[x]<=mid)++tot; | for(auto x:vecp)if(L<=w[x]&&w[x]<=mid)++tot; | ||
| if(tot>k){ | if(tot>k){ | ||
| - | for(unt i=0;i<n;++i)vectr[i]=ls(vectr[i]); | + | for(auto &x:vectr)x=ls(x); |
| R=mid; | R=mid; | ||
| } | } | ||
| else { | else { | ||
| - | for(unt i=0;i<n;++i)vectr[i]=rs(vectr[i]); | + | for(auto &x:vectr)x=rs(x); |
| L=mid+1;k-=tot; | L=mid+1;k-=tot; | ||
| } | } | ||
| 行 657: | 行 656: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | ~~~ | + | </code> |
| ====平衡树套线段树(非旋treap)==== | ====平衡树套线段树(非旋treap)==== | ||
2020-2021/teams/hotpot/lotk_树套树.1588925929.txt.gz · 最后更改: 2020/05/08 16:18 由 lotk
