A. ABC427G Takahashi's Expectation 2 (6.5)
非常厉害的题目。
首先肯定考虑维护一个答案函数，初始为 \(y=x\)，那么每次操作相当于用一条横线砍它，上面 -b 下面 +a。
考场上想了一个正确性其实不是很显然，感觉也不一定对的东西：首先肯定时时刻刻我的斜线条数是 加入次数+1 的。因为我对断点上做一次操作，会让中间一个断点合到一起，并在两边多加一个断点。那么考虑找一下这个断点的性质，首先断点初的差分一定是 a+b，然后我认为值域有交的斜线一定定义域连续。考虑一个这样的连续段，每次切过值域重合处，会相当于把我的断点向左平移一段，然后最后加一个断点。平移量是可以简单得出的。然后维护端点位置，相当于区间减和单点插入...或许可以平衡树 /xk
正解是比较有道理的。
考虑我暴力维护这个东西。首先可以简化一下题意，默认每次一定会减掉一个 \(B\)，如果我真能加就加上 \(A+B\)，最后求答案的时候把答案减去 \(nB\) 即可。那么对应到它给的礼物，第 \(i\) 个礼物的价值要提高 \((i-1)B\)，这样才能正确比较。这样我的过程还拥有了当前心情值不减的优美性质。不妨设 \(d=A+B\)。
那么有了这个性质，我们会很想要一个递减的礼物序列。如果礼物序列递减，那么上一个礼物不能买，下一个礼物将也不能买，具有着状态单调性。这样可以二分，找到一个最后一个能买的位置，然后前面全都能买，即得出答案。但是对于相邻的两个礼物 \(x<y\) 怎么办？
讨论一下这样的对产生的贡献：一开始 \(\leq \min(x,y-d)\) 的数会被加两次 \(d\)，\(\min(x,y-d)<w\leq y\) 的数会被加一次，其他的根本不加。因此这个操作 \((x,y)\) 等价于 \((\min(x,y-d),y)\)。此时的两次操作是互不干扰的！因此可以调换顺序，变为 \((y, \min(x+d,y))\)。此时右边是比左边小的，做到了改变大小关系。
那么我现在暴力去做这个操作，去维护一个递减的、与原序列等价的序列 \(c\)，每次插入 \(x\) 相当于找到第一个 \(<x\) 的 \(c_i\)，将其左边插进 \(x\)，再找到最后一个 \(\geq x-d\) 的 \(c_j\)，然后 Assign([i, j], x), Add([j + 1, end], a + b)。此时可以大力平衡树直接 \(mathcal{O}((n\log n)\) 爆掉，但是我不太会平衡树所以没写。如果暴力去做这个过程将会是单次操作 \(\mathcal{O}(n)\) 的。
但是这个我们其实可以做到快速合并两个有序序列！有左右相邻的两个已经变得有序的区间，可以归并地做这个操作：考虑把右侧序列一个一个插入到左侧，而且右侧序列它也是有序的，我做操作是多出来一段 \(r_i\)，所以到 \(r_{i+1}\) 的时候它的 \(i\) 也不会到这个里面，所以可以双指针维护，简单合并即可。
于是可以二进制分组，查询暴力枚举块然后二分即可，查询为瓶颈，复杂度 \(\mathcal{O}(n\log^2 n)\)。
Code
#pragma GCC optimize("Ofast,unroll-loops")
// STOOOOOOOOOOOOOOOOOOOOOOOOO hzt CCCCCCCCCCCCCCCCCCCCCCCORZ
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>using namespace std;
using LL = long long;
using Block = vector<LL>;
using PII = pair<int, int>;
constexpr int kN = 2e5 + 1;int n, q;
LL A, B, d;inline void operator+=(Block &a, Block &b) {int i = 0, j = 0, cnt = 0;Block ret;for (; j < b.size(); j++) {for (; i < a.size() && a[i] + cnt * d >= b[j]; i++)ret.push_back(a[i] + cnt * d);cnt++;for (; i < a.size() && a[i] + cnt * d >= b[j]; i++)ret.push_back(b[j]);ret.push_back(b[j]);}for (; i < a.size(); ret.push_back(a[i++] + cnt * d));a.swap(ret), ret.clear();
}
vector<Block> b;
inline void Insert(LL w) {b.emplace_back(1, w);for (int sz = b.size() - 1; sz > 0 && b[sz].size() == b[sz - 1].size();) {b[sz - 1] += b[sz];b[sz].clear(), b[sz].shrink_to_fit();b.pop_back(), sz--;}
}
int main() {
#ifndef ONLINE_JUDGEfreopen("input.in", "r", stdin);freopen("output.out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> n >> A >> B, d = A + B;for (int i = 1, p; i <= n; i++)cin >> p, Insert(p + (i - 1) * B);cin >> q;for (LL op, x; q--;) {cin >> op >> x;if (op == 2) {for (auto &vb : b) {int l = 0, r = vb.size() - 1, ans = 0;for (int mid; l <= r;) {mid = (l + r) / 2;if (vb[mid] >= x + mid * d)l = mid + 1, ans = mid + 1;elser = mid - 1;}x += ans * d;}cout << x - 1ll * n * B << '\n';} elseInsert(x + n * B), n++;}return 0;
}