bzoj3196 Tyvj 1730 二逼平衡树

本文主要是介绍bzoj3196 Tyvj 1730 二逼平衡树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

终于把这个大坑填完了。。。
sb树套树
看似最不合理的方案恰恰是正确方案，树套树并不会MLE，它的空间复杂度非常科学，O(nlogn)。（结果因为空间算错数组开小神奇的T掉，浪费了我两天时间）

嘛。貌似除了操作二没什么好说的。转换成判定性问题就好了，二分O(nlog$^{3}$n)解决。其他按照正常线段树和平衡树写就好了。

CODE：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=50005;
struct node
{int size,num,sum;node *ch[2],*fa;inline int getwh(){return fa->ch[0]==this?0:1;}inline void update(){size=ch[0]->size+ch[1]->size+sum;}inline void setch(int wh,node *child);
}pool[2000005],*null,*t[N<<2];
inline void node::setch(int wh,node *child)
{ch[wh]=child;if(child!=null) child->fa=this;update();
}
int a[N];
int n,m,opt,x,y,z,tot;
inline node *getnew(int value)
{node *now=pool+ ++tot;now->ch[0]=now->ch[1]=now->fa=null;now->num=value;now->size=now->sum=1;return now;
}
inline void rotate(node *&now)
{node *fa=now->fa,*grand=fa->fa;int wh=now->getwh();fa->setch(wh,now->ch[wh^1]);now->setch(wh^1,fa);now->fa=grand;if(grand!=null) grand->ch[grand->ch[0]==fa?0:1]=now;
}
inline void splay(node *now,node *tar,node *&root)
{for(;now->fa!=tar;rotate(now))if(now->fa->fa!=tar) now->getwh()==now->fa->getwh()?rotate(now->fa):rotate(now);if(tar==null) root=now;
}
inline void insert(int value,node *&root)
{node *now=root,*last=null;while(now!=null){last=now;if(now->num==value) return now->sum++,now->size++,splay(now,null,root);if(now->num>value) now=now->ch[0];else now=now->ch[1];}if(last==null){root=getnew(value);return;}now=getnew(value);if(last->num>value) last->setch(0,now);else last->setch(1,now);splay(now,null,root);
}
inline node *find(int value,node *&root)
{node *now=root;while(now!=null){if(now->num==value){splay(now,null,root);return now;}if(now->num>value) now=now->ch[0];else now=now->ch[1];}
}
inline void del(int value,node *&root)
{node *now=find(value,root);if(now->sum>1){now->sum--;now->size--;return;}if(now->ch[0]==null&&now->ch[1]==null){root=null;return;}if(now->ch[0]==null){root=now->ch[1];now->ch[1]->fa=null;return;}if(now->ch[1]==null){root=now->ch[0];now->ch[0]->fa=null;return;}node *pre=now->ch[0];while(pre->ch[1]!=null) pre=pre->ch[1];splay(pre,now,root);pre->setch(1,now->ch[1]);pre->fa=null;root=pre;
}
inline int rank(int value,node *&root)
{int ranking=0;node *now=root;while(now!=null){if(now->num==value){ranking+=now->ch[0]->size;splay(now,null,root);return ranking;}if(now->num>value) now=now->ch[0];else ranking+=now->ch[0]->size+now->sum,now=now->ch[1];}return ranking;
}
inline void change(int value,int num,node *&root)
{del(value,root);insert(num,root);
}
inline int pre(int value,node *&root)
{node *now=root;int ans=-2147483647;while(now!=null)if(now->num>=value) now=now->ch[0];else ans=max(ans,now->num),now=now->ch[1];return ans;
}
inline int nxt(int value,node *&root)
{node *now=root;int ans=2147483647;while(now!=null)if(now->num<=value) now=now->ch[1];else ans=min(ans,now->num),now=now->ch[0];return ans;
}
inline void init(int l,int r,node *&root)
{root=null;for(int i=l;i<=r;i++)insert(a[i],root);
}
void build(int l,int r,int now)
{init(l,r,t[now]);if(l==r) return;int mid=(l+r)>>1;build(l,mid,now<<1);build(mid+1,r,now<<1|1);
}
int askrank(int L,int R,int l,int r,int now,int num)
{if(L<=l&&r<=R) return rank(num,t[now]);int mid=(l+r)>>1,ans=0;if(L<=mid) ans=askrank(L,R,l,mid,now<<1,num);if(R>mid) ans+=askrank(L,R,mid+1,r,now<<1|1,num);return ans;
}
inline int askkth(int L,int R,int num)
{int l=0,r=1e8+1,mid;while(l<r){mid=(l+r)>>1;if(askrank(L,R,1,n,1,mid)>=num) r=mid;else l=mid+1;}return l-1;
}
void changenum(int p,int l,int r,int now,int num)
{change(a[p],num,t[now]);if(l==r) return;int mid=(l+r)>>1;if(p<=mid) return changenum(p,l,mid,now<<1,num);changenum(p,mid+1,r,now<<1|1,num);
}
int askpre(int L,int R,int l,int r,int now,int num)
{if(L<=l&&r<=R) return pre(num,t[now]);int mid=(l+r)>>1,ans=-2147483647;if(L<=mid) ans=askpre(L,R,l,mid,now<<1,num);if(R>mid) ans=max(ans,askpre(L,R,mid+1,r,now<<1|1,num));return ans;
}
int asknxt(int L,int R,int l,int r,int now,int num)
{if(L<=l&&r<=R) return nxt(num,t[now]);int mid=(l+r)>>1,ans=2147483647;if(L<=mid) ans=asknxt(L,R,l,mid,now<<1,num);if(R>mid) ans=min(ans,asknxt(L,R,mid+1,r,now<<1|1,num));return ans;
}
int main()
{null=pool;null->ch[0]=null->ch[1]=null->fa=null;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);while(m--){scanf("%d",&opt);if(opt==1) scanf("%d%d%d",&x,&y,&z),printf("%d\n",askrank(x,y,1,n,1,z)+1);else if(opt==2) scanf("%d%d%d",&x,&y,&z),printf("%d\n",askkth(x,y,z));else if(opt==3) scanf("%d%d",&x,&y),changenum(x,1,n,1,y),a[x]=y;else if(opt==4) scanf("%d%d%d",&x,&y,&z),printf("%d\n",askpre(x,y,1,n,1,z));else scanf("%d%d%d",&x,&y,&z),printf("%d\n",asknxt(x,y,1,n,1,z));}return 0;
}

这篇关于bzoj3196 Tyvj 1730 二逼平衡树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---