倍增¶
例题 #1 [POI2010] ZAB-Frog¶
有 \(n\) 个点，升序给出每个点到起点的距离。有编号为 \(1 \sim n\) 的 \(n\) 只青蛙分别在第 \(1 \sim n\) 个点上，每次它们会跳到距离自己第 \(k\) 近的点上。
如果有相同距离的点，就跳到下标更小的点上。
求跳 \(m\) 次之后，第 \(i\) 只的青蛙在哪个点上。
输入共一行三个整数：代表 \(n, k, m\)。
输出共一行 \(n\) 个整数，代表每只青蛙最终所处在的点。
预处理出每个点第k远的点。这个可以使用双指针。
具体来说，就是维护两个相距k的指针l,r。每次要求出\(nxt_i\)时比较l,r到i的距离。
然后在i→i+1时，比较r+1,l到i的距离。如果r+1更近，那么l,r向右移动一位。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s << ' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
const int N = 1e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int d[N];
signed nxt[N][66];
signed main(){
int n=rd,K=rd,m=rd;
for(int i=1;i<=n;i++){
d[i]=rd;
}
int l=1,r=K+1;
for(int i=1;i<=n;i++){
// dbg(i,l,r,el);
if(d[r]-d[i]>d[i]-d[l])nxt[i][0]=r;
else nxt[i][0]=l;
if(i<n)while(r<n&&d[r+1]-d[i+1]<d[i+1]-d[l])l++,r++;
}
for(int i=1;i<=62;i++){
for(int j=1;j<=n;j++){
nxt[j][i]=nxt[nxt[j][i-1]][i-1];
}
}
for(int i=1;i<=n;i++){
int cur=i;
int kk=m;
for(int i=62;~i;i--){
if(kk>=(1ll<<i)){
cur=nxt[cur][i];
kk-=1ll<<i;
}
}
cout<<cur<<' ';
}
}
例题 #2 [SCOI2015] 国旗计划¶
题目描述
A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了 \(N\) 名优秀的边防战士作为这项计划的候选人。
A 国幅员辽阔，边境线上设有 \(M\) 个边防站，顺时针编号 \(1\) 至 \(M\)。每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。\(N\) 名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。
现在，国土安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划。不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。
输入格式
第一行，包含两个正整数 \(N,M\)，分别表示边防战士数量和边防站数量。
随后 \(N\) 行，每行包含两个正整数。其中第 \(i\) 行包含的两个正整数 \(C_i\)、\(D_i\) 分别表示 \(i\) 号边防战士常驻的两个边防站编号，\(C_i\) 号边防站沿顺时针方向至 \(D_i\) 号边防站力他的奔袭区间。数据保证整个边境线都是可被覆盖的。
输出格式
输出数据仅 \(1\) 行，需要包含 \(N\) 个正整数。其中，第 \(j\) 个正整数表示 \(j\) 号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。
\(N\leqslant 2×10^5,M<10^9,1\leqslant C_i,D_i\leqslant M\)。
首先**断环为链**，复制一份放在后面。不要用取模法，那个太麻烦。
然后处理出每个人向后走应该走到那个人（即给谁接力）
因为没有区间包含的情况，所以一定是走到左端点最靠后的且与当前区间有交的那个人那里。这个可以尺取，O(n)，没必要上单调栈
然后直接构造倍增数组即可。每次从x出发时，倍增走到一个y使得y的右端点>x+m即可。
注意要像lca一样不可到达，只能到前一个位置。
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define itn int
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pf first
#define ps second
#define cdbg(x) cerr<<#x<<" = "<<x<<'\n';
#define rd read()
inline int read(){
int x;
cin>>x;
return x;
}
const int N=6e5+5;
const int M=2e5+5;
const int INF=1e18;
const int MOD=998244353;
/*
策略
考虑倍增
f_{i,j}表示从第i个人出发，传递2^j个人时传递到的人和下标
*/
struct node{
itn a,b;
int id;
}t[N];
// struct edge{
// int x,d;//下一个人，总距离
// }
int f[N][22];
bool cmp(node a,node b){
return a.a<b.a;
}
int n,m;
// list<int> ls;
// int nxt[N];
void init (){
int x=1;
for(int i=1;i<=n;i++){
while(x<=n&&t[x].a<=t[i].b)x++;
f[i][0]=x-1;
}
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
}
int ans[N];
void solve(int x,int b){
int id=t[x].id;
int res=1;
for(int i=18;~i;i--){
if(f[x][i]&&t[f[x][i]].b<b+m){x=f[x][i],res+=1ll<<i;}
}
// while(1){
// if(len==m)break;
// }
ans[id]=res+1;
}
void solve(){
n=rd,m=rd;
for(int i=1;i<=n;i++){
//二倍法解决环问题
t[i].id=t[i+1].id=i;
t[i].a=rd;
t[i].b=rd;
if(t[i].a>t[i].b)t[i].b+=m;
}
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;i++){
t[i+n].a=t[i].a+m;
t[i+n].b=t[i].b+m;
}
n<<=1;
init();
for(int i=1;i<=n/2;i++){
solve(i,t[i].a);
}
for(int i=1;i<=n/2;i++){
cout<<ans[i]<<' ';
}
}
signed main(){
int T=1;
while(T--){
solve();
// if(T)puts("");
}
return 0;
}