3196: Tyvj 1730 二逼平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2271 Solved: 935
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
Input
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继
Output
对于操作1,2,4,5各输出一行，表示查询结果
Sample Input
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
Sample Output
2
4
3
4
9
4
3
4
9
HINT
1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数
Source
Solution
树套树，线段树套平衡树 其实也可以写 权值线段树套区间线段树
正确姿势就是，对于区间建一颗线段树，线段树的每个区间都建一颗平衡树，对于区间的询问，从线段树上找区间，利用平衡树去询问
操作一：查询区间中的小于K的值，最后+1
操作二：二分判定，代入操作一
操作三：对于包含的每个区间上的pos都修改
操作四：对于每段都查询前驱，最后找到最大的前驱
操作五：对于每段都查询后继，最后找到最小的后继
启发：
认真背模板！！！一条语句的错误浪费了自己和别人很长时间
数据结构题要多练多总结，多调多背
要坚定不移的相信自己是智障，新东西一昧想YY不愿了解别人的方法，就是在作死
大代码题要面向对象编程,合理分成程序段,方便差错和调试
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 2000100
int n,m,a[maxn],maxx;
//SplayTree-----------------------------------------------------------------------------------------
int fa[maxn],son[maxn][],key[maxn],cnt[maxn],size[maxn],root[maxn],sz;
void clear(int now){son[now][]=son[now][]=fa[now]=cnt[now]=key[now]=size[now]=;}
int get(int now){return son[fa[now]][]==now;}
void update(int now)
{
if (!now) return;
size[now]=cnt[now];
if (son[now][]) size[now]+=size[son[now][]];
if (son[now][]) size[now]+=size[son[now][]];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],which=get(x);
son[y][which]=son[x][which^]; fa[son[y][which]]=y;
fa[y]=x; son[x][which^]=y; fa[x]=z;
if (z) son[z][son[z][]==y]=x;
update(y); update(x);
}
void splay(int rt,int x,int tar)
{
for (int f; (f=fa[x])!=tar; rotate(x))
if (fa[f]!=tar)
rotate(get(x)==get(f)?f:x);
if (tar==) root[rt]=x;
}
void insert(int rt,int v)
{
if (!root[rt])
{sz++;son[sz][]=son[sz][]=fa[sz]=;key[sz]=v;size[sz]=;cnt[sz]=;root[rt]=sz;return;}
int now=root[rt],f=;
while (now)
{
if (key[now]==v) {cnt[now]++;update(now);update(f);splay(rt,now,);break;}
f=now; now=son[now][key[now]<v];
if (now==)
{
sz++;son[sz][]=son[sz][]=;key[sz]=v;size[sz]=;
cnt[sz]=;fa[sz]=f;son[f][key[f]<v]=sz;
update(f);splay(rt,sz,);break;
}
}
}
int find(int rt,int x)
{
int now=root[rt];
while (now)
{
if (key[now]==x) return now;
if (key[now]>x) now=son[now][];
else now=son[now][];
}
}
int findrank(int rt,int x)
{
int now=root[rt],ans=;
while (now)
{
if (key[now]>x) now=son[now][];
else if (key[now]<x)
ans+=(cnt[now]+size[son[now][]]),now=son[now][];
else {ans+=size[son[now][]];break;}
}
return ans;
}
int findkth(int rt,int x)
{
int now=root[rt];
while (now)
{
if (son[now][] && x<=size[son[now][]]) now=son[now][]; else
{
int temp;
if (son[now][]) temp=size[son[now][]]+cnt[now];
else temp=cnt[now];
if (x<=temp) return key[now];
x-=temp; now=son[now][];
}
}
}
int prev(int rt)
{
int now=son[root[rt]][];
while (son[now][]) now=son[now][];
return now;
}
bool remove(int rt,int now)
{
int fi=find(rt,now);
if (fi==-) return false;
else splay(rt,fi,);
if (cnt[root[rt]]>) {cnt[root[rt]]--; size[root[rt]]--; return true;};
if (!son[root[rt]][] && !son[root[rt]][]) {clear(root[rt]); root[rt]=; return true;}
if (!son[root[rt]][])
{int oldroot=root[rt]; root[rt]=son[root[rt]][]; fa[root[rt]]=; clear(oldroot); return true;}
else if (!son[root[rt]][])
{int oldroot=root[rt]; root[rt]=son[root[rt]][]; fa[root[rt]]=; clear(oldroot); return true;}
int leftbig=prev(rt),oldroot=root[rt];
splay(rt,leftbig,);
fa[son[oldroot][]]=root[rt]; son[root[rt]][]=son[oldroot][];
clear(oldroot); update(root[rt]); return true;
}
int Prev(int rt,int x)
{
int now=root[rt],ans=-0x7fffffff;
while (now)
{
if (key[now]<x)
{if (ans<key[now])ans=key[now]; now=son[now][];}
else now=son[now][];
}
return ans;
}
int Succ(int rt,int x)
{
int now=root[rt],ans=0x7fffffff;
while (now)
{
if (key[now]>x)
{if (ans>key[now]) ans=key[now]; now=son[now][];}
else now=son[now][];
}
return ans;
}
//SegmentTree---------------------------------------------------------------------------------------
void buildTree(int now,int l,int r)
{
for (int i=l; i<=r; i++) insert(now,a[i]);
if (l==r) return;
int mid=(l+r)>>;
buildTree(now<<,l,mid); buildTree(now<<|,mid+,r);
}
int FindRank(int now,int l,int r,int L,int R,int rk)
{
if (L<=l && R>=r) return findrank(now,rk);
int mid=(l+r)>>,rak=;
if (L<=mid) rak+=FindRank(now<<,l,mid,L,R,rk);
if (mid<R) rak+=FindRank(now<<|,mid+,r,L,R,rk);
return rak;
}
int FindKth(int L,int R,int kt)
{
int ll=,rr=maxx,mid;
while (ll<rr)
{
mid=(ll+rr)>>;
if (FindRank(,,n,L,R,mid)<kt) ll=mid+;
else rr=mid;
}
return ll-;
}
void ChangeK(int now,int l,int r,int p,int k)
{
remove(now,a[p]); insert(now,k);
if (l==r) {a[p]=k;return;}
int mid=(l+r)>>;
if (p<=mid) ChangeK(now<<,l,mid,p,k);
else ChangeK(now<<|,mid+,r,p,k);
}
int GetPrev(int now,int l,int r,int L,int R,int k)
{
int mid=(l+r)>>,pre=-0x7fffffff;
if (L<=l && R>=r) return Prev(now,k);
if (L<=mid) pre=max(pre,GetPrev(now<<,l,mid,L,R,k));
if (mid<R) pre=max(pre,GetPrev(now<<|,mid+,r,L,R,k));
return pre;
}
int GetSucc(int now,int l,int r,int L,int R,int k)
{
int mid=(l+r)>>,suc=0x7fffffff;
if (L<=l && R>=r) return Succ(now,k);
if (L<=mid) suc=min(suc,GetSucc(now<<,l,mid,L,R,k));
if (mid<R) suc=min(suc,GetSucc(now<<|,mid+,r,L,R,k));
return suc;
}
//Solve---------------------------------------------------------------------------------------------
void solve_1(int l,int r,int k) {printf("%d\n",FindRank(,,n,l,r,k)+);}
void solve_2(int l,int r,int k) {printf("%d\n",FindKth(l,r,k));}
void solve_3(int pos,int k) {ChangeK(,,n,pos,k);}
void solve_4(int l,int r,int k) {printf("%d\n",GetPrev(,,n,l,r,k));}
void solve_5(int l,int r,int k) {printf("%d\n",GetSucc(,,n,l,r,k));}
//void debug(int now)
//{
// if (!now) return;
// debug(son[now][0]);
// printf("%d-%d个 ",key[now],cnt[now]);
// debug(son[now][1]);
//}
//main----------------------------------------------------------------------------------------------
int main()
{
// freopen("output.out","w",stdout);
n=read(),m=read();
for (int i=; i<=n; i++) a[i]=read(),maxx=max(maxx,a[i]);
buildTree(,,n);
for (int i=; i<=m; i++)
{
int opt=read(),l,r,k,pos;
switch (opt)
{
case : l=read(); r=read(); k=read(); solve_1(l,r,k); break;
case : l=read(); r=read(); k=read(); solve_2(l,r,k); break;
case : pos=read(); k=read(); solve_3(pos,k); break;
case : l=read(); r=read(); k=read(); solve_4(l,r,k); break;
case : l=read(); r=read(); k=read(); solve_5(l,r,k); break;
} //for (int i=1;i<=17;i++) debug(root[i]),puts("");
} return ;
}
让南爷看了两个shabi错误...[好友'智商'已经掉线]...秀了一波智商下限TAT''
UPD:ShallWe大爷的 权值线段树套区间线段树 没调..留着以后学姿势
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 51000
using namespace std;
int tn,Hash[N],a[N],head[N];
int n,m,totp,totin,rt;
struct P{
int l,r,in;
} p[];
struct I{
int l,r,sz;
} in[];
struct Q{
int type,l,r,k;
} query[N]; inline int read()
{ char ch=getchar();int flag=;for(;ch<''||ch>'';ch=getchar())if(ch=='-') flag=-;
int x=; for(;ch>=''&&ch<='';x=x*+ch-,ch=getchar());return x*flag;
}
inline int DC(int x)
{ return lower_bound(Hash+,Hash++tn,x)-Hash;} inline int DCC(int x)
{ int w=lower_bound(Hash+,Hash++tn,x)-Hash;
return w-; } inline int DCCC(int x)
{ int w=upper_bound(Hash+,Hash++tn,x)-Hash;} inline void Up(int x)
{ in[x].sz=in[in[x].l].sz+in[in[x].r].sz;} void Insert(int &x,int l,int r,int w,int delta)
{ if (!x) x=++totin;
// cout<<x<<endl;
// cout<<l<<' '<<r<<' '<<w<<endl;
if (l==r){
in[x].sz+=delta;
return;
} int mid=(l+r)>>;
if (w<=mid) Insert(in[x].l,l,mid,w,delta);
else Insert(in[x].r,mid+,r,w,delta);
Up(x);
} void Add(int &x,int l,int r,int val,int whe,int delta)
{ if (!x) x=++totp;
// cout<<l<<' '<<r<<' '<<val<<' '<<whe<<endl;
Insert(p[x].in,,n,whe,delta);
if (l==r) return; int mid=(l+r)>>;
if (val<=mid) Add(p[x].l,l,mid,val,whe,delta);
else Add(p[x].r,mid+,r,val,whe,delta);
} int Get_sz_in(int x,int l,int r,int L,int R)
{ if (!x) return ;
if (L>R) return x;
if (L<=l&&r<=R) return in[x].sz;
int mid=(l+r)>>,now=;
if (L<=mid) now+=Get_sz_in(in[x].l,l,mid,L,R);
if (R>mid) now+=Get_sz_in(in[x].r,mid+,r,L,R);
return now;
} int Get_sz(int x,int l,int r,int L,int R,int il,int ir)
{ if (!x) return ;
if (L>R) return ;
// cout<<x<<' '<<l<<' '<<r<<' '<<endl;
if (L<=l&&r<=R) return Get_sz_in(p[x].in,,n,il,ir);
int mid=(l+r)>>,now=;
if (L<=mid) now+=Get_sz(p[x].l,l,mid,L,R,il,ir);
if (R>mid) now+=Get_sz(p[x].r,mid+,r,L,R,il,ir);
return now;
} inline int Find_rate(int l,int r,int k)
{ int sz=Get_sz(rt,,tn,,k-,l,r);
return sz+;
} inline int Find_kth(int l,int r,int k)
{ int L=,R=tn,x=rt;
while (L<R)
{ int mid=(L+R)>>;
int Left=Get_sz_in(p[p[x].l].in,,n,l,r);
if (Left>=k) R=mid,x=p[x].l;
if (Left<k) k-=Left,L=mid+,x=p[x].r;
}
return Hash[L];
}
int main()
{ freopen("a.in","r",stdin);
n=read(),m=read();
for (int i=;i<=n;i++)
Hash[i]=a[i]=read();
tn=n;
int x,y,z,type ;
for (int i=;i<=m;i++)
{ type=query[i].type=read();
if (type==)
{ query[i].l=read();
query[i].k=read();
Hash[++tn]=query[i].k;
}else{
query[i].l=read();
query[i].r=read();
query[i].k=read();
}
}
// for (int i=1;i<=m;i++)
// cout<<query[i].l<<' '<<query[i].r<<' '<<query[i].k<<endl;
sort(Hash+,Hash++tn);
tn=unique(Hash+,Hash++tn)-Hash;
for (int i=;i<=n;i++)
Add(rt,,tn,a[i]=DC(a[i]),i,+);
// for(int i=1;i<=n;i++) cout<<a[i]<<endl;
for (int i=;i<=m;i++)
{ int l=query[i].l,r=query[i].r,k=query[i].k;
// cout<<query[i].type<<endl;
switch (query[i].type){
case :{
printf("%d\n",Find_rate(l,r,DC(k)));
break;
}
case :{
printf("%d\n",Find_kth(l,r,k));
break;
}
case :{
Add(rt,,tn,a[l],l,-);
Add(rt,,tn,a[l]=DC(k),l,);
break;
}
case :{
int now=DCC(k);
int x=Get_sz(rt,,tn,l,r,now,now);
if (x)
printf("%d\n",Hash[now]);
else
printf("%d\n",Find_kth(l,r,Find_rate(l,r,now)-));
break;
}
case :{
int now=DCCC(k);
int x=Get_sz(rt,,tn,l,r,now,now);
if (x)
printf("%d\n",Hash[now]);
else
printf("%d\n",Find_kth(l,r,Find_rate(l,r,now)));
break;
}
}
}
return ;
}
ShallWe's Code