https://uoj.ac/submission/621863

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << var << "; "
#define int long long
int n, m, q, a[200010];
struct Node {
	int id, l, r, l_, r_, x, y, f;
} p[200010], tmp[200010];
bool cmpX(Node a, Node b) {
	return a.x < b.x;
}
bool cmpY(Node a, Node b) {
	return a.y < b.y;
}
struct Seg {
	int tag[800010];
	void upd(int u, int l, int r, int L, int R, int x) {
		tag[u] = max(tag[u], x);
		if (L <= l && R >= r) return;
		else if (!(r < L || R < l)) {
			int mid = (l + r) >> 1;
			upd(u << 1, l, mid, L, R, x); upd(u << 1 | 1, mid + 1, r, L, R, x);
		}
	}
	void set(int u, int l, int r, int L, int R, int x) {
		tag[u] = x;
		if (L <= l && R >= r) return;
		else if (!(r < L || R < l)) {
			int mid = (l + r) >> 1;
			set(u << 1, l, mid, L, R, x); set(u << 1 | 1, mid + 1, r, L, R, x);
		}
	}
	int query(int u, int l, int r, int L, int R) {
		if (L <= l && R >= r) return tag[u];
		else if (!(r < L || R < l)) {
			int mid = (l + r) >> 1;
			return max(tag[u], max(query(u << 1, l, mid, L, R), query(u << 1 | 1, mid + 1, r, L, R)));
		} return -1e18;
	}
} seg;
void sol(int l, int r) {
	if (l == r) {
		p[l].f = max(p[l].f, p[l].y); return;
	}
	int mid = (l + r) >> 1;
	sol(mid + 1, r);
	memcpy(tmp + l, p + l, sizeof(p[0]) * (r - l + 6));
	sort(tmp + l, tmp + mid + 1, cmpY);
	sort(tmp + mid + 1, tmp + r + 1, cmpX);
	int now = mid;
	for (int i = l; i <= mid; i++) {
		while (now < r && tmp[now + 1].x <= tmp[i].y) {
			now++;
			seg.upd(1, 1, n, tmp[now].l, tmp[now].r, tmp[now].f);
		}
		p[tmp[i].id].f = max(p[tmp[i].id].f, seg.query(1, 1, n, tmp[i].l_, tmp[i].r_));
	}
//	cerr<<'\n';
	for (int i = mid + 1; i <= r; i++) seg.set(1, 1, n, tmp[i].l, tmp[i].r, -1e18);
	sol(l, mid);
}
struct Upd {
	int id, p, x, ans;
} upd[1000010];
bool cmpUX(Upd a, Upd b) {
	return a.x < b.x;
}
bool cmpID(Upd a, Upd b) {
	return a.id < b.id;
}
int lst[500010];
multiset<int> st;
signed main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) {
		p[i].id = i; cin >> p[i].l >> p[i].r >> p[i].x >> p[i].l_ >> p[i].r_ >> p[i].y; p[i].f = -1e18;
	}
	sol(1, m);
//	for (int i = 1; i <= m; i++) {
//		deb(i);
////		deb(p[i].f) << "\n";
//	}
	for (int i = 1; i <= q; i++) {
		cin >> upd[i].p >> upd[i].x; upd[i].id = i; upd[i].ans = -1e18;
	}
	for (int i = 1; i <= n; i++) {
		q++;
		upd[q].p = i; upd[q].id = q; upd[q].x = a[i]; upd[q].ans = -1e18;
	}
	sort(upd + 1, upd + q + 1, cmpUX);
	sort(p + 1, p + m + 1, cmpX);
	int now = 0;
	for (int i = 1; i <= q; i++) {
		while (now < m && p[now + 1].x <= upd[i].x) {
			now++;
			seg.upd(1, 1, n, p[now].l, p[now].r, p[now].f);
		}
		upd[i].ans = seg.query(1, 1, n, upd[i].p, upd[i].p);
	}
	sort(upd + 1, upd + q + 1, cmpID);
	for (int i = 1; i <= n; i++) {
		lst[i] = q - n + 1; st.insert(upd[lst[i]].ans); st.insert(a[i]);
//		deb(upd[lst[i]].ans);
	}
//		multiset<int>::iterator it = st.end(); it--;
//		cout << *it << "\n"; 
	for (int i = 1; i <= q - n; i++) {
		int p = upd[i].p;
		int ans = upd[i].ans;
//		deb(ans);
		st.erase(st.lower_bound(upd[lst[p]].ans)); st.insert(ans);
		st.erase(st.lower_bound(a[p]));
		a[p] = upd[i].x;
		st.insert(a[p]);
		multiset<int>::iterator it = st.end(); it--;
		cout << *it << "\n"; lst[p] = i;
	}
}