专栏文章

题解：P14617 [2019 KAIST RUN Fall] Hilbert' s Hotel

zzhuweiqi
P14617题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mimzhdjd
此快照首次捕获于
2025/12/01 18:05
3 个月前
此快照最后确认于
2025/12/01 18:05
3 个月前
查看原文
好题。
先考虑询问 22 怎么做，可以用乘法标记和加法标记维护每个团队的人员编号，新加一个团队时，若 k=0k=0，则相当于给之前所有团队打上一个 ×2\times 2 的乘标记，否则相当于打上一个 +k+k 的加标记，这部分可以用线段树维护，详见 P3373。查询时找出该团队的乘法标记 mulmul，和加法标记 addadd，若该团队 k=0k=0，位置即为 (2x−1)mul+add(2x-1)mul+add，否则即为 (x−1)mul+add(x-1)mul+add。
再考虑询问 33，发现这个用数据结构不太好维护，于是考虑挖掘性质，假设我们暴力的话，每遇到一个 k=0k=0 的团队，若 xx 的位置为奇数，说明答案为当前团队，否则就将 xx 除以二，继续往前查询。如果每次只跳到 k=0k=0 的团队时，可以在 log⁡x\log x 次就跳到 00，那么具体的，维护一个 kk 的前缀和，上一个 k=0k=0 的团队 laslas，设当前跳到团队 nwnw，如果 sumnw−sumk>xsum_{nw}-sum_k>x，就说明答案在这里面，一个 lower_bound 即可解决，否则将 xx 减掉上式，继续往前查询。此外，当 x=0x=0 时需要跳到最近的一个 k>0k>0 的团队，否则会假。特别注意和团队 00 有关的 corner case。综上，时间复杂度为 O(nlog⁡V)O(n\log V)。
赛时代码：（没想到居然还是首 A）
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
struct node{
	int mul,add;
}t[N<<2];
struct node0{
	int x,las,hav;
}s[N];
int sum[N];
void pd(int u){
	t[u<<1].mul=t[u<<1].mul*t[u].mul%mod;
	t[u<<1].add=(t[u<<1].add*t[u].mul+t[u].add)%mod;
	t[u<<1|1].mul=t[u<<1|1].mul*t[u].mul%mod;
	t[u<<1|1].add=(t[u<<1|1].add*t[u].mul+t[u].add)%mod;
	t[u].mul=1,t[u].add=0;
	return;
} 
int ask(int u,int l,int r,int x,int y){
	if(l==r){
		if(s[x].x==0) return (2*y-1)*t[u].mul+t[u].add;
		return (y-1)*t[u].mul+t[u].add;
	}
	pd(u);
	int mid=l+r>>1;
	if(x<=mid) return ask(u<<1,l,mid,x,y);
	return ask(u<<1|1,mid+1,r,x,y);
}
void upd(int u,int l,int r,int x,int y,int mul,int add){
	if(x<=l && r<=y){
		t[u].mul=t[u].mul*mul%mod;
		t[u].add=(t[u].add*mul+add)%mod;
		return;
	}
	pd(u);
	int mid=l+r>>1;
	if(x<=mid) upd(u<<1,l,mid,x,y,mul,add);
	if(mid<y) upd(u<<1|1,mid+1,r,x,y,mul,add);
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int Q,n=3e5,g=0,las=0,hv=0;
	for(int i=1;i<=(n<<2);i++) t[i].mul=1;
	s[0].x=1;
	cin>>Q;
	while(Q--){
		int op;
		cin>>op;
		if(op==1){
			int x;
			cin>>x;
			g++;
			s[g].x=x;
			s[g].las=las;
			s[g].hav=hv;
			if(x==0) upd(1,0,n,0,g-1,2,0),las=g;
			else upd(1,0,n,0,g-1,1,x),hv=g;
			sum[g]=sum[g-1]+x;
		}
		if(op==2){
			int num,x;
			cin>>num>>x;
			cout<<ask(1,0,n,num,x)%mod<<"\n";
		}
		if(op==3){
			int x;
			cin>>x;
			int nw=g,ans=0;
			if(s[nw].x==0){
				if(x%2==1) ans=nw;
				x/=2;
			}
			else if(s[nw].x>x) ans=nw;
			while(ans==0 && nw){
				if(x==0){
					ans=s[nw].hav;
					break;
				}
				if(sum[nw]-sum[s[nw].las]>x){
					ans=lower_bound(sum,sum+nw+1,sum[nw]-x)-sum;
					break;
				}
				x-=sum[nw]-sum[s[nw].las];
				nw=s[nw].las;
				if(x%2==1){
					ans=nw;
					break;
				}
				x/=2;
			}
			cout<<ans<<"\n";
		} 
	}
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...