【题解】Luogu P5338 [TJOI2019]甲苯先生的滚榜

原题传送门

这题明显可以平衡树直接大力整，所以我要说一下线段树+树状数组的做法

实际线段树+树状数组的做法也很暴力

我们先用树状数组维护每个ac数量有多少个队伍。这样就能快速求出有多少队伍ac数比现在这个队伍ac数多

我们再用\(n\)棵动态开点的线段树，第\(i\)棵线段树维护的是ac数为\(i\)的队伍的罚时情况。当一个队伍ac数为\(x\)罚时为\(t\)时，就在第\(x\)棵线段树\(t\)上加一。这样就能快速求出有多少队伍ac数与现在这个队伍ac数相同且罚时更少

当一个队伍过了一题后就在线段树和树状数组中正常修改即可

#include <bits/stdc++.h>

#define M 1000005

#define N 150005

#define ML 1500005

#define uint unsigned int

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

uint randNum(uint& seed,uint last,const uint mod)

{

	seed=17*seed+last;

	return seed%mod+1;

}

struct bit{

	int tr[N];

	inline void init()

	{

		memset(tr,0,sizeof(tr));

	}

	inline void update(register int pos,register int val)

	{

		for(register int i=pos;i<N;i+=i&(-i))

			tr[i]+=val;

	}

	inline int query(register int pos)

	{

		int res=0;

		for(register int i=pos;i;i-=i&(-i))

			res+=tr[i];

		return res;

	}

}tr1;

struct segt{

	struct node{

		int ls,rs,sum;

	}tr[M*40];

	int tot,root[N];

	inline void init()

	{

		memset(root,0,sizeof(root));

		tot=0;

	}

	inline void update(register int &rt,register int l,register int r,register int pos,register int val)

	{

		if(!rt)

		{

			rt=++tot;

			tr[rt].ls=tr[rt].rs=tr[rt].sum=0;

		}

		if(l==r)

		{

			tr[rt].sum+=val;

			return;

		}

		int mid=l+r>>1;

		if(pos<=mid)

			update(tr[rt].ls,l,mid,pos,val);

		else

			update(tr[rt].rs,mid+1,r,pos,val);

		tr[rt].sum=tr[tr[rt].ls].sum+tr[tr[rt].rs].sum;

	}

	inline int query(register int &rt,register int l,register int r,register int L,register int R)

	{

		if(!rt)

			return 0;

		if(L<=l&&r<=R)

			return tr[rt].sum;

		int mid=l+r>>1,res=0;

		if(L<=mid)

			res+=query(tr[rt].ls,l,mid,L,R);

		if(R>mid)

			res+=query(tr[rt].rs,mid+1,r,L,R);

		return res;

	}

}tr2;

uint seed,last;

int T,n,m,tim[N],num[N];

int main()

{

	T=read();

	last=7;

	while(T--)

	{

		m=read(),n=read(),seed=read();

		memset(num,0,sizeof(num));

		memset(tim,0,sizeof(tim));

		tr1.init(),tr2.init();

		for(register int i=1;i<=m;++i)

			num[i]=1,tim[i]=1;

		tr1.update(1,m),tr2.update(tr2.root[1],1,ML,1,m);

		for(register int i=1;i<=n;++i)

		{

			int p=randNum(seed,last,m),v=randNum(seed,last,m);

			tr1.update(num[p],-1);

			tr2.update(tr2.root[num[p]],1,ML,tim[p],-1);

			++num[p],tim[p]+=v;

			tr1.update(num[p],1);

			tr2.update(tr2.root[num[p]],1,ML,tim[p],1);

			int res=m-tr1.query(num[p]);

			res+=tr2.query(tr2.root[num[p]],1,ML,1,tim[p]-1);

			last=res;

			write(res),puts("");

		}

	}

	return 0;

}

巴特西

【题解】Luogu P5338 [TJOI2019]甲苯先生的滚榜

原题传送门

这题明显可以平衡树直接大力整，所以我要说一下线段树+树状数组的做法

实际线段树+树状数组的做法也很暴力

我们先用树状数组维护每个ac数量有多少个队伍。这样就能快速求出有多少队伍ac数比现在这个队伍ac数多

当一个队伍过了一题后就在线段树和树状数组中正常修改即可

最新文章

热门文章