萌新求调FHQ qwq
查看原帖
萌新求调FHQ qwq
311306
dk_qwq楼主2023/4/21 19:58

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("");
            }
		}
    }
}

2023/4/21 19:58
加载中...