优美的数据结构题。
这题先修改再查询，基本明确了要使用扫描线做这道题。
我们将第一维视为时间，那么我们对于一个操作，将其变为时刻 \(l_1\) 时，在区间 \([l_2,r_2]\) 加上 \(x\)，时刻 \(r_1+1\) 时，在区间 \([l_2,r_2]\) 减去 \(x\)。
然后对于一个查询，相当于是要求区间 \([l_2,r_2]\) 在时刻 \([l_1,r_1]\) 中的历史版本和。直接维护非常的不优秀啊，考虑优化这个东西。
继续将问题简化，如果询问只有一段前缀，也就是询问都为以 \((1,r_1,l2,r2)\) 形式出现的该怎么做？
我们可以求历史版本和，将操作和询问挂在时刻上，边修改边查询即可。
而对于一段前缀，我们也可以用类似的办法，先完成所有时刻的操作，再开始求历史版本和，从时刻 \(n\) 到 \(1\)，边修改边查询，这样就可以完成一段后缀。
那么接下来启发我们对于一个查询将其劈成两半，分别查询。具体我们可以考虑取若干个中点，解决若干次询问的查询。
我们可以进行线段树分治，将区间挂在最小的能包含自己的线段树上，其实就是 \(l\le l_1\le mid< r_1\le r\)，\(l,r,mid\) 分别为线段树节点的左节点，右节点，和中点，对于每个节点，每次先将 \([l,mid]\) 时刻的操作先完成，再进入线段树右节点，然后再处理挂在该节点上的询问的后半段，开始查询历史版本和，处理完这些询问后我们减去 \([mid+1,r]\) 的贡献，再处理询问的前半段，边查询边回撤 \([l,mid]\) 的操作，最后再进入左节点。这样，就能优美地处理完了所有询问。
最后讲讲线段树维护细节吧。开始查询历史版本和，其本质是让所有节点的维护历史版本的节点都等于当前的值，我们可以在要查询时打一个标记，但是标记是不能乱打的！如果我们像普通标记下传那样，就会存在一个区间加的标记与开始查询的标记产生冲突的问题，不信自己去分情况手玩一下，本人因为这个调了很久！这个时候我们可以在每次开始查询标记下传时先把区间加的标记下传就没问题了。
哦对了，注意是历史版本和，所以对于每个时刻一定要先将加的值小的操作先处理！
时间复杂度 \(\mathcal{O}(n\log^2n)\)。
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
#define id(x, y) n * (x - 1) + y
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 5e5 + 5, M = (1ll << 31) - 1, P = 998244353, inf = 1e16;
constexpr double PI = acos (-1.0);
inline int rd () {
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
if (ch == '-') f = -1;
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar ();
}
return x * f;
}
int qpow (int x, int y) {
int ret = 1;
for (; y; y >>= 1, x = x * x % P) if (y & 1) ret = ret * x % P;
return ret;
}
int mx[N], his[N];
bool sta[N];
int tag[N][3];
bool cov[N];
void add (int p, int k1, int k2) {
his[p] = max (his[p], mx[p] + k2);
mx[p] += k1;
tag[p][1] = max (tag[p][1], tag[p][0] + k2);
tag[p][0] += k1;
}
void cover (int p) {
add (ls, tag[p][0], tag[p][1]);
add (rs, tag[p][0], tag[p][1]);
tag[p][0] = tag[p][1] = 0;
tag[p][2] = 1;
his[p] = mx[p], tag[p][1] = tag[p][0];
}
void psd (int p) {
if (tag[p][2]) {
cover (ls), cover (rs);
tag[p][2] = 0;
}
add (ls, tag[p][0], tag[p][1]);
add (rs, tag[p][0], tag[p][1]);
tag[p][0] = tag[p][1] = 0;
}
void upd (int p, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) {
add (p, k, k);
return ;
} int mid = l + r >> 1; psd (p);
if (L <= mid) upd (ls, l, mid, L, R, k);
if (R > mid) upd (rs, mid + 1, r, L, R, k);
mx[p] = max (mx[ls], mx[rs]);
his[p] = max (his[ls], his[rs]);
}
int qry (int p, int l, int r, int L, int R) {
if (L <= l && r <= R) return his[p];
int ret = 0, mid = l + r >> 1;
psd (p);
if (L <= mid) ret = max (ret, qry (ls, l, mid, L, R));
if (R > mid) ret = max (ret, qry (rs, mid + 1, r, L, R));
return ret;
}
int n, m, q;
class oper {
public:
int l, r, k;
friend bool operator < (const oper &a, const oper &b) {
return a.k < b.k;
}
} ;
vector <oper> vec[50005], vvc[50005];
int ans[N];
class ask {
public:
int l1, r1, l2, r2, i;
} ;
bool cmp1 (ask o, ask p) {
return o.r1 < p.r1;
}
bool cmp2 (ask o, ask p) {
return o.l1 > p.l1;
}
vector <ask> vc[N];
void insert (int p, int l, int r, ask x) {
if (l == r) {
vc[p].eb (x);
return ;
}
int mid = l + r >> 1;
if (x.r1 <= mid) insert (ls, l, mid, x);
else if (x.l1 > mid) insert (rs, mid + 1, r, x);
else vc[p].eb (x);
}
void solve (int p, int l, int r) {
if (l == r) {
if (! vc[p].size ()) return ;
for (auto it : vec[l]) upd (1, 1, n, it.l, it.r, it.k);
cover (1);
for (auto it : vc[p]) {
ans[it.i] = qry (1, 1, n, it.l2, it.r2);
}
for (auto it : vec[l]) upd (1, 1, n, it.l, it.r, - it.k);
return ;
}
int mid = l + r >> 1;
rep (i, l, mid) {
for (auto it : vec[i]) {
int L = it.l, R = it.r, k = it.k;
upd (1, 1, n, L, R, k);
}
}
solve (rs, mid + 1, r);
for (auto it : vc[p]) {
vvc[it.r1].eb ((oper) {it.l2, it.r2, it.i});
}
rep (i, mid + 1, r) {
for (auto it : vec[i]) {
int L = it.l, R = it.r, k = it.k;
upd (1, 1, n, L, R, k);
}
if (i == mid + 1) cover (1);
for (auto it : vvc[i]) {
ans[it.k] = max (ans[it.k], qry (1, 1, n, it.l, it.r));
} vvc[i].clear ();
}
rep (i, mid + 1, r) {
for (auto it : vec[i]) {
int L = it.l, R = it.r, k = it.k;
upd (1, 1, n, L, R, - k);
}
}
for (auto it : vc[p]) {
vvc[it.l1].eb ((oper) {it.l2, it.r2, it.i});
}
cover (1);
rrp (i, l, mid) {
for (auto it : vvc[i]) {
ans[it.k] = max (ans[it.k], qry (1, 1, n, it.l, it.r));
}
for (int j = vec[i].size (); j >= 0; -- j) {
if (j == vec[i].size ()) continue;
int L = vec[i][j].l, R = vec[i][j].r, k = vec[i][j].k;
upd (1, 1, n, L, R, - k);
// if(p==3)
// cout<<L<<" "<<R<<" "<<-k<<" "<<i<<" "<<his[1]<<endl;
} vvc[i].clear ();
}
solve (ls, l, mid);
}
signed main () {
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
n = rd (), m = rd (), q = rd (); ++ n;
rep (i, 1, m) {
int l1 = rd (), l2 = rd (), r1 = rd (), r2 = rd (), x = rd ();
vec[l1].eb ((oper) {l2, r2, x}), vec[r1 + 1].eb ((oper) {l2, r2, - x});
}
rep (i, 1, n) sort (vec[i].begin (), vec[i].end ());
rep (i, 1, q) {
int l1 = rd (), l2 = rd (), r1 = rd (), r2 = rd ();
insert (1, 1, n, (ask) {l1, r1, l2, r2, i});
}
solve (1, 1, n);
rep (i, 1, q) printf ("%lld\n", ans[i]);
}