2020-2021:teams:hotpot:lotk_树套树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:lotk_树套树 [2020/05/08 16:37] misakatao [平衡树套线段树(替罪羊)] |
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 【模板】二逼平衡树（树套树）]] |
| 并没有找到带区间翻转和区间查询的题，读者如果有兴趣可以出一道（ | 并没有找到带区间翻转和区间查询的题，读者如果有兴趣可以出一道（ | ||
| 行 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好像木了，仅供练习使用吧。 | ||
| 行 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; | ||
| } | } | ||
2020-2021/teams/hotpot/lotk_树套树.1588927041.txt.gz · 最后更改: 2020/05/08 16:37 由 misakatao
