Solution
考虑维护任意两个相邻码头之间的费用总和，设 \(val_i\) 表示第 \(i\) 个码头与第 \(i + 1\) 个码头之间所有船到达下一个码头的费用之和。
此时计算 \(val\) 数组在初始时，与修改时都能够做到 \(O(1)\)。
用 set 来维护码头的位置，方便在新建码头时快速找到前驱和后继的位置。
每次新建一个码头，\(val\) 要改变的只有前驱和当前的码头。
对于查询造作：我们不妨先把答案记录成 \([l, r]\) 中码头的 \(val\) 值总和，发现有两段是需要我们额外去处理的。
在左边，我们是没有处理从 \(l\) 到了后第一个码头的价值，把答案加上这一部分。
而在右边，我们多算了从 \(r+1\) 开始到 \(r\) 右边第一个码头价值，于是答案减去这一部分。
这样查询和修改我们都做到了 \(\log n\)，瓶颈在于区间求和与 set。
总复杂度 \(O((n + q) \log n)\)。
写法较丑。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 3e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 998244353;
int n, m, q;
set<int> s;
int val[N], w[N], g[N];
struct BIT {
int N;
vector<LL> c;
#define lbt(x) x & -x
BIT(int n) {
N = n;
c.resize(n + 1);
}
void modify(int x, LL v) {
for(; x <= N; x += lbt(x)) c[x] += v;
}
LL query(int x) {
LL res = 0;
for(; x; x -= lbt(x)) res += c[x];
return res;
}
LL query(int l, int r) {
return query(r) - query(l - 1);
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> q;
BIT bit(n);
for(int i = 1; i <= m; i ++) {
int x;
cin >> x;
g[i] = x;
s.insert(x);
}
for(int i = 1; i <= m; i ++) {
int v;
cin >> v;
w[g[i]] = v;
}
for(auto it = s.begin(); it != s.end(); it ++) {
auto it2 = it;
it2 ++;
int p = *it, nxt = *it2;
if(p == n) continue;
int d = nxt - p - 1;
val[p] = d * (d + 1ll) / 2ll * w[p];
bit.modify(p, val[p]);
}
while(q --) {
int op, x, y;
cin >> op >> x >> y;
if(op == 1) {
w[x] = y;
auto it = s.lower_bound(x);
int nxt = *it;
it --;
int pre = *it;
bit.modify(pre, -val[pre]);
int d = x - pre - 1;
val[pre] = d * (d + 1ll) / 2ll * w[pre];
bit.modify(pre, val[pre]);
d = nxt - x - 1;
val[x] = d * (d + 1ll) / 2ll * w[x];
bit.modify(x, val[x]);
s.insert(x);
}
else {
int ans = bit.query(x, y);
int l = *--s.upper_bound(x), ll = *s.lower_bound(x), r = *s.upper_bound(y), rr = *--s.upper_bound(y);
int d = ll - x;
ans += d * (d + 1ll) / 2ll * w[l];
if(y != r && y != n) {
d = r - y - 1;
ans -= d * (d + 1ll) / 2ll * w[rr];
}
cout << ans << '\n';
}
}
return 0;
}