不知道为什么好像大家在这题上花了挺久的。
发现对于一对相邻的港口 \((x_i, x_{i + 1})\)，\(x \in (x_i, x_{i + 1})\) 的花费是 \(y_i (x_{i + 1} - x)\)。拆开得 \(y_i x_{i + 1} - y_i x\)。
考虑用 set 维护所有港口，这样可以知道一个港口左边和右边的港口的坐标和价值。那么前一项 \(y_i x_{i + 1}\) 可以线段树区间覆盖，后一项 \(-y_i x\) 也可以线段树区间覆盖处理，相当于让一个代表 \([l, r]\) 区间的线段树结点的和加上 \(- y_i \frac{(l + r)(r - l + 1)}{2}\)。这个标记是可以下传的。
总时间复杂度为 \(O((m + q) \log n)\)。
code
// Problem: B. Space Harbour
// Contest: Codeforces - Codeforces Round 921 (Div. 1)
// URL: https://codeforces.com/contest/1924/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
ll n, m, q, a[maxn], b[maxn];
inline ll calc(ll l, ll r) {
return (l + r) * (r - l + 1) / 2;
}
struct {
ll a[maxn << 2], tag[maxn << 2];
inline void pushup(int x) {
a[x] = a[x << 1] + a[x << 1 | 1];
}
inline void init() {
mems(tag, -1);
}
inline void pushdown(int x, int l, int r) {
if (tag[x] == -1) {
return;
}
int mid = (l + r) >> 1;
a[x << 1] = tag[x] * (mid - l + 1);
a[x << 1 | 1] = tag[x] * (r - mid);
tag[x << 1] = tag[x << 1 | 1] = tag[x];
tag[x] = -1;
}
void update(int rt, int l, int r, int ql, int qr, ll x) {
if (ql > qr) {
return;
}
if (ql <= l && r <= qr) {
a[rt] = x * (r - l + 1);
tag[rt] = x;
return;
}
pushdown(rt, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
ll query(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return a[rt];
}
pushdown(rt, l, r);
int mid = (l + r) >> 1;
ll res = 0;
if (ql <= mid) {
res += query(rt << 1, l, mid, ql, qr);
}
if (qr > mid) {
res += query(rt << 1 | 1, mid + 1, r, ql, qr);
}
return res;
}
} t1;
struct {
ll a[maxn << 2], tag[maxn << 2];
inline void pushup(int x) {
a[x] = a[x << 1] + a[x << 1 | 1];
}
inline void init() {
mems(tag, -1);
}
inline void pushdown(int x, int l, int r) {
if (tag[x] == -1) {
return;
}
int mid = (l + r) >> 1;
a[x << 1] = tag[x] * calc(l, mid);
a[x << 1 | 1] = tag[x] * calc(mid + 1, r);
tag[x << 1] = tag[x << 1 | 1] = tag[x];
tag[x] = -1;
}
void update(int rt, int l, int r, int ql, int qr, ll x) {
if (ql > qr) {
return;
}
if (ql <= l && r <= qr) {
a[rt] = x * calc(l, r);
tag[rt] = x;
return;
}
pushdown(rt, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
ll query(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return a[rt];
}
pushdown(rt, l, r);
int mid = (l + r) >> 1;
ll res = 0;
if (ql <= mid) {
res += query(rt << 1, l, mid, ql, qr);
}
if (qr > mid) {
res += query(rt << 1 | 1, mid + 1, r, ql, qr);
}
return res;
}
} t2;
set<pii> S;
inline void upd(ll x, ll y, ll z) {
t1.update(1, 1, n, x + 1, y - 1, z * y);
t2.update(1, 1, n, x + 1, y - 1, -z);
}
void solve() {
t1.init();
t2.init();
scanf("%lld%lld%lld", &n, &m, &q);
for (int i = 1; i <= m; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
S.emplace(a[i], b[i]);
}
for (auto it = S.begin(); next(it) != S.end(); ++it) {
auto jt = next(it);
upd(it->fst, jt->fst, it->scd);
}
while (q--) {
ll op, x, y;
scanf("%lld%lld%lld", &op, &x, &y);
if (op == 1) {
S.emplace(x, y);
t1.update(1, 1, n, x, x, 0);
t2.update(1, 1, n, x, x, 0);
auto it = S.find(mkp(x, y));
auto p = prev(it), q = next(it);
upd(p->fst, it->fst, p->scd);
upd(it->fst, q->fst, it->scd);
} else {
printf("%lld\n", t1.query(1, 1, n, x, y) + t2.query(1, 1, n, x, y));
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}