rt,已知问题:输出跟着seed变
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
template<typename T>
inline T read(){
T x=0,p=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())
if(ch=='-') p=-1;
for(;ch>='0'&&ch<='9';ch=getchar())
x=(x<<3)+(x<<1)+(ch^48);
return x*p;
}
struct Player{
int score,id;
Player() {}
Player(int score,int id):
score(score),id(id){}
friend bool operator<(const Player& a,const Player& b){
return a.score==b.score?a.id<b.id:a.score>b.score;
}
friend bool operator<=(const Player& a,const Player& b){
return a.score==b.score?a.id<=b.id:a.score>b.score;
}
Player operator-(int x){
return Player(score,id-1);
}
};
const int N=15;
template<typename T=int>
struct FHQ{
int seed=0;//关注永雏塔菲谢谢喵
int rand(){return seed=(seed*114514)%998244353;}
T val[N];
int lc[N],rc[N],siz[N];
int Priority[N];
int tot,Root;
int Create(T v){
int root=++tot;
val[root]=v;
Priority[root]=rand();
lc[root]=rc[root]=0,siz[root]=1;
return root;
}
void updata(int p){
siz[p]=siz[lc[p]]+siz[rc[p]]+1;
}
void split(int root,T k,int &x,int &y){
if(!root) return x=0,y=0,void(0);
if(val[root]<=k) split(rc[root],k,rc[x=root],y);
else split(lc[root],k,x,lc[y=root]);
updata(root);
}
void split(int root,int sz,int &x,int &y){
if(root==0) return x=0,y=0,void(0);
if(siz[lc[root]]+1<=sz)
split(rc[root],sz-siz[lc[root]]-1,rc[x=root],y);
else
split(lc[root],sz,x,lc[y=root]);
updata(root);
}
int merge(int x,int y){
if(x==0||y==0) return x+y;
if(Priority[x]>Priority[y]){
rc[x]=merge(rc[x],y);
updata(x);
return x;
}
lc[y]=merge(x,lc[y]);
updata(y);
return y;
}
void insert(T v){
int x,y;
split(Root,v-1,x,y);
Root=merge(merge(x,Create(v)),y);
}
void remove(T v){
int x,y,z;
split(Root,v,x,z);
split(x,v-1,x,y);
if(y){
y=merge(lc[y],rc[y]);
}
Root=merge(merge(x,y),z);
}
int rank(T v){
int x,y,ans;
split(Root,v-1,x,y);
ans=siz[x]+1;
Root=merge(x,y);
return ans;
}
void DFS(int root,vector<T> &s){
if(!root) return ;
if(lc[root]) DFS(lc[root],s);
s.push_back(val[root]);
if(rc[root]) DFS(rc[root],s);
}
void out(int k,int num,vector<T> &s){
int x,y,z;
split(Root,k-1,x,y);
split(y,num,y,z);
cout<<siz[x]<<' '<<siz[y]<<' '<<siz[z]<<endl;
DFS(y,s);
Root=merge(x,merge(y,z));
}
};
FHQ<Player>Tree;
#include<map>
#include<string>
map<string,Player>players;//score id
map<int,string>names;//id names
string op,name;
int n,score;
vector<Player>d;
int main(){
// freopen("P2584.in","r",stdin);
// freopen("P2584.out","w",stdout);
n=read<int>();
for(int i=1;i<=n;i++){
cin>>op;
if(op[0]=='+') score=read<int>();
if(op[1]<'0'||op[1]>'9') name=op.substr(1);
else {
score=0;
for(auto ch:op)
if(ch<='9'&&ch>='0') score=(score*10)+(ch^48);
}
if(op[0]=='+'){
if(players.count(name)) Tree.remove(players[name]);
players[name]=Player(score,i);
names[i]=name;
Tree.insert(players[name]);
}
if(op[0]=='?'){
if(op[1]<'0'||op[1]>'9') printf("%d\n",Tree.rank(players[name]));
else {
d.clear();
Tree.out(score,10,d);
for(auto ed:d) cout<<names[ed.id]<<' ';
puts("");
}
}
}
}