fhq-treap做法
这道题目涉及到了多关键字排序和字符串的一点小问题,是综合性较强的一道题目
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,times,cntt;
const int maxn=3e5+5;
map <string,int> G;
struct rec
{
int score,id,no;
};
struct fhq_treap
{
int siz,l,r,rnd;
rec v;
}tr[maxn];
struct ee
{
char name[15];
rec v;
}a[maxn];
bool operator<(const rec &a, const rec &b) {
return (a.score > b.score) || (a.score == b.score && a.id < b.id);
}
bool operator==(const rec &a, const rec &b) {
return a.score == b.score && a.id == b.id;
}
bool operator>=(const rec &a, const rec &b) {
return !(a<b);
}
int root,tot;
void pushup(int now)
{
tr[now].siz=tr[tr[now].l].siz+tr[tr[now].r].siz+1;
}
int merge(int x,int y)
{
if(!x || !y) return x+y;
if(tr[x].rnd<=tr[y].rnd)
{
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}
else
{
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
void split(int now,rec k,int &x,int &y)
{
if(!now) x=0,y=0;
else
{
if(k>=tr[now].v)
{
x=now;
split(tr[now].r,k,tr[x].r,y);
}
else
{
y=now;
split(tr[now].l,k,x,tr[now].l);
}
pushup(now);
}
}
void del(rec val)
{
int x,y,z;
split(root,val,x,z);
rec v2;
v2.score=val.score; v2.id=val.id-1;
split(x,v2,x,y);
y=merge(tr[y].l,tr[y].r);
root=merge(merge(x,y),z);
return;
}
int read(char *s)
{
int ans = 0;
while (*s != '\0') {
ans = ans * 10 + (*s) - '0';
s++;
}
return ans;
}
int newnode(rec val)
{
tot++;
tr[tot].siz=1;
tr[tot].v=val; tr[tot].rnd=rand();
return tot;
}
void insert(rec val)
{
int x,y;
split(root,val,x,y);
root=merge(x,merge(newnode(val),y));
}
char op[105];
string str;
rec kth(int x,int k)
{
if(tr[tr[x].l].siz>=k)
return kth(tr[x].l,k);
else if(tr[tr[x].l].siz+1==k) return tr[x].v;
else return kth(tr[x].r,k-tr[tr[x].l].siz-1);
}
int rnk(rec val)
{
val.id--;
int x,y;
split(root,val,x,y);
int ans=tr[x].siz+1;
root=merge(x,y);
return ans;
}
void ldr(int x)
{
if(tr[x].l) ldr(tr[x].l);
printf("%s ",a[tr[x].v.no].name);
if(tr[x].r) ldr(tr[x].r);
}
void getrank(int val)
{
rec l=kth(root,val),r=kth(root,min(cntt,val+9));
l.id--;
int x,y,z;
split(root,l,x,y);
split(y,r,y,z);
ldr(y);
printf("\n");
root=merge(x,merge(y,z));
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d",&n);
int x;
for(int i=1;i<=n;i++)
{
scanf("%s",op);
if(op[0]=='+')
{
scanf("%d",&x);
++times;
str=op+1;
int id=G[str];
if(id) del(a[id].v);
else
{
G[str]=++cntt;
id=cntt;
for(int k=0;k<(int)str.length();k++)
a[id].name[k]=str[k];
a[id].v.no=id;
}
a[id].v.score=x;
a[id].v.id=times;
insert(a[id].v);
}
else
{
if(op[1]>='0' && op[1]<='9')
{
x=read(op+1);
getrank(x);
}
else
{
str=op+1;
int id=G[str];
printf("%d\n",rnk(a[id].v));
}
}
}
return 0;
}