原题链接洛谷P5338 [TJOI2019]甲苯先生的滚榜

题目描述

甲苯先生在制作一个online judge，他发现做比赛的人们很关心自己的排名(显而易见),在acm赛制的比赛中，如果通过题目数量不相等，则通过题目数量多的人排名更靠前，如果通过题目数量相等，

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

则罚时更少的人排名更高。甲苯先生想让大家帮忙设计一个程序，每次有人通过之后，就告诉他排名在他的前面有多少人。(不包括和他罚时题数都相同的同学)

输入输出格式

输入格式：

 

第一行输入一个整数T表示样例数。

对于每一个样例:输入三个整数m, n, seed。m表示参赛总人数(编号1−m)，n表示一共有n次accept(假设accept已经去重，即不存在相同人的相同题目提交)。seed表示生成数据的种子。

接下来要求同学们使用之下的函数生成数据

typedef unsigned int ui;
    ui randNum(ui& seed, ui last, const ui m) {
    seed = seed * 17 + last;
    return seed % m + 1;
}
（last为上一次输出的结果,在没有输出结果时last=7)

要求每次生成两个数据Ria, Rib 表示Ria的人Accept了一道题目，他的罚时为Rib。（也就是说Ria的题目数量+1，罚时长度+Rib）。

要求一共生成n组数据，代表一共有n次提交

对于所有数据，保证罚时总和不超过1500000

 

输出格式：

 

每次提交输出一行整数，表示Ria在ac后比Ria成绩高的有多少选手。

 

输入输出样例

输入样例#1：  复制 
1
7 3 1
输出样例#1：  复制 
0
1
0

说明 

测试点#　　1, 2　　　　3, 4 　　　　5 　　　6, 7, 8　　　　9, 10   

T　　　　　≤10　　　　≤5 　　　　≤15　　　　≤5　　　　　　≤5   

m　　　　　≤1000　　　≤10000 　　≤10^5　　　≤10^4　　　　　≤10^5   

n　　　　　≤1000 　　≤10000 　　≤10^5　　　≤10^6　　　　　≤10^6 

题解

Method1：平衡树

这题要动态维护排名，很容易想到平衡树（根据两个关键字维护排序二叉树）

实现：

0.初始化

(1)定义node表示状态，包含AC数目，罚时两个成员，建立平衡树

struct node{
    int ac,fine;
    node(){
        ac=fine=0;
    }
    node(int x,int y){
        ac=x;
        fine=y;
    }
    friend inline bool operator<(node x,node y){
        if(x.ac!=y.ac)
            return x.ac>y.ac;
        return x.fine<y.fine;
    }
}key[MAXN],A[MAXN];

1.更新

查找原状态并删除（A是按照编号查询的备份状态），更新状态并插入

if(A[ii].ac)
    del(A[ii]);
A[ii].ac++;
A[ii].fine+=jj;
ins(A[ii]);

 

2.查询排名

直接查找find的排名即可

last=find(A[ii]);
printf("%d\n",last);

splay代码（因为我写的splay常数极大，TLE了）

洛谷P5338 [TJOI2019]甲苯先生的滚榜 随笔 第1张 
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int INF=1e9+7,MAXN=1e5+5;
  5 struct node{
  6     int ac,fine;
  7     node(){
  8         ac=fine=0;
  9     }
 10     node(int x,int y){
 11         ac=x;
 12         fine=y;
 13     }
 14     friend inline bool operator<(node x,node y){
 15         if(x.ac!=y.ac)
 16             return x.ac>y.ac;
 17         return x.fine<y.fine;
 18     }
 19     friend inline bool operator==(node x,node y){
 20         return x.ac==y.ac&&x.fine==y.fine;
 21     }
 22 }key[MAXN],A[MAXN];
 23 int cnt[MAXN],ch[MAXN][2],siz[MAXN],f[MAXN];
 24 int root,sz;
 25 inline void clear(int x){
 26     key[x].ac=key[x].fine=cnt[x]=ch[x][0]=ch[x][1]=siz[x]=f[x]=0;
 27 }
 28 inline int get(int x){
 29     return x==ch[f[x]][1];
 30 }
 31 inline void upd(int x){
 32     if(x){
 33         siz[x]=cnt[x];
 34         if(ch[x][0]){
 35             siz[x]+=siz[ch[x][0]];
 36         }
 37         if(ch[x][1]){
 38             siz[x]+=siz[ch[x][1]];
 39         }
 40     }
 41 }
 42 inline void rotate(int x){
 43     int fa=f[x],gf=f[fa],which=get(x);
 44     ch[fa][which]=ch[x][which^1];
 45     f[ch[fa][which]]=fa; 
 46     ch[x][which^1]=fa;
 47     f[fa]=x;
 48     f[x]=gf;
 49     if(gf){
 50         ch[gf][ch[gf][1]==fa]=x;
 51     }
 52     upd(fa);
 53     upd(x);
 54 }
 55 inline void splay(int x){
 56     for(int fa;(fa=f[x]);rotate(x)){
 57         if(f[fa]){
 58             rotate(get(x)==get(fa)?fa:x);
 59         }
 60     }
 61     root=x;
 62 }
 63 inline void ins(node x){
 64     if(!root){
 65         sz++;
 66         clear(sz);
 67         root=sz;
 68         cnt[sz]=siz[sz]=1;
 69         key[sz]=x;
 70         return;
 71     }
 72     int cur=root,fa=0;
 73     while(1){
 74         if(x==key[cur]){
 75             cnt[cur]++;
 76             upd(cur);
 77             upd(fa);
 78             splay(cur);
 79             return;
 80         }
 81         fa=cur;
 82         cur=ch[fa][key[fa]<x];
 83         if(!cur){
 84             clear(++sz);
 85             f[sz]=fa;
 86             cnt[sz]=siz[sz]=1;
 87             ch[fa][key[fa]<x]=sz;
 88             key[sz]=x;
 89             upd(fa);
 90             splay(sz);
 91             return;
 92         }
 93     }
 94 }
 95 inline int find(node x){
 96     int cur=root,ret=0;
 97     while(1){
 98         if(x<key[cur]){
 99             cur=ch[cur][0];
100         }else{
101             ret+=(ch[cur][0]?siz[ch[cur][0]]:0);
102             if(key[cur]==x){
103                 splay(cur);
104                 return ret;/*return ret+1*/
105             }
106             ret+=cnt[cur];
107             cur=ch[cur][1];
108         }
109     }
110 }
111 inline node findx(int x){
112     int cur=root;
113     while(1){
114         if(ch[cur][0]&&x<=siz[ch[cur][0]]){
115             cur=ch[cur][0];
116         }else{
117             int tmp=(ch[cur][0]?siz[ch[cur][0]]:0)+cnt[cur];
118             if(x<=tmp){
119                 return key[cur];
120             }
121             x-=tmp;
122             cur=ch[cur][1];
123         }
124     }
125 }
126 inline int pre(){
127     int cur=ch[root][0];
128     while(ch[cur][1]){
129         cur=ch[cur][1];
130     }
131     return cur;
132 }
133 inline int nxt(){
134     int cur=ch[root][1];
135     while(ch[cur][0]){
136         cur=ch[cur][0];
137     }
138     return cur;
139 }
140 inline void del(node x){
141     find(x);
142     if(cnt[root]>1){
143         cnt[root]--;
144         upd(root);
145         return;
146     }
147     if(!ch[root][0]&&!ch[root][1]){
148         clear(root);
149         root=0;
150         return;
151     }
152     if(!ch[root][0]){
153         int old=root;
154         root=ch[root][1];
155         f[root]=0;
156         clear(old);
157         return;
158     }
159     if(!ch[root][1]){
160         int old=root;
161         root=ch[root][0];
162         f[root]=0;
163         clear(old);
164         return;
165     }
166     int old=root,p=pre();
167     splay(p);
168     ch[root][1]=ch[old][1];
169     f[ch[old][1]]=root;
170     clear(old);
171     upd(root);
172 }
173 int Task;
174 int N;
175 unsigned int M,seed,last=7;
176 inline unsigned int randNum() {
177     seed=seed*17+last;
178     return seed%M+1;
179 }
180 int main(){
181     scanf("%d",&Task);
182     while(Task--){
183         scanf("%d%d%d",&M,&N,&seed);
184         root=sz=0;
185         memset(A,0,sizeof(A));
186         memset(cnt,0,sizeof(cnt));
187         memset(ch,0,sizeof(ch));
188         memset(siz,0,sizeof(siz));
189         memset(f,0,sizeof(f));
190         for(int i=1;i<=N;i++){
191             int ii=randNum(),jj=randNum();
192             if(A[ii].ac)
193                 del(A[ii]);
194             A[ii].ac++;
195             A[ii].fine+=jj;
196             ins(A[ii]);
197             last=find(A[ii]);
198             printf("%d\n",last);
199         }
200     }
201     return 0;
202 }
View Code

 

splay不够快，但又不会别的算法，怎么办？用红黑树rb_tree！

rb_tree代码太长，不会写怎么办？用平板电视pbds！

rb_tree代码

洛谷P5338 [TJOI2019]甲苯先生的滚榜 随笔 第3张 
 1 #include<bits/stdc++.h>
 2 #include <ext/pb_ds/tree_policy.hpp>
 3 #include <ext/pb_ds/assoc_container.hpp>
 4 using namespace __gnu_pbds;
 5 using namespace std;
 6 typedef long long LL;
 7 const int MAXN=1e5+7;
 8 const LL INF=1.5e14,UNIT=1e7;
 9 struct node{
10     int ac,order;
11     LL fine;
12     node(){ ac=fine=order=0; }
13     node(int x,int y,int z){ ac=x; fine=y; order=z; }
14     friend bool operator<(node x,node y){
15         if(x.ac!=y.ac)
16             return x.ac>y.ac;
17         if(x.fine!=y.fine)
18             return x.fine<y.fine;
19         return x.order<y.order;
20     }
21 };
22 tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> q;
23 int Task;
24 int N;
25 unsigned M,seed,last=7;
26 inline unsigned int randNum() {
27     seed=seed*17+last;
28     return seed%M+1;
29 }
30 int ac[MAXN];
31 LL fine[MAXN];
32 int main(){
33     scanf("%d",&Task);
34     while(Task--){
35         scanf("%d%d%d",&M,&N,&seed);
36         q.clear();
37         memset(ac,0,sizeof(ac));
38         memset(fine,0,sizeof(fine));
39         for(unsigned int i=1;i<=M;i++){
40             q.insert(node(0,fine[i],i));
41         }
42         for(int i=1;i<=N;i++){
43             unsigned int ii=randNum();
44             unsigned long long jj=randNum();
45             q.erase(node(ac[ii],fine[ii],ii));
46             ac[ii]++;
47             fine[ii]+=jj;
48             q.insert(node(ac[ii],fine[ii],ii));
49             last=q.order_of_key(node(ac[ii],fine[ii],0));
50             printf("%d\n",last);
51         }
52     }
53     return 0;
54 }
View Code

 

 

 

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄