https://codeforces.com/contest/1924/submission/330766058 （提交记录

#include <bits/stdc++.h>

using namespace std;

const long long N = 3e5 + 5, INF = 1e18;

struct S {
	__int128 sum;
	long long tag1 = -INF, tag2 = -INF;
} tr[N * 4];

long long n, m, q, a[N], b[N], vis[N];

set<long long> s;

__int128 Sum(long long a, long long k, long long o) {
	__int128 cnt = (__int128)a + (__int128)((__int128)k * (__int128)(o - 1));
	return (__int128)(cnt + a) * (__int128)o / (__int128)2;
}

void pushup(long long x) {
	tr[x].sum = tr[2 * x].sum + tr[2 * x + 1].sum;
}

void pushdown(long long x, long long l, long long mid, long long r) {
	if (tr[x].tag1 == -INF) {
		return;
	}
	tr[2 * x].tag2 = tr[2 * x + 1].tag2 = tr[x].tag2;
	tr[2 * x].tag1 = tr[x].tag1, tr[2 * x + 1].tag1 = tr[x].tag1 + ((mid + 1 - l) * tr[x].tag2);
	tr[2 * x].sum = Sum(tr[2 * x].tag1, tr[2 * x].tag2, mid - l + 1);
	tr[2 * x + 1].sum = Sum(tr[2 * x + 1].tag1, tr[2 * x + 1].tag2, r - mid);
	tr[x].tag1 = tr[x].tag2 = -INF;
}

void D(long long x, long long l, long long r, long long sx, long long ex, long long xo, long long k) {
	if (sx > ex) {
		return;
	}
	if (l == sx && r == ex) {
		tr[x].sum = Sum(xo, k, r - l + 1);
		tr[x].tag1 = xo, tr[x].tag2 = k;
		return;
	}
	long long mid = (l + r) / 2, tmp = 0;
	pushdown(x, l, mid, r);
	if (sx <= mid) {
		D(2 * x, l, mid, sx, min(mid, ex), xo, k);
		tmp = min(mid, ex) - sx + 1;
	}
	if (mid + 1 <= ex) {
		D(2 * x + 1, mid + 1, r, max(sx, mid + 1), ex, xo + (tmp * k), k);
	}
	pushup(x);
}

void F(long long x, long long l, long long r, long long o) {
	if (l == r) {
		tr[x].sum = 0;
		return;
	}
	long long mid = (l + r) / 2;
	pushdown(x, l, mid, r);
	if (o <= mid) {
		F(2 * x, l, mid, o);
	} else {
		F(2 * x + 1, mid + 1, r, o);
	}
	pushup(x);
}

void insert(long long x, long long o) {
	auto cnt = --s.lower_bound(x);
	auto tmp = s.lower_bound(x);
	long long l = *cnt, r = *tmp;
	D(1, 1, n, l + 1, x - 1, vis[l] * (x - l - 1), -vis[l]);
	D(1, 1, n, x + 1, r - 1, o * (r - x - 1), -o);
	F(1, 1, n, x);
	s.insert(x);
	vis[x] = o;
//	cout << l << " " << x << " " << r << "\n";
}

__int128 E(long long x, long long l, long long r, long long sx, long long ex) {
	if (l == sx && r == ex) {
//		cout << l << " " << r << " " << tr[x].sum << "\n";
		return tr[x].sum;
	}
	__int128 ans = 0;
	long long mid = (l + r) / 2;
	pushdown(x, l, mid, r);
	if (sx <= mid) {
		ans += E(2 * x, l, mid, sx, min(mid, ex));
	}
	if (mid + 1 <= ex) {
		ans += E(2 * x + 1, mid + 1, r, max(sx, mid + 1), ex);
	}
	return ans;
}

int main() {
	cin >> n >> m >> q;
	s.insert(1), s.insert(n);
	for (long long i = 1; i <= m; i++) {
		cin >> a[i];
	}
	for (long long i = 1; i <= m; i++) {
		cin >> b[i];
		vis[a[i]] = b[i];
	}
	D(1, 1, n, 2, n - 1, vis[1] * (n - 2), -vis[1]);
	for (long long i = 2; i < m; i++) {
		insert(a[i], b[i]);
	}
	for (long long op, x, v, l, r; q--;) {
		cin >> op;
		if (op == 1) {
			cin >> x >> v;
			insert(x, v);	
		} else {
			cin >> l >> r;
			__int128 ans = E(1, 1, n, l, r);
			long long tmp = (long long)ans;
			cout << tmp << "\n";
		}
	}
	return 0;
}