【山东省选2008】郁闷的小J 平衡树Treap

小J是国家图书馆的一位图书管理员,他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳,但是由于这个书架十分巨大,所以他的工作效率总是很低,以致他面临着被解雇的危险,这也正是他所郁闷的。具体说来,书架由N个书位组成,编号从1到N。每个书位放着一本书,每本书有一个特定的编码。
 小J的工作有两类:
1.      图书馆经常购置新书,而书架任意时刻都是满的,所以只得将某位置的书拿掉并换成新购的书。
2.      小J需要回答顾客的查询,顾客会询问某一段连续的书位中某一特定编码的书有多少本。
例如,共5个书位,开始时书位上的书编码为1,2,3,4,5
一位顾客询问书位1到书位3中编码为“2”的书共多少本,得到的回答为:1
一位顾客询问书位1到书位3中编码为“1”的书共多少本,得到的回答为:1
此时,图书馆购进一本编码为“1”的书,并将它放到2号书位。
一位顾客询问书位1到书位3中编码为“2”的书共多少本,得到的回答为:0
一位顾客询问书位1到书位3中编码为“1”的书共多少本,得到的回答为:2
……
 
       你的任务是写一个程序来回答每个顾客的询问。

输入

第一行两个整数N,M,表示一共N个书位,M个操作。
接下来一行共N个整数数A1,A2…AN,Ai表示开始时位置i上的书的编码。
接下来M行,每行表示一次操作,每行开头一个字符
若字符为‘C’,表示图书馆购进新书,后接两个整数A(1<=A<=N),P,表示这本书被放在位置A上,以及这本书的编码为P。
若字符为‘Q’,表示一个顾客的查询,后接三个整数A,B,K(1<=A<=B<=N),表示查询从第A书位到第B书位(包含A和B)中编码为K的书共多少本。

输出

对每一个顾客的查询,输出一个整数,表示顾客所要查询的结果。

样例输入

5 5 1 2 3 4 5 Q 1 3 2 Q 1 3 1 C 2 1 Q 1 3 2 Q 1 3 1

样例输出

1 1 0 2

提示

对于40%的数据,1<=N,M<=5000
对于100%的数据,1<=N,M<=100000
对于100%的数据,所有出现的书的编码为不大于2147483647的正数。
 
 
题解:
本弱用的平衡树Treap做法,开始想的维护一个书的编号和所在书柜的平衡树,然后查找时,先在平衡树找到该编号书所在区域,然后爆搜判断是否满足l<=id<=r,ans++。
但发现如果平衡树中相同的编号的书太多就会卡成O(n^2),只拿了82分;
以下是暴力代码:
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N=;
struct node
{
int x,lev,id;
node *child[];
}a[N*];
node *pos,*root;
void newnode(node *&r,int key,int ids)
{
r=pos++;
r->child[]=r->child[]=NULL;
r->x=key;
r->id=ids;
r->lev=rand();
} int n;
int gi()
{
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
int b[N]; void rotate(node *&r,bool t)//0左旋 1右旋
{
node *y=r->child[!t];
r->child[!t]=y->child[t];
y->child[t]=r;
r=y;
}
void insert(node *&r,int key,int ids)
{
if(r==NULL){newnode(r,key,ids);return ;}
bool t=key>r->x;
insert(r->child[t],key,ids);
if(r->child[t]->lev<r->lev)rotate(r,!t);
} void Delet(node *&r,int key,int ids)
{
if(r==NULL)return ;
if(r->x==key && r->id==ids)
{
if(r->child[] && r->child[])
{
bool t=r->child[]->lev<r->child[]->lev;
rotate(r,t);
Delet(r->child[t],key,ids);
}
else
{
if(r->child[])r=r->child[];
else r=r->child[];
}
}
else
{
if(r->x!=key)Delet(r->child[key>r->x],key,ids);
else {
if(r->child[])Delet(r->child[],key,ids);
if(r->child[])Delet(r->child[],key,ids);
}
}
} int find(node *&r,int ls,int rs,int key)
{
if(r==NULL)return ;
int sum=;
if(r->x==key && r->id>=ls && r->id<=rs)sum++;
if(r->x!=key)sum+=find(r->child[r->x<key],ls,rs,key);//先找到相同编号的书所在区域
else {//然后爆搜
if(r->child[])sum+=find(r->child[],ls,rs,key);
if(r->child[])sum+=find(r->child[],ls,rs,key);
}
return sum;
} void check(node *r)//检查的时候用
{
if(r==NULL)return ;
printf("key=%d id=%d ",r->x,r->id);
if(r->child[])printf("right=%d ",r->child[]->x);
if(r->child[])printf("left=%d ",r->child[]->x);
printf("\n");
check(r->child[]);check(r->child[]);
}
int main()
{
int m;
n=gi();m=gi();
pos=a;
for(int i=;i<=n;i++)
{
b[i]=gi();
insert(root,b[i],i);
}
char f;int x,y,z;
while(m--)
{
f=getchar();
while(f!='Q' && f!='C')f=getchar();
if(f=='C')//修改时先删再添加。
{
x=gi();y=gi();
Delet(root,b[x],x);
b[x]=y;
insert(root,y,x);
}
else if(f=='Q')
{
x=gi();y=gi();z=gi();
printf("%d\n",find(root,x,y,z));
}
}
return ;
}

然后是正解:离散化+Treap

设询问中C出现的次数为K,只需维护(K+N)个平衡树,用一个*root[N+K]来保存根节点即可实现。

注意是每一种书对应一颗平衡树,平衡树里保存的是在原数组出现的位置(即书柜号)。

然后Q L R X的话,先找到X对应的平衡树,再寻找编号在L和R之间的节点个数即可(可以用小于等于R的个数-小于L的个数)。

C X Y 设读入的数组为a[N],先在a[x]对应的树中删除编号为x的节点,再在Y对应的树中加入编号为X的节点。

代码如下:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N=;
struct node
{
int x,lev,size;
node *child[];
}a[N*];
struct Ques
{
int flag,x,y,z;
}q[N];
int qm=;
node *pos,*root[N];
int s[N*];
void newnode(node *&r,int key)
{
r=pos++;
r->child[]=r->child[]=NULL;
r->x=key;
r->size=;
r->lev=rand();
}
void updata(node *&r)
{
if(r)
r->size=(r->child[]?r->child[]->size:)+(r->child[]?r->child[]->size:)+;
}
int n;
int gi()
{
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
int b[N]; void rotate(node *&r,bool t)//0左旋 1右旋
{
node *y=r->child[!t];
r->child[!t]=y->child[t];
y->child[t]=r;
updata(r);
r=y;
updata(r);
}
void insert(node *&r,int key)
{
if(r==NULL){newnode(r,key);return ;}
bool t=key>r->x;
insert(r->child[t],key);
if(r->child[t]->lev<r->lev)rotate(r,!t);
updata(r);
} void Delet(node *&r,int key)
{
if(r==NULL)return ;
if(r->x==key)
{
if(r->child[] && r->child[])
{
bool t=r->child[]->lev<r->child[]->lev;
rotate(r,t);
Delet(r->child[t],key);
}
else
{
if(r->child[])r=r->child[];
else r=r->child[];
}
}
else Delet(r->child[key>r->x],key);
updata(r);
} int find(node *&r,int key)
{
if(r==NULL)return ;
int sum=;
if(r->x<=key){
if(r->child[])sum+=r->child[]->size;
sum++;
}
sum+=find(r->child[key>=r->x],key);
return sum;
} int py[N*],bel[N];
int ny=;
int midit(int x)//二分离散化以后该书对应的新编号
{
int mid,l=,r=ny,ans;
while(l<=r)
{
mid=(l+r)>>;
if(py[mid]<=x)ans=mid,l=mid+;
else r=mid-;
}
return ans;
} void check(node *r)//检查时用的,可以忽略
{
if(r==NULL)return ;
printf("key=%d size=%d ",r->x,r->size);
if(r->child[])printf("right=%d ",r->child[]->x);
if(r->child[])printf("left=%d ",r->child[]->x);
printf("\n");
check(r->child[]);check(r->child[]);
} int main()
{
int m;
n=gi();m=gi();
pos=a;
for(int i=;i<=n;i++)s[i]=b[i]=gi();
char f;int num=n;
for(int i=;i<=m;i++)//现将数据全部读入,再编号 离散化。
{
f=getchar();
while(f!='Q' && f!='C')f=getchar();
if(f=='C')
{
q[i].x=gi();q[i].y=gi();
s[++num]=q[i].y;
}
if(f=='Q')
{
q[i].x=gi();q[i].y=gi();q[i].z=gi();
q[i].flag=;
}
}
sort(s+,s+num+); //从小到大排序,方便编号
for(int i=;i<=num;i++)if(s[i]!=s[i+])py[++ny]=s[i];//去重 该操作之后原数组对应的新编号就是py数组的下标。
int tmp;
for(int i=;i<=n;i++){
tmp=midit(b[i]);
bel[i]=tmp;//Bel为在书柜i位置的书对应的平衡树root[]中的下标。
insert(root[tmp],i);
}
for(int i=;i<=m;i++)
{
if(!q[i].flag)
{
tmp=midit(q[i].y);
Delet(root[bel[q[i].x]],q[i].x);
bel[q[i].x]=tmp;
insert(root[tmp],q[i].x);
}
else
{
tmp=midit(q[i].z);
printf("%d\n",find(root[tmp],q[i].y)-find(root[tmp],q[i].x-));
}
}
return ;
}
上一篇:“全栈2019”Java多线程第十一章:线程优先级详解


下一篇:170630、springboot编程之普通类中调用spring管理的bean对象