4
20
2016
1

[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: 1459
Avatar_small
AP 1st Inter Botany 说:
2022年9月08日 20:06

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Question Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


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