2020-2021:teams:hotpot:lotk_树套树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:lotk_树套树 [2020/05/08 16:46] lotk |
2020-2021:teams:hotpot:lotk_树套树 [2020/05/08 16:53] (当前版本) lotk [平衡树套线段树(替罪羊)] |
||
|---|---|---|---|
| 行 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_树套树.1588927618.txt.gz · 最后更改: 2020/05/08 16:46 由 lotk
