P4155 国旗计划
这道题的关键可能是这句话
每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。
得知每个区间向右达到的最远距离是递增的
具体实现是环->链，随后把每个区间左右端点分别加一个环长度置于最后，预处理倍增数组 \(f[i][j]\) 表示从 \(i\) 开始选取 \(2^j\) 个区间可到达的最右端点，对于每一次询问，从当前区间开始以倍增的方式向右扩展直到回到这一区间即可
P5465 星际穿越
大致为上一题的升级版
大体思路是从后往前倍增，以 \(pre[i][j]\) 表示从 \(i\) 开始往前走 \(2^j\) 步可以到达的最左边的点，以 \(sum[i][j]\) 表示从 \(i\) 走到 \(2^j\) 到 \(i - 1\) 这些点的距离和，询问时，倍增处理
特别地，为方便后续计算，\(pre[i][0]\) 的意义需要进行调整，表示从最后一位到第 \(i\) 位中可以向前扩展的最远距离，而题目给定的 \(l[i]\) 代替了原来 \(pre[i][0]\) 的功能
预处理如下
\[pre[i][j] = pre[pre[i][j - 1]][j - 1] \]\[sum[i][j] = sum[i][j - 1] + sum[pre[i][j - 1]][j - 1] + 2^{j - 1} * (pre[i][j - 1] - pre[i][j]) \]询问的处理如下
点击查看代码
int query(int left, int right){
if(leftmost[right] <= left) return right - left;
int now = leftmost[right];
long long cnt = 1;
long long ans = right - leftmost[right];
for(int j = 19; j >= 0; j--){
if(pre[now][j] >= left){
ans += sum[now][j] + cnt * (now - pre[now][j]);
cnt += (1 << j);
now = pre[now][j];
}
}
ans += cnt * (now - left) + now - left;
return ans;
}
其中注意第一步和最后一步的特殊处理
P1273 有线电视网
树上背包模板题
标签：pre,倍增,训练,int,sum,2023,区间,日志,now From： https://www.cnblogs.com/xj22yangyichen/p/17111201.html