代码:
```cpp
#include <bits/stdc++.h>
#define gc IO::fastgc()
#define pc(c) IO::fastpc(c)
//#define gc getchar()
//#define pc putchar
#define int long long
using namespace std;
namespace IO{
char ibuf[1<<23],obuf[1<<23],*ip1=ibuf,*ip2=ibuf,*o=obuf;
inline char fastgc(){
return ((ip1==ip2)&&(ip2=(ip1=ibuf)+fread(ibuf,1,1<<21,stdin),ip1==ip2)?EOF:*ip1++);
}
inline void fastpc(char c){
*(o++)=c;
}
inline bool isspc(char c){
return c==' '||c=='\t'||c=='\r'||c=='\n'||c==0||c==EOF;
}
inline int readi(){
register int t=0,f=1;
register char c=gc;
while(c!='-'&&(c<'0'||c>'9')) c=gc;
if(c=='-') c=gc,f=-1;
while(c>='0'&&c<='9') t=10*t+(c^48),c=gc;
return f*t;
}
inline char readc(){
register char c=gc;
while(isspc(c)) c=gc;
return c;
}
inline void reads(string &buf){
buf="";
register char c=gc;
while(isspc(c)) c=gc;
while(!isspc(c)) buf+=c,c=gc;
}
inline void writei(int x){
if(!x) return (void)pc('0');
if(x<0) pc('-'),x=-x;
static char c[33]={""};
static int cc=0;
while(x) c[++cc]=x%10,x/=10;
while(cc) pc(c[cc--]|48);
}
inline void writes(const string &s){
for(auto c:s) pc(c);
}
inline void flush(){
fwrite(obuf,o-obuf,1,stdout);
}
struct IO_Flusher{
inline IO_Flusher(){}
inline ~IO_Flusher(){
flush();
}
}__io_flusher_;
}
using IO::readi;
using IO::readc;
using IO::reads;
using IO::writei;
using IO::writes;
const int N=2000007,INF=LLONG_MAX;
mt19937 mtrand(random_device{}());
int n,idcnt;
string name[N];
unordered_map<string,int> id;
struct Info{
int id,v;
inline bool operator==(const Info &ib)const{
return v==ib.v&&id==ib.id;
}
inline bool operator<(const Info &ib)const{
if(v==ib.v) return id<ib.id;
return v>ib.v;
}
inline bool operator>(const Info &ib)const{
return ib<(*this);
}
inline bool operator<=(const Info &ib)const{
return (*this)<ib||(*this)==ib;
}
inline bool operator>=(const Info &ib)const{
return ib<=(*this);
}
};
struct Node{
Info v;
int dat,s[2],sz;
}tr[N];
int ncnt,rt,rclstk[N],rclstktop;
int score[N];
inline int tonum(const string &s){
int t=0;
for(int i:s){
if(i<'0'||i>'9') return -1;
t=10*t+(i&15);
}
return t;
}
inline int newnodeid(){
if(rclstktop) return rclstk[rclstktop--];
return (++ncnt);
}
inline int newnode(Info v){
int u=newnodeid();
tr[u].v=v,
tr[u].dat=mtrand(),
tr[u].s[0]=tr[u].s[1]=0;
tr[u].sz=1;
return u;
}
inline void recycle(int u){
rclstk[++rclstktop]=u;
}
inline void pushup(int u){
tr[u].sz=tr[tr[u].s[0]].sz+tr[tr[u].s[1]].sz+1;
}
inline void rotate(int &x,int d){
int y=tr[x].s[d^1],z=tr[y].s[d];
tr[x].s[d^1]=z;
tr[y].s[d]=x;
x=y;
pushup(tr[x].s[d]),
pushup(x);
}
inline void init(){
tr[0].dat=-INF;
rt=newnode(Info{-INF,INF});
tr[rt].s[1]=newnode(Info{INF,-INF});
pushup(rt);
if(tr[tr[rt].s[1]].dat>tr[rt].dat){
rotate(rt,0);
}
}
void insert(int &u,Info v){
if(!u){
u=newnode(v);
return;
}
int d=(v>=tr[u].v);
insert(tr[u].s[d],v);
pushup(u);
if(tr[tr[u].s[d]].dat>tr[u].dat){
rotate(u,d^1);
}
}
void del(int &u,Info v){
if(!u){
return;
}
if(tr[u].v==v){
if(tr[u].s[0]||tr[u].s[1]){
if(!tr[u].s[0]){
rotate(u,0);
del(tr[u].s[0],v);
}
else if(!tr[u].s[1]){
rotate(u,1);
del(tr[u].s[1],v);
}
else if(tr[tr[u].s[1]].dat>tr[tr[u].s[0]].dat){
rotate(u,0);
del(tr[u].s[0],v);
}
else{
rotate(u,1);
del(tr[u].s[1],v);
}
pushup(u);
}
else{
recycle(u);
u=0;
}
return;
}
int d=(v>=tr[u].v);
del(tr[u].s[d],v);
pushup(u);
}
int query_rk(int u,Info v){
if(!u){
return 0;
}
if(tr[u].v==v){
return tr[tr[u].s[0]].sz+1;
}
else if(v<tr[u].v){
return query_rk(tr[u].s[0],v);
}
else{
return tr[tr[u].s[0]].sz+1+query_rk(tr[u].s[1],v);
}
}
Info query_kth(int u,int k){
if(!u){
return Info{0,0};
}
int sz0=tr[tr[u].s[0]].sz;
if(sz0+1==k){
return tr[u].v;
}
else if(sz0>=k){
return query_kth(tr[u].s[0],k);
}
else{
return query_kth(tr[u].s[1],k-sz0-1);
}
}
inline void queryindex(int x){
for(int i=x;i<=min(x+9,idcnt);++i){
Info t=query_kth(rt,i+1);
writes(name[t.id]),pc(' ');
}
pc('\n');
}
inline void queryname(const string &s){
int x=id[s];
int rk=query_rk(rt,Info{x,score[x]})-1;
writei(rk),pc('\n');
}
inline void doquery(const string &s){
int t=tonum(s);
if(~t){
queryindex(t);
}
else{
queryname(s);
}
}
signed main(){
string x;int sc;
n=readi();
init();
while(n--){
switch(readc()){
case '+':{
int t;
reads(x);
sc=readi();
if(id.count(x)){
t=id[x];
}
else{
t=(++idcnt);
name[t]=x;
id[x]=t;
}
del(rt,Info{t,score[t]});
score[t]=sc;
insert(rt,Info{t,score[t]});
break;
}
case '?':{
reads(x);
doquery(x);
break;
}
}
}
return 0;
}
```
by rzh123 @ 2022-07-31 17:13:44
(不是 TLE,是 WA)
by rzh123 @ 2022-07-31 17:15:34
@[rzh123](/user/237530) 那我觉得大概率你写锅了?![](//图.tk/e)
treap正确性应该没问题吧
by happybob @ 2022-07-31 17:48:44
@[happybob](/user/332914) 那麻烦您看一看我哪里写锅了?
by rzh123 @ 2022-07-31 17:49:53
我也觉得是我写锅了
by rzh123 @ 2022-07-31 17:51:11
@[rzh123](/user/237530) 我只是说说罢了。
treap我早忘了?
我看看吧。
by happybob @ 2022-07-31 17:51:55
@[happybob](/user/332914) 谢谢大佬
by rzh123 @ 2022-07-31 17:52:22
我现在发现的一个错是不存在也会执行一次 `del`,但这个应该不影响 Treap,改了还是一样的
by rzh123 @ 2022-07-31 17:53:07
@[rzh123](/user/237530) 完了我调不出来
我都几个月没碰treap了全忘了![](//图.tk/7)
我这就去补一下
by happybob @ 2022-07-31 17:53:52
@[happybob](/user/332914) 谢谢大佬
by rzh123 @ 2022-07-31 17:54:54