Solution. LG3863 序列
Description
给定长度为 $n$ 的序列，$q$ 次操作，操作有两种：
- 区间加减；
- 查询某个位置上的数在多少个历史版本中 $\ge k$。
$2\le n,q\le 10^5$
Solution
首先我们可以将序列的所有历史版本看作是一个关于下标与时间的平面，那么修改实际上是在平面上做 3-side 矩形加减，而查询又都发生在时间维上，显然用数据结构去维护序列没有什么意义，我们考虑对下标一维做扫描线，转而去维护时间维，这样操作依旧可以看作区间加减，而查询则变成了求区间内 $\ge k$ 的数的个数。
这个问题最暴力的做法是直接分块，对每个块维护块内元素的有序序列。修改时整块打标记，散块暴力修改后用 std::sort 重构；查询时整块 std::lower_bound，散块暴力。总复杂度 $O(q\sqrt q\log q)$。
这个做法感觉就很有优化空间，我们分别来看。
修改的复杂度为 $O(B\log q+q/B)$，瓶颈在散块。事实上，由于我们维护了块内所有元素的有序序列，我们可以线性地将处于修改区间之内和之外的元素分开，同时保证两部分元素分别有序，然后我们对修改区间之内的元素修改后再做一次归并即可，总复杂度 $O(B)$。参考 Main::add_rebuild 的实现。
至此就可以优化到 $O\left(q\sqrt{q\log q}\right)$ 了。
对查询的优化要复杂一些。查询的瓶颈在整块，我们尝试将二分去掉。由于题目不强制在线，我们可以将对每个整块的查询分别离线下来，最后用双指针统计答案。如果要对一个块进行重构，则需要当时就将块内存储的所有询问处理掉。至多会发生 $O(q)$ 次重构，令 $cnt$ 为存储的询问个数，则双指针统计答案的复杂度为 $O(B+cnt)$，另外每次统计答案我们还会对询问进行排序，这部分复杂度为 $O(cnt\log{cnt})$。$\sum cnt =q$，故总复杂度为 $O(qB+q\log q)$。
Update：这里是错误的。每个询问可以被放到 $O(q/B)$ 个块内，$\sum cnt$ 是 $O(q^2/B)$ 级别的，对询问排序的话总复杂度为 $qB+q^2\log q/B$，平衡过后无法除去 $\log$。一种可能的实现方法是将所有块的所有版本都离线下来，空间复杂度上升至 $O(q\sqrt q)$，所有被存储在块内的询问共有 $O(q^2/B)$ 种，如果询问的值域较小则可以对询问做计数排序，总复杂度可以平衡至 $O(q\sqrt q+V)$。但是这种做法应该也没有什么优势，因为空间复杂度过高，$q$ 无法开到较大的级别，该做法很难与 $O(q\sqrt q\log q)$ 拉开差距，更不用说 $O\left(q\sqrt{q\log q}\right)$，这两种做法常数都相当小。不知道有没有更优秀的做法。
Code
namespace Main{
const int N = 100005;
const int B = 320;
int n, q, a[N], cnt, ans[N], len, blocks, bel[N], L[B], R[B];
ll add[B];
vector<pair<int, int>> buc[N];
vector<pair<pair<int, int>, int>> ask[N];
vector<pair<ll, int>> num[B], sav[B];
void Main(){
input(n, q);
for(int i = 1; i <= n; i++) input(a[i]);
q++;
for(int i = 2; i <= q; i++){
int op;
input(op);
if(op == 1){
int l, r, x; input(l, r, x);
buc[l].emplace_back(i, x);
buc[r + 1].emplace_back(i, -x);
}
else{
int p, x; input(p, x);
ask[p].emplace_back(make_pair(i - 1, x - a[p]), cnt++);
}
}
len = sqrt(q);
blocks = (q - 1) / len + 1;
for(int i = 0; i < blocks; i++){
L[i] = i * len + 1;
R[i] = min((i + 1) * len, q);
for(int j = L[i]; j <= R[i]; j++) bel[j] = i, num[i].emplace_back(0, j);
}
// handle all queries and pushdown addition tag
auto pushdown = [&](int id){
sort(sav[id].begin(), sav[id].end(), greater<pair<ll, int>>());
int p = 0;
for(int i = 0; i < num[id].size(); i++){
while(p < sav[id].size() && sav[id][p].first > num[id][i].first){
ans[sav[id][p].second] += i;
p++;
}
}
while(p < sav[id].size()) ans[sav[id][p++].second] += num[id].size();
sav[id].clear();
for(pair<ll, int> &x: num[id]) x.first += add[id];
add[id] = 0;
};
auto add_rebuild = [&](int id, int l, int r, int k){
pushdown(id);
vector<pair<ll, int>> keep, change;
for(pair<ll, int> x: num[id]){
if(x.second >= l && x.second <= r) x.first += k, change.push_back(x);
else keep.push_back(x);
}
merge(keep.begin(), keep.end(), change.begin(), change.end(), num[id].begin(), greater<pair<ll, int>>());
};
auto modify = [&](int l, int k){
if(bel[l] == bel[q]) add_rebuild(bel[q], l, q, k);
else{
for(int i = bel[l] + 1; i <= bel[q]; i++) add[i] += k;
add_rebuild(bel[l], l, R[bel[l]], k);
}
};
auto query = [&](int r, int k, int ans_id){
for(int i = bel[1]; i < bel[r]; i++) sav[i].emplace_back(k - add[i], ans_id);
for(pair<ll, int> x: num[bel[r]]) if(x.second <= r) ans[ans_id] += x.first + add[bel[r]] >= k;
};
for(int i = 1; i <= n; i++){
for(pair<int, int> x: buc[i]) modify(x.first, x.second);
for(auto x: ask[i]) query(x.first.first, x.first.second, x.second);
}
for(int i = 0; i < blocks; i++) pushdown(i);
for(int i = 0; i < cnt; i++) write(ans[i]), puts("");
return;
}
} // namespace Main本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
