LOJ 6346 线段树：关于时间 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，另有一个存储三元组的列表 $L$.
有 $m$ 个操作分两种：

• $\mathrm{add}(l,r,k)$：将 $(l,r,k)$ 插入到 $L$ 末尾.
• $\mathrm{query}(l,r)$：求 $\sum _{i=l}^r{a}_i$.

每次操作后，对于 $L$ 中每一项 $(l,r,k)$，将 $a_l\sim a_r$ 加上 $k$.

Limitations

$1\le n,m\le 10^5$
$1\le l\le r\le n$
$1\le a_i\le 10^4$
$|k|\le 10^4$
$0.2\text{s},256\text{MB}$

Solution

直接硬做是无法维护的，考虑每次修改后立刻计算贡献.
下设当前为第 $i$ 次操作.

• 如果是修改，则直到最后一次操作前，$a_l\sim a_r$ 会被加 $(m-i)$ 次 $k$.
• 但如果是询问，那么没有执行的 $(m-i)$ 次操作的贡献要减掉.

接下来很显然了，我们维护序列 $\text{add},\text{del}$，初始时 $\text{add}=a$，$\text{del}$ 为全 $0$.

• 对于修改，我们给 ${\text{add}}_l\sim {\text{add}}_r$ 加上 $k\times (m-i)$，给 ${\text{del}}_l\sim {\text{del}}_r$ 加上 $k$.
• 对于查询，答案就是 $(\sum _{j=l}^{r}ad{d}_j)-(m-i)\times (\sum _{j=l}^{r}de{l}_j)$.

$\text{add},\text{del}$ 可用线段树维护，但是时限很紧，需要用 BIT 维护，实现见代码.

Code

$1.6\text{KB},0.16\text{s},3.6\text{MB}\text{(in total, C++20 with O3)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}inline int lowbit(int x) { return x & (-x); }struct bit {int n;vector<i64> c1, c2;inline bit() {}inline bit(int _n): n(_n) {c1.resize(n);c2.resize(n);}inline void add(int x, i64 k) {for (int i = x + 1; i <= n; i += lowbit(i)) {c1[i - 1] += k;c2[i - 1] += k * x;}}inline i64 ask(int x) {i64 res = 0;for (int i = x + 1; i; i -= lowbit(i)) {res += c1[i - 1] * (x + 1) - c2[i - 1];}return res;}inline void update(int l, int r, i64 v) {add(l, v);add(r + 1, -v);}inline i64 sum(int l, int r) {return ask(r) - ask(l - 1);}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n; scanf("%d", &n);bit f1(n), f2(n);for (int i = 0, x; i < n; i++) f1.update(i, i, (scanf("%d", &x), x));int m; scanf("%d", &m);for (int i = 0, op, l, r, x; i < m; i++) {scanf("%d %d %d", &op, &l, &r), l--, r--;if (op == 1) {scanf("%d", &x);f1.update(l, r, 1LL * x * (m - i - 1));f2.update(l, r, x);}else {printf("%lld\n", f1.sum(l, r) - f2.sum(l, r) * (m - i - 1));}}return 0;
}