## 王国边缘
#模拟 #倍增 #二分
首先如果坐标都是在模 $n$ 意义下的话，这 $n$ 个位置的下一步走法是固定的。这个可以 $\mathcal O(n)$ 或 $\mathcal O(n\log_2 n)$ 处理出来。（注意对 $m\le n$ 和 $m>n$ 的特别处理。我为了方便搞了 $2n$ 长的，但是当 $m>n$ 时循环了需要特殊处理）
接下来我就开始发癫了。我想得是没错的，从一个地方走了若干步之后一定会到环上并且不会出来，所以维护环就行了。但是事情并没有这么简单。
因为我们不止需要知道模 $n$ 意义下的位置，还需要知道实际的位置。这个实际位置有很多可能，我们不知道，所以需要记录走到下一步所进行的位移。于是我们就需要维护环上的位移前缀和、环周围的链的前缀和……非常复杂，而且讨论很多。
最后发现我是大煞笔。像这种走若干步的问题，直接倍增就行了。$\mathcal O(n\log_2 V)$ 预处理出倍增数组，然后每次走 $2^k$ 步，最后拼出询问的 $K$ 即可。时间复杂度 $\mathcal O((n+q)\log_2 V)$。
需要注意取模部分，因为输入的就有 $10^{18}$ 了。
```cpp
const LL kMaxN = 2e5 + 5, kLog = 63, kMod = 1e9 + 7;
// 走 2^k 步能到达的 (mod n) 的地方和 Δx
LL nxt[kLog][kMaxN], val[kLog][kMaxN], n, m, q;
vector<LL> v;
string a;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q >> a;
a = " " + a + a;
for (LL i = 1; i <= 2 * n; i++) {
if (a[i] == '1') {
v.push_back(i);
}
}
LL zrr = m / n, wyy = m % n;
for (LL i = 1; i <= n; i++) {
if (v.empty()) {
nxt[0][i] = i % n + 1;
val[0][i] = 1;
continue;
}
if (m <= n) {
auto p = upper_bound(v.begin(), v.end(), i + m);
if (p == v.begin()) {
nxt[0][i] = i % n + 1;
val[0][i] = 1;
continue;
}
LL x = *prev(p);
if (x > i) {
nxt[0][i] = (x - 1) % n + 1;
val[0][i] = x - i;
} else {
nxt[0][i] = i % n + 1;
val[0][i] = 1;
}
} else {
auto p = upper_bound(v.begin(), v.end(), i + wyy);
// 要么在 [1, i+wyy] 当中，如果没有必然 i+wyy<n 且在 (i+wyy,n] 中
if (p == v.begin()) {
p = upper_bound(v.begin(), v.end(), n);
LL x = *prev(p);
nxt[0][i] = x;
val[0][i] = (zrr - 1) * n + x - i;
continue;
}
LL x = *prev(p);
nxt[0][i] = (x - 1) % n + 1;
val[0][i] = zrr * n + x - i;
}
val[0][i] %= kMod;
}
for (LL i = 1; i < kLog; i++) {
for (LL j = 1; j <= n; j++) {
nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
val[i][j] = (val[i - 1][j] + val[i - 1][nxt[i - 1][j]]) % kMod;
}
}
for (LL x, k; q; q--) {
cin >> x >> k;
LL ans = x % kMod;
x = (x - 1) % n + 1;
for (LL i = 0; i < kLog; i++) {
if (k >> i & 1) {
ans = (ans + val[i][x]) % kMod;
x = nxt[i][x];
}
}
cout << ans << '\n';
}
return 0;
}
```
## 买东西题
#贪心 #优先队列
我最开始写了一个线段树的做法。
具体来说，我做个贪心，把折扣优惠 $v_i$ 更多的排在前面，然后用线段树维护下标 $a$ 所对应的 $a-b$ 的区间最小值。按照 $v_i$ 从大到小的顺序枚举每张优惠券，在所有 $a$ 大于等于 $w_i$ 的商品中取出 $a-b$ 最小的买掉（这样实际收益更多），然后把它从线段树当中删除。其它的用 $b_i$ 买。
这个算法不出意料地在大样例上面 TLE 了。$v_i$ 越大的放前面不一定好，因为 $w_i$ 的限制，如果前一个限制更小，然后把 $a$ 小的夺走了；后面一个 $v$ 小一些，但是它限制大，被前面的夺走了。这样子本来这两张优惠券全部可以用上的，结果最后只能用上一张，答案就不对。
既然我们没办法一次就找出哪张优惠券对应哪个商品，所以回归老本行：反悔贪心。
首先，对于一个新物品，它有三种选择策略：
1. 不使用优惠券用折扣价买；
2. 把之前的一个物品的优惠券抢过来用，再给被抢的补一张（相当于新用一个然后交换）；
3. 把之前的一个物品的优惠券抢过来用，但不补偿。
第二个操作最长，但是我们实际上只需要按照 $a$ 从小到大的顺序排序处理就不会用到第二种情况了。因为在交换前后都是合法的情况下，交换前后的收益是一样大的。
所以我们只需要考虑第三种情况就行了。反悔贪心的本质就是把第三种情况变到第一种情况去。由于我们是按照 $a$ 排序的，所以 $i$ 抢 $j$ $(j<i)$ 是一定符合条件的。
好的。假设 $i$ 抢了 $j$ $(i>j)$，抢的优惠券优惠力度为 $v$（由于 $a$ 递增所以抢过来合法）。那么抢之前的收益：
$
a_i-v+b_j
$
抢之后的收益
$
b_i+a_j-v
$
我们要把抢的过程看作用了一个新的优惠券，那么这个优惠券具体是多少的优惠力度呢？设为 $x$，有
$
(a_i-v)+(a_j-x)=b_i+a_j-v
$
所以 $x=a_i-b_i$。
代码就很简单了。由于 $a$ 单调递增，我们给优惠券的限制 $w$ 也排个序，那么可用的优惠券在序列中就是一个单调边长的前缀。优惠券用优先队列（大根堆）维护（因为维护的都是可以作用的，所以只需要优惠力度大的放前面即可）。
时间复杂度 $\mathcal O(n\log_2 n)$ $(\mathcal O(n)=\mathcal O(m))$。
```cpp
const LL kMaxN = 1e6 + 5;
LL n, m, ans;
pair<LL, LL> a[kMaxN], b[kMaxN];
priority_queue<LL> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a + 1, a + n + 1);
for (LL i = 1; i <= m; i++) {
cin >> b[i].first >> b[i].second;
}
sort(b + 1, b + m + 1);
for (LL i = 1, j = 1; i <= n; i++) {
for (; j <= m && b[j].first <= a[i].first; j++) {
q.push(b[j].second);
}
if (q.size() && q.top() > a[i].first - a[i].second) {
ans += a[i].first - q.top();
q.pop();
q.push(a[i].first - a[i].second);
} else {
ans += a[i].second;
}
}
cout << ans << '\n';
return 0;
}
```
## IMAWANOKIWA (Construction ver.)
不会写，暴力都没打。$0$ 分。
## 魔法少女们
不会写，暴力都没打。$0$ 分。