4
20
2016
0

[bzoj]1056&1862: [HAOI2008]排名系统

这不是裸题吗?干嘛拿出来,太闲?

是是是,您教导的是

主要促使我写这题的动力是:怎么他们写的都是$splay$和$treap$?


其实这题难的,并不是题目本身。。是读入

不知道怎么$WA$的,都是读入写错了!

只有三个操作,插入,删除已有的数,查$k$大值

这个东西不就一棵权值线段树吗?写啊写,发现他如果权值一样,大小是按插入前后来排的,那简单啊,离散化的时候记插入时间就行了

不知道$Seter$写的是什么。。反正线段树跑的挺快的

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline int read(int x){char ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;}
inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
inline void Read(char*s){char ch=nc();for(;ch==' '||ch=='\n';ch=nc());for(;ch!=' '&&ch!='\n';ch=nc())*s++=ch;*s=0;}
#define N 250010
int i,j,k,m,n,f[N],humen,o,T[N<<2],v[N],M,x,l,V[N],vis[N],F,cnt,len,y;char qs[N][22],ch;
struct node{int v,t;}h[N];
inline bool operator<(const node&a,const node&b){return(a.v<b.v)||(a.v==b.v&&a.t>b.t);}
inline bool operator==(const node&a,const node&b){return a.v==b.v&&a.t==b.t;}
unsigned int hash[22],hs[N],H[N];
#define ls k<<1,l,m
#define rs k<<1|1,m+1,r
void add(int k,int l,int r,int x,int v){T[k]+=v;if(l==r)return;int m=l+r>>1;x<=m?add(ls,x,v):add(rs,x,v);}
inline int askkth(int k,int l,int r,int x){int kth=0;for(int m;l<r;)m=l+r>>1,x<=m?(kth+=T[k<<1|1],k=k<<1,r=m):(k=k<<1|1,l=m+1);return kth+1;}
inline int askknm(int k,int l,int r,int x){for(int m;l<r;)m=l+r>>1,T[k<<1|1]>=x?(k=k<<1|1,l=m+1):(x-=T[k<<1|1],k=k<<1,r=m);return l;}
int main(){
	for(n=read(),i=1;i<=n;++i){
		read(ch);
		if(ch=='+'){
			Read(qs[i]+1);
			f[i]=0,v[i]=read(),h[++cnt]=(node){v[i],i},len=strlen(qs[i]+1);
			for(j=1;j<=len;++j)hash[j]=hash[j-1]*131+qs[i][j];
			H[++l]=hs[i]=hash[len];
		}else{
			read(ch);
			if(ch>='A'){
				f[i]=k=1,qs[i][1]=ch,ch=nc();
				while(ch!=' '&&ch!='\n')qs[i][++k]=ch,ch=nc();
				for(len=strlen(qs[i]+1),j=1;j<=len;++j)hash[j]=hash[j-1]*131+qs[i][j];
				H[++l]=hs[i]=hash[len];
			}else f[i]=2,v[i]=read(ch-48);
		}
	}
	for(sort(h+1,h+cnt+1),M=unique(h+1,h+cnt+1)-h-1,i=1;i<=n;++i)if(!f[i])v[i]=lower_bound(h+1,h+M+1,(node){v[i],i})-h;
	for(sort(H+1,H+l+1),F=unique(H+1,H+l+1)-H-1,i=1;i<=n;++i)if(f[i]!=2)hs[i]=lower_bound(H+1,H+F+1,hs[i])-H;
	for(i=1;i<=n;++i){
		if(!f[i])if(vis[hs[i]])add(1,1,M,V[hs[i]],-1),add(1,1,M,V[hs[i]]=v[i],1);
		else add(1,1,M,V[hs[i]]=v[i],1),vis[hs[i]]=1,++humen;
		if(f[i]==1)
			printf("%d\n",askkth(1,1,M,V[hs[i]]));
		if(f[i]==2){
			for(j=v[i],o=min(humen,v[i]+9);j<o;++j)printf("%s ",qs[h[askknm(1,1,M,j)].t]+1);
			printf("%s\n",qs[h[askknm(1,1,M,o)].t]+1);
		}
	}
}

 

$loading...$

Category: bzoj | Tags: hash 平衡树 线段树 | Read Count: 552

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com