[TJOI2019]甲苯先生的滚榜

[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;
}