luogu3380 【模板】二逼平衡树（树套树）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了luogu3380 【模板】二逼平衡树（树套树），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4276字，纯文字阅读大概需要7分钟。
内容图文
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using
namespace std;
int n, m, cnt, a[50005], rot[200005], opt, ans, uu, vv, ww;
struct Node{
int l, r, siz, hav, val, rnd;
}nd[4000005];
void upd(int k){
nd[k].siz = nd[nd[k].l].siz + nd[nd[k].r].siz + nd[k].hav;
}
void lRotate(int &k){
int t=nd[k].r; nd[k].r = nd[t].l; nd[t].l = k;
nd[t].siz = nd[k].siz; upd(k); k = t;
}
void rRotate(int &k){
int t=nd[k].l; nd[k].l = nd[t].r; nd[t].r = k;
nd[t].siz = nd[k].siz; upd(k); k = t;
}
void treapInsert(int &k, int x){
if(!k){
k = ++cnt; nd[k].siz = nd[k].hav = 1;
nd[k].val = x; nd[k].rnd = rand();
return ;
}
nd[k].siz++;
if(nd[k].val==x) nd[k].hav++;
elseif(nd[k].val>x){
treapInsert(nd[k].l, x);
if(nd[nd[k].l].rnd<nd[k].rnd) rRotate(k);
}
else{
treapInsert(nd[k].r, x);
if(nd[nd[k].r].rnd<nd[k].rnd) lRotate(k);
}
}
void treapDelete(int &k, int x){
if(!k) return ;
if(nd[k].val==x){
if(nd[k].hav>1){
nd[k].hav--; nd[k].siz--;
return ;
}
elseif(nd[k].l*nd[k].r==0) k = nd[k].l + nd[k].r;
elseif(nd[nd[k].l].rnd<nd[nd[k].r].rnd)
rRotate(k), treapDelete(k, x);
else
lRotate(k), treapDelete(k, x);
}
elseif(nd[k].val<x) nd[k].siz--, treapDelete(nd[k].r, x);
else nd[k].siz--, treapDelete(nd[k].l, x);
}
int treapQueryRank(int k, int x){
if(!k) return0;
if(nd[k].val>x) return treapQueryRank(nd[k].l, x);
elseif(nd[k].val<x) return treapQueryRank(nd[k].r, x)+nd[nd[k].l].siz+nd[k].hav;
elsereturn nd[nd[k].l].siz;
}
void treapQueryPre(int k, int x){
if(!k) return ;
if(nd[k].val<x) ans = max(ans, nd[k].val), treapQueryPre(nd[k].r, x);
else treapQueryPre(nd[k].l, x);
}
void treapQueryNxt(int k, int x){
if(!k) return ;
if(nd[k].val>x) ans = min(ans, nd[k].val), treapQueryNxt(nd[k].l, x);
else treapQueryNxt(nd[k].r, x);
}
void sgtInsert(int o, int l, int r, int x, int k){
treapInsert(rot[o], k);
if(l==r) ;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) sgtInsert(lson, l, mid, x, k);
if(mid<x) sgtInsert(rson, mid+1, r, x, k);
}
}
void sgtDelete(int o, int l, int r, int x, int k){
treapDelete(rot[o], k);
if(l==r) ;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) sgtDelete(lson, l, mid, x, k);
if(mid<x) sgtDelete(rson, mid+1, r, x, k);
}
}
int sgtQueryRank(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y) return treapQueryRank(rot[o], k);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
int re=0;
if(x<=mid) re += sgtQueryRank(lson, l, mid, x, y, k);
if(mid<y) re += sgtQueryRank(rson, mid+1, r, x, y, k);
return re;
}
}
void sgtQueryPre(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y) treapQueryPre(rot[o], k);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) sgtQueryPre(lson, l, mid, x, y, k);
if(mid<y) sgtQueryPre(rson, mid+1, r, x, y, k);
}
}
void sgtQueryNxt(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y) treapQueryNxt(rot[o], k);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) sgtQueryNxt(lson, l, mid, x, y, k);
if(mid<y) sgtQueryNxt(rson, mid+1, r, x, y, k);
}
}
int queryKth(int uu, int vv, int ww){
int l=0, r=100000000, mid, re;
while(l<=r){
mid = (l + r) >> 1;
if(sgtQueryRank(1, 1, n, uu, vv, mid)+1<=ww) re = mid, l = mid + 1;
else r = mid - 1;
}
return re;
}
int main(){
srand(time(NULL));
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
sgtInsert(1, 1, n, i, a[i]);
}
while(m--){
scanf("%d", &opt);
if(opt==1){
scanf("%d%d%d", &uu, &vv, &ww);
printf("%d\n", sgtQueryRank(1, 1, n, uu, vv, ww)+1);
}
if(opt==2){
scanf("%d%d%d", &uu, &vv, &ww);
printf("%d\n", queryKth(uu, vv, ww));
}
if(opt==3){
scanf("%d%d", &uu, &vv);
sgtDelete(1, 1, n, uu, a[uu]);
a[uu] = vv;
sgtInsert(1, 1, n, uu, vv);
}
if(opt==4){
scanf("%d%d%d", &uu, &vv, &ww);
ans = -2147483647;
sgtQueryPre(1, 1, n, uu, vv, ww);
printf("%d\n", ans);
}
if(opt==5){
scanf("%d%d%d", &uu, &vv, &ww);
ans = 2147483647;
sgtQueryNxt(1, 1, n, uu, vv, ww);
printf("%d\n", ans);
}
}
return0;
}
原文：https://www.cnblogs.com/poorpool/p/8445658.html
内容总结
以上是互联网集市为您收集整理的luogu3380 【模板】二逼平衡树（树套树）全部内容，希望文章能够帮你解决luogu3380 【模板】二逼平衡树（树套树）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】