FHQtreap新模板

洛谷P4291

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=250005;
LL root,tot,ch[MAXN][2],siz[MAXN],pri[MAXN],val[MAXN];
string nm[MAXN];
map<string,LL>vis;
void pushup(LL rt){siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;
}
void split_val(LL rt,LL &rt1,LL &rt2,LL k){if(!rt){rt1=rt2=0;return ;}else if(k>=val[rt]){rt1=rt;split_val(ch[rt][1],ch[rt][1],rt2,k);}else{rt2=rt;split_val(ch[rt][0],rt1,ch[rt][0],k);}pushup(rt);
}
void split_rank(LL rt,LL &rt1,LL &rt2,LL k){if(!rt){rt1=rt2=0;return ;}else if(k>=siz[ch[rt][0]]+1){rt1=rt;split_rank(ch[rt][1],ch[rt][1],rt2,k-siz[ch[rt][0]]-1);}else{rt2=rt;split_rank(ch[rt][0],rt1,ch[rt][0],k);}pushup(rt);
}
LL merge(LL x,LL y){if(!x||!y)return x+y;if(pri[x]<pri[y]){ch[x][1]=merge(ch[x][1],y);pushup(x);return x;}else{ch[y][0]=merge(x,ch[y][0]);pushup(y);return y;}
}
void erase(LL k){LL x,y,z;x=y=z=0;split_val(root,x,z,k);split_val(x,x,y,k-1);root=merge(x,z);
}
LL new_node(string s,LL sc,LL tim){siz[++tot]=1;nm[tot]=s;val[tot]=sc*MAXN-tim;pri[tot]=rand();return tot;
}
void insert(string s,LL sc,LL tim){if(vis[s])erase(val[vis[s]]);vis[s]=new_node(s,sc,tim);LL x,y;x=y=0;split_val(root,x,y,val[tot]);root=merge(merge(x,tot),y);
}
void print(LL rt){if(!rt)return ;print(ch[rt][1]);cout<<nm[rt]<<" ";print(ch[rt][0]);
}
void printindex(LL k){LL nowtot=siz[root];LL x,y,z;x=y=z=0;split_rank(root,x,z,nowtot-k+1);split_rank(x,x,y,max(nowtot-k-9,0ll));print(y);printf("\n");root=merge(merge(x,y),z);
}
void printrank(string s){LL rt=vis[s];LL x,y;x=y=0;split_val(root,x,y,val[rt]);printf("%lld\n",siz[y]+1);root=merge(x,y);
}
int main(){// freopen("test.in","r",stdin);srand(time(0));LL n;scanf("%lld",&n);for(LL i=1;i<=n;i++){char opt;while(1){scanf("%c",&opt);if(opt=='+'||opt=='?')break;}if(opt=='+'){string name;cin>>name;LL num;scanf("%lld",&num);insert(name,num,i);// cout<<opt<<"*"<<name<<"*"<<num<<endl;}else{string name;cin>>name;if(name[0]>='0'&&name[0]<='9'){LL num=0;for(LL j=0;j<name.size();j++){num=num*10+name[j]-'0';}printindex(num);// cout<<opt<<"*"<<num<<endl;}else{printrank(name);// cout<<opt<<"*"<<name<<endl;}}}
}