D. Frog Traveler

$nn$为起点，要跳到地面上，每次向上跳需要比之前里地面更近（假设存在状态，如果当前有，那么之前就跑过$i>xi>x$了）（$i->ji->j$表示从地面以下$ii$米跳到地面以下$jj$米）。用队列从起点向外扩散，维护前面所有状态能够到达的最高高度$mm$，从点$ii$每次向上跳$i-a[i]\sim m-1i-a[i]\backslash sim\; m-1$，然后下滑到点$jj$，把所有没到过的点存进队列，重复操作。

因为要输出路径，而且还是下滑前的高度，所以需要记录每个点是由那个点先扩散到的，然后再存这个点是从什么位置滑下来的。

因为队列中的点向上跳跃的区间和以及遍历过的区间是不重叠的，可以知道这个算法是线性的。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+7;
int n,a[maxn],b[maxn],pre[maxn],del[maxn];
bool vis[maxn];
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) cin>>b[i];
	int m=n,now;
	queue<int>que;
	que.emplace(n);
	vis[n]=1;
	while(que.size()) {
		now=que.front();
		que.pop();
		if(now-a[now]>=m) continue;
		for(int i=now-a[now],nxt;i<m;++i) {
			nxt=i+b[i];
			if(vis[nxt]) continue;
			vis[nxt]=1,pre[nxt]=now,del[nxt]=i;
			que.emplace(nxt);
		}
		m=now-a[now];
	}
	if(!vis[0]) cout<<"-1\n";
	else {
		vector<int>ans;
		int x=0;
		do{
			ans.emplace_back(del[x]);
			x=pre[x];
		}while(x!=n);
		cout<<ans.size()<<'\n';
		for(int i=ans.size()-1;~i;--i) cout<<ans[i]<<' ';
		cout<<'\n';
	}
	return 0;
}