[TJOI2019]甲苯先生的滚榜
又双叒叕来水博客了
几乎就是一个板子，虽然有两个关键字，但是实际上可以压成一个。
k=a*mo-b 其中a为过题数，b为罚时，mo=2e6，因为b<1.5e6。所以我们可以用这样一个二元组来表示。
虽然说相同的二元组可以对应不同的人，但实际上是谁不重要，重要的是有哪些数。然后就是基本的delete和insert操作，然后查询可以和insert合到一起写，这样会快一些。
刚开始看到10s，心想这不随便过，然而我还t了几发QAQ，加了快速输出和一点优化才卡到8s。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<ctime>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef unsigned int ui ;
typedef long long ll;
ui last,m,n,seed;
ui randNum( ui& seed , ui last , const ui m){
seed = seed * 17 + last ; return seed % m + 1;
}
const int N=1e5+5;
const int mo=2e6;
int ls[N],rs[N],p[N],cnt,rt,s[N],l,r,x,y,t,z,temp;
ll v[N],k,a,b,h[N];
int ss[N],top;
int New(ll x){
++cnt;
p[cnt]=rand();
v[cnt]=x;
ls[cnt]=rs[cnt]=0;
s[cnt]=1;
return cnt;
}
void upd(int x){
s[x]=s[ls[x]]+s[rs[x]]+1;
}
int build(int n){
int x,last;
top=0;
fo(i,1,n) {
x=New(0);
last=0;
while (top && p[ss[top]] < p[x]) {
upd(ss[top]);
last=ss[top];
top--;
}
if (top) {
rs[ss[top]]=x;
}
ls[x]=last;
ss[++top]=x;
}
while (top)
upd(ss[top--]);
return ss[1];
}
void split(int u,ll x,int &l,int &r){
if (!u) {
l=r=0; return;
}
if (v[u]<=x) {
l=u;
split(rs[u],x,rs[u],r);
}
else{
r=u;
split(ls[u],x,l,ls[u]);
}
upd(u);
}
int merge(int l,int r){
if (!l || !r) return l+r;
if (p[l]>p[r]) {
rs[l]=merge(rs[l],r);
upd(l);
return l;
}
else{
ls[r]=merge(l,ls[r]);
upd(r);
return r;
}
}
void del(ll x){
split(rt,x,l,r);
split(l,x-1,l,z);
cnt=z-1;
z=merge(ls[z],rs[z]);
rt=merge(l,z);
rt=merge(rt,r);
}
int tot,c[10];
inline void W(int x){
if (!x) {
puts("0");
return;
}
tot=0;
while (x){
c[++tot]=x%10;
x/=10;
}
fd(i,tot,1) {
putchar(c[i]+'0');
}
putchar('\n');
}
void ins(ll x){
z=New(x);
split(rt,x,l,r);
last=m-1-s[l];
W(last);
rt=merge(l,z);
rt=merge(rt,r);
}
int main(){
srand(time(NULL));
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int T;
last=7;
scanf("%d",&T);
while (T--) {
cnt=0;
cin >> m >> n >> seed;
fo(i,1,(int)m) h[i]=0;
rt=build(m);
fo(i,1,(int)n){
x=randNum(seed,last,m);
y=randNum(seed,last,m);
k=h[x];
if (k%mo){
a=k/mo+1;
b=a*mo-k;
}
else{
a=k/mo;
b=0;
}
a++;
b+=y;
h[x]=a*mo-b;
del(k);
ins(h[x]);
}
}
return 0;
}