神奇的倍增题，场上多个 草过
分。
题目链接。
题意
现在有
个城市，每一个城市有一个传送门。
第 个城市的传送门以 为周期，如果第 天进入第 个城市的传送门，你就会被传送到第 个城市。
组询问，每一次给出 。你需要于第 天进入第
个城市的传送门，并等待一天，继续进入所在城市的传送门……
求进入
次后，求所在的城市编号。
。
。
。
。
所有的 均为 的幂。
题解
设 。
这道题中，每一次询问都需要走
步，那大概率就是倍增之类的东西，考虑往倍增上想。
考虑 表示第 个时刻从城市 出发，走 到的城市。
但这个做法有一个问题。
假如我们中途走到了一个城市
满足 ，那么这个时候我们的状态就不够用了。
那么我们就只处理所有城市都不大于
的部分，并且额外计算，走了多久到达第一个 的点 。
尝试计算复杂度。
对于每一次询问，要么我们直接跳到下一个 更大的点，在 的时间内将 翻倍。
否则可以 直接往前走最大的
步，但是这样可能会到达一个
更小的点。
单组询问复杂度为 ，但是预处理的时候需要询问 次。
总复杂度为 ，可以过前
个点，但是还差 个点。
发现时间复杂度瓶颈主要在于，我们需要频繁在不同的 之间切换。
定义：称两个点 同层当且仅当
。
不妨直接令 表示，第 个时刻从城市 出发，经过的第 个同层城市是哪一个，同时记录 表示经过的时间。
此外，还需要计算
到达的第一个更高层点。
再次尝试计算复杂度。
对于预处理，我们需要优先计算
更小的城市。
对于点 与时间 ，我们的预处理分为两步，第一步是计算到达的第一个同层点，第二步是倍增。
第二步是简单的，直接倍增即可，复杂度是 。
考虑如何计算第一个同层点，首先我们先从 出发往前走一步到达每一个点 。
之后，由于低层点已经计算完毕了，每一次都只需要 的时间，直接从 跳到下一个比 层数更高的点 。
这样，我们至多跳
次就可以跳到第一个层数
的点。
故预处理的总复杂度是 。
对于一组询问来说，我们会先花 的时间走到整条路径的最高点，然后的再花 的时间将最高层走完。
那么之后走到的点，高度一定比当前点小，再走一步，然后重复上面的过程即可。
因为层数只有
种，所以最大高度只会变化
次。
故总时间复杂度为 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
vc<int>num[100001];
ll tim[100001];int e[100001];
int to[100001][70];
ll w[100001][70];
int s[100001];
int T[100001];
int n,m,cnt;
inline void init()
{
for(int lv=0;lv<=16;lv++)
{
vc<pi>nod;
for(int j=1;j<=n;j++) if(T[j]==(1<<lv)) for(int k=0;k<T[j];k++)
{
int id=s[j]+k;nod.push_back(pi(id,k));
ll t=1;int u=num[j][k];bool flag=0;
while(T[u]<T[j])
{
int nid=s[u]+((k+t)%T[u]);
if(tim[nid]==inf)
{
tim[id]=inf;
flag=1;
break;
}
t=min(t+tim[nid],inf);
u=e[nid];
}
if(!flag)
{
if(T[u]>T[j]) tim[id]=t,e[id]=u;
else to[id][0]=u,w[id][0]=t;
}
}
for(int i=1;i<=60;i++) for(auto p:nod)
{
int j=p.first,k=p.second;
if(!to[j][i-1]) continue;
ll t=w[j][i-1];int u=to[j][i-1];
int nid=s[u]+((t+k)%T[u]);
if(!to[nid][i-1]) tim[j]=min(inf,t+tim[nid]),e[j]=e[nid];
else w[j][i]=min(inf,t+w[nid][i-1]),to[j][i]=to[nid][i-1
}
for(auto p:nod)
{
int j=p.first;
if(!tim[j]) tim[j]=inf;
}
}
}
inline int get(int u,ll t,ll rest)
{
while(rest)
{
int id=s[u]+(t%T[u]);
if(rest>=tim[id])
{
t+=tim[id];
rest-=tim[id];
u=e[id];
}
else
{
for(int i=60;i>=0;i--) if(to[id][i]&&rest>=w[id][i])
{
rest-=w[id][i],t+=w[id][i],u=to[id][i];
id=s[u]+(t%T[u]);
}
if(rest)
{
u=num[u][t%T[u]];
rest--,t++;
}
}
}
return u;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) T[i]=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=T[i];j++) num[i].push_back(read());
s[i]=cnt+1,cnt+=T[i];
}
init();
for(int i=1;i<=m;i++)
{
int u=read();ll t=lread(),rest=lread();
printf("%d\n",get(u,t,rest));
}
return 0;
}
|
感谢观看！