9159金沙游艺场-奥门金沙游艺场-[欢迎您]

9159金沙游艺场为您呈现最新的面貌!,目前注册送体验金,欢迎您将成为影视娱乐行业新的风向标,是亚洲的优质娱乐先锋。

山东省选2008

日期:2019-11-12编辑作者:前端

【山东省选2008】郁闷的小J 平衡树Treap,山东省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的正数。     9159金沙游艺场 ,题解: 本弱用的平衡树Treap做法,开始想的维护一个书的编号和所在书柜的平衡树,然后查找时,先在平衡树找到该编号书所在区域,然后爆搜判断是否满足l<=id<=r,ans++。 但发现如果平衡树中相同的编号的书太多就会卡成O(n^2),只拿了82分; 以下是暴力代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cstdlib>
  6 #include<ctime>
  7 using namespace std;
  8 const int N=100005;
  9 struct node
 10 {
 11     int x,lev,id;
 12     node *child[2];
 13 }a[N*2];
 14 node *pos,*root;
 15 void newnode(node *&r,int key,int ids)
 16 {
 17     r=pos++;
 18     r->child[0]=r->child[1]=NULL;
 19     r->x=key;
 20     r->id=ids;
 21     r->lev=rand();
 22 }
 23    
 24 int n;
 25 int gi()
 26 {
 27     int str=0;char ch=getchar();
 28     while(ch>'9' || ch<'0')ch=getchar();
 29     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
 30     return str;
 31 }
 32 int b[N];
 33    
 34 void rotate(node *&r,bool t)//0左旋 1右旋
 35 {
 36     node *y=r->child[!t];
 37     r->child[!t]=y->child[t];
 38     y->child[t]=r;
 39     r=y;
 40 }
 41 void insert(node *&r,int key,int ids)
 42 {
 43     if(r==NULL){newnode(r,key,ids);return ;}
 44     bool t=key>r->x;
 45     insert(r->child[t],key,ids);
 46     if(r->child[t]->lev<r->lev)rotate(r,!t);
 47 }
 48    
 49 void Delet(node *&r,int key,int ids)
 50 {
 51     if(r==NULL)return ;
 52     if(r->x==key && r->id==ids)
 53     {
 54         if(r->child[0] && r->child[1])
 55         {
 56             bool t=r->child[0]->lev<r->child[1]->lev;
 57             rotate(r,t);
 58             Delet(r->child[t],key,ids);
 59          }
 60          else
 61          {
 62              if(r->child[0])r=r->child[0];
 63              else r=r->child[1];
 64          }
 65      }
 66     else
 67     {
 68         if(r->x!=key)Delet(r->child[key>r->x],key,ids);
 69         else {
 70                 if(r->child[1])Delet(r->child[1],key,ids);
 71                 if(r->child[0])Delet(r->child[0],key,ids);
 72         }
 73     }
 74 }
 75   
 76 int find(node *&r,int ls,int rs,int key)
 77 {
 78     if(r==NULL)return 0;
 79     int sum=0;
 80     if(r->x==key && r->id>=ls && r->id<=rs)sum++;
 81     if(r->x!=key)sum+=find(r->child[r->x<key],ls,rs,key);//先找到相同编号的书所在区域 
 82     else {//然后爆搜 
 83            if(r->child[0])sum+=find(r->child[0],ls,rs,key);
 84            if(r->child[1])sum+=find(r->child[1],ls,rs,key);
 85     }
 86     return sum;
 87 }
 88  
 89 void check(node *r)//检查的时候用 
 90 {
 91     if(r==NULL)return ;
 92     printf("key=%d id=%d ",r->x,r->id);
 93     if(r->child[1])printf("right=%d ",r->child[1]->x);
 94     if(r->child[0])printf("left=%d ",r->child[0]->x);
 95     printf("n");
 96     check(r->child[0]);check(r->child[1]);
 97 }
 98 int main()
 99 {
100     int m;
101     n=gi();m=gi();
102     pos=a;
103     for(int i=1;i<=n;i++)
104     {
105         b[i]=gi();
106         insert(root,b[i],i);
107     }
108     char f;int x,y,z;
109     while(m--)
110     {
111         f=getchar();
112         while(f!='Q' && f!='C')f=getchar();
113         if(f=='C')//修改时先删再添加。 
114         {
115             x=gi();y=gi();
116             Delet(root,b[x],x);
117             b[x]=y;
118             insert(root,y,x);
119         }
120         else if(f=='Q')
121         {
122             x=gi();y=gi();z=gi();
123             printf("%dn",find(root,x,y,z));
124         }
125     }
126     return 0;
127 }

然后是正解:离散化+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的节点。

代码如下:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cstdlib>
  6 #include<ctime>
  7 using namespace std;
  8 const int N=100005;
  9 struct node
 10 {
 11     int x,lev,size;
 12     node *child[2];
 13 }a[N*2];
 14 struct Ques
 15 {
 16     int flag,x,y,z;
 17 }q[N];
 18 int qm=0;
 19 node *pos,*root[N];
 20 int s[N*2];
 21 void newnode(node *&r,int key)
 22 {
 23     r=pos++;
 24     r->child[0]=r->child[1]=NULL;
 25     r->x=key;
 26     r->size=1;
 27     r->lev=rand();
 28 }
 29 void updata(node *&r)
 30 {
 31     if(r)
 32     r->size=(r->child[0]?r->child[0]->size:0)+(r->child[1]?r->child[1]->size:0)+1;
 33 } 
 34 int n;
 35 int gi()
 36 {
 37     int str=0;char ch=getchar();
 38     while(ch>'9' || ch<'0')ch=getchar();
 39     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
 40     return str;
 41 }
 42 int b[N];
 43    
 44 void rotate(node *&r,bool t)//0左旋 1右旋
 45 {
 46     node *y=r->child[!t];
 47     r->child[!t]=y->child[t];
 48     y->child[t]=r;
 49     updata(r);
 50     r=y;
 51     updata(r);
 52 }
 53 void insert(node *&r,int key)
 54 {
 55     if(r==NULL){newnode(r,key);return ;}
 56     bool t=key>r->x;
 57     insert(r->child[t],key);
 58     if(r->child[t]->lev<r->lev)rotate(r,!t);
 59     updata(r);
 60 }
 61    
 62 void Delet(node *&r,int key)
 63 {
 64     if(r==NULL)return ;
 65     if(r->x==key)
 66     {
 67         if(r->child[0] && r->child[1])
 68         {
 69             bool t=r->child[0]->lev<r->child[1]->lev;
 70             rotate(r,t);
 71             Delet(r->child[t],key);
 72          }
 73          else
 74          {
 75              if(r->child[0])r=r->child[0];
 76              else r=r->child[1];
 77          }
 78      }
 79     else Delet(r->child[key>r->x],key);
 80     updata(r);
 81 }
 82   
 83 int find(node *&r,int key)
 84 {
 85     if(r==NULL)return 0;
 86     int sum=0;
 87     if(r->x<=key){
 88         if(r->child[0])sum+=r->child[0]->size;
 89         sum++;
 90     }
 91     sum+=find(r->child[key>=r->x],key);
 92     return sum;
 93 }
 94  
 95 int py[N*2],bel[N];
 96 int ny=0;
 97 int midit(int x)//二分离散化以后该书对应的新编号 
 98 {
 99     int mid,l=1,r=ny,ans;
100     while(l<=r)
101     {
102         mid=(l+r)>>1;
103         if(py[mid]<=x)ans=mid,l=mid+1;
104         else r=mid-1;
105     }
106     return ans;
107 }
108  
109 void check(node *r)//检查时用的,可以忽略 
110 {
111     if(r==NULL)return ;
112     printf("key=%d size=%d ",r->x,r->size);
113     if(r->child[1])printf("right=%d ",r->child[1]->x);
114     if(r->child[0])printf("left=%d ",r->child[0]->x);
115     printf("n");
116     check(r->child[0]);check(r->child[1]);
117 }
118  
119 int main()
120 {
121     int m;
122     n=gi();m=gi();
123     pos=a;
124     for(int i=1;i<=n;i++)s[i]=b[i]=gi();
125     char f;int num=n;
126     for(int i=1;i<=m;i++)//现将数据全部读入,再编号 离散化。 
127     {
128         f=getchar();
129         while(f!='Q' && f!='C')f=getchar();
130         if(f=='C')
131         {
132             q[i].x=gi();q[i].y=gi();
133             s[++num]=q[i].y;
134         }
135         if(f=='Q')
136         {
137             q[i].x=gi();q[i].y=gi();q[i].z=gi();
138             q[i].flag=1;
139         }
140     }
141     sort(s+1,s+num+1); //从小到大排序,方便编号 
142     for(int i=1;i<=num;i++)if(s[i]!=s[i+1])py[++ny]=s[i];//去重 该操作之后原数组对应的新编号就是py数组的下标。 
143     int tmp;
144     for(int i=1;i<=n;i++){
145         tmp=midit(b[i]);
146         bel[i]=tmp;//Bel为在书柜i位置的书对应的平衡树root[]中的下标。 
147         insert(root[tmp],i);
148     }
149     for(int i=1;i<=m;i++)
150     {
151         if(!q[i].flag)
152         {
153             tmp=midit(q[i].y);
154             Delet(root[bel[q[i].x]],q[i].x);
155             bel[q[i].x]=tmp;
156             insert(root[tmp],q[i].x);
157         }
158         else
159         {
160             tmp=midit(q[i].z);
161             printf("%dn",find(root[tmp],q[i].y)-find(root[tmp],q[i].x-1));
162         }
163     }
164     return 0;
165 }

 

平衡树Treap,山东省treap 小J是国家图书馆的一位图书管理员,他的工作是管理一个巨大的书架。虽然他很能吃苦...

本文由9159金沙游艺场-奥门金沙游艺场-[欢迎您]发布于前端,转载请注明出处:山东省选2008

关键词:

判断一个数是不是素数【9159金沙游艺场】

C语言 达成三个函数,判定一个数是或不是素数 #define _CRT_SECURE_NO_WARNINGS 1#include stdio.h#includestdlib.hint prime(num){ int i; ...

详细>>

读取properties属性文件

读取properties属性文件——国际化,properties国际化 3.算法综合实践——搜索引擎上网搜索有关“搜索引擎”的相关资料...

详细>>

Ubuntu下使用skipfish扫描网站漏洞9159金沙游艺场

skipfish是谷歌开发网站完全扫描工具,强大易用。 #安装所需软件库: sudo apt-get install libssl0.9.8 sudo apt-get install libss...

详细>>

模拟注册登录幸运抽奖全过程

初学Java5:模拟注册登录幸运抽奖全过程,java5幸运抽奖 刚刚好不容易写了很多,结果一不小心点错,关闭了,重点是...

详细>>