BZOJ 3166

太过爱你忘了你带给我的痛 2021-12-04 06:59 333阅读 0赞

BZOJ3196: Tyvj 1730 二逼平衡树

传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3196

题意:

1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

树套树模板题,在TLE的边缘疯狂试探

  1. /************************************************************** Problem: 3196 User: buerdepepeqi Language: C++ Result: Accepted Time:9660 ms Memory:73172 kb ****************************************************************/ #include<iostream> #include<cstdlib> #include<cstdio> #define inf 100000000 #define N 200001 #define M 3000001 using namespace std; int n,m,sz,tmp,a[N]; int ls[M],rs[M],rnd[M],v[M],s[M],w[M]; int root[N]; void update(int k) {s[k]=s[ls[k]]+s[rs[k]]+w[k];} void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;} void insert(int &k,int num) { if(!k){k=++sz;s[k]=w[k]=1;v[k]=num;rnd[k]=rand();return;} s[k]++; if(num==v[k])w[k]++; else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);} else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void del(int &k,int num) { if(v[k]==num) { if(w[k]>1){w[k]--;s[k]--;return;} if(ls[k]*rs[k]==0)k=ls[k]+rs[k]; else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);} else {lturn(k);del(k,num);} } else if(num<v[k]) {del(ls[k],num);s[k]--;} else {del(rs[k],num);s[k]--;} } void build(int k,int l,int r,int x,int num) { insert(root[k],num); if(l==r)return; int mid=(l+r)>>1; if(x<=mid)build(k<<1,l,mid,x,num); else build(k<<1|1,mid+1,r,x,num); } void ask_rank(int k,int num) { if(!k)return; if(num==v[k]){tmp+=s[ls[k]];return;} else if(num<v[k])ask_rank(ls[k],num); else {tmp+=s[ls[k]]+w[k];ask_rank(rs[k],num);} } void get_rank(int k,int l,int r,int x,int y,int num) { if(l==x&&r==y){ask_rank(root[k],num);return;} int mid=(l+r)>>1; if(mid>=y)get_rank(k<<1,l,mid,x,y,num); else if(mid<x)get_rank(k<<1|1,mid+1,r,x,y,num); else { get_rank(k<<1,l,mid,x,mid,num); get_rank(k<<1|1,mid+1,r,mid+1,y,num); } } void get_index(int x,int y,int z) { int l=0,r=inf,ans; while(l<=r) { int mid=(l+r)>>1; tmp=1;get_rank(1,1,n,x,y,mid); if(tmp<=z){l=mid+1;ans=mid;} else r=mid-1; } printf("%d\n",ans); } void change(int k,int l,int r,int x,int num,int y) { del(root[k],y); insert(root[k],num); if(l==r)return; int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,num,y); else change(k<<1|1,mid+1,r,x,num,y); } void before(int k,int num) { if(!k)return; if(v[k]<num){tmp=max(v[k],tmp);before(rs[k],num);} else before(ls[k],num); } void after(int k,int num) { if(!k)return; if(v[k]>num){tmp=min(v[k],tmp);after(ls[k],num);} else after(rs[k],num); } void ask_after(int k,int l,int r,int x,int y,int num) { if(l==x&&r==y){after(root[k],num);return;} int mid=(l+r)>>1; if(mid>=y)ask_after(k<<1,l,mid,x,y,num); else if(mid<x)ask_after(k<<1|1,mid+1,r,x,y,num); else { ask_after(k<<1,l,mid,x,mid,num); ask_after(k<<1|1,mid+1,r,mid+1,y,num); } } void ask_before(int k,int l,int r,int x,int y,int num) { if(l==x&&r==y){before(root[k],num);return;} int mid=(l+r)>>1; if(mid>=y)ask_before(k<<1,l,mid,x,y,num); else if(mid<x)ask_before(k<<1|1,mid+1,r,x,y,num); else { ask_before(k<<1,l,mid,x,mid,num); ask_before(k<<1|1,mid+1,r,mid+1,y,num); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)build(1,1,n,i,a[i]); for(int i=1;i<=m;i++) { int f;scanf("%d",&f); int x,y,k; switch(f) { case 1:scanf("%d%d%d",&x,&y,&k);tmp=1;get_rank(1,1,n,x,y,k);printf("%d\n",tmp);break; case 2:scanf("%d%d%d",&x,&y,&k);get_index(x,y,k);break; case 3:scanf("%d%d",&x,&y);change(1,1,n,x,y,a[x]);a[x]=y;break; case 4:scanf("%d%d%d",&x,&y,&k);tmp=0;ask_before(1,1,n,x,y,k);printf("%d\n",tmp);break; case 5:scanf("%d%d%d",&x,&y,&k);tmp=inf;ask_after(1,1,n,x,y,k);printf("%d\n",tmp);break; } } return 0; }

转载于:https://www.cnblogs.com/buerdepepeqi/p/10841366.html

发表评论

表情:
评论列表 (有 0 条评论,333人围观)

还没有评论,来说两句吧...

相关阅读

    相关 BZOJ2938

    BZOJ2938-病毒 题意: > 二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们...

    相关 bzoj3632

    裸的最大团,随机化大法好 多次随机出一个选择顺序然后贪心即可 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

    相关 bzoj4042

    比较好的树形dp,涉及到树上路径的题目,我们往往考虑对路径分类 当我们考虑以x为根的子树,有这样几类路径 1. 起点终点都在子树内 2. 一个点延伸到子树外 对于要选择

    相关 bzoj 1834

    网络流的模板题 首先第一问我们直接用dinic搞就行了,费用直接存为0(时间上界非常松,这道题是能过),然后第二问我们只需要在第一问 的残余网络上加一个源点,源点指向1号点

    相关 BZOJ2019】nim

    著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。...

    相关 bzoj4407

    以前写过一次线性筛 发现不是很理解 写了个欧拉筛的 t了 其实每次推式子,都会先推出一组的