【题解】[Ynoi2009] rprmq
题目链接：[Ynoi2009] rprmq
题意：
有一个 $n \times n$ 的矩阵 $A$，初始全是 $0$，有 $m$ 次修改操作和 $q$ 次查询操作，先进行所有修改操作，然后进行所有查询操作。
一次修改操作会给出 $l_1,l_2,r_1,r_2,x$，代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素加上一个值 $x$。
一次查询操作会给出 $l_1,l_2,r_1,r_2$，代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素的最大值。
$1\le n,m\le 5\times 10^4,1\le q \le 5\times 10^5$。
或许是一个实现方式有一些小差别的做法。
首先考虑离线分治，每次考虑跨过分治中心的查询与修改。
将第二维放在线段树上，第一维做扫描线，每次从分治中心 $\text{mid}$ 向左、右进行拓展，如果遇到一个矩阵的开始，或一个矩阵的结束，就在线段树上进行区间修改。
由于我们需要的是“矩形 $\max$”，而在分治的时候，第一维变成了时间，所以这个问题在这里就是线段树历史 $\max$。
于是对于一个跨过 $\text{mid}$ 的询问，我们只需要在扫描线到了左端点处，或到了右端点处的时候，查询区间历史最大值即可。
这一部分中，一个实现的细节是当扫描完 $\text{mid}$ 左侧时，需要将整棵线段树的状态 $\text{roll back}$ 回到还没有扫描左侧时的状态，然后再进行右侧的扫描线。这个可以通过直接对线段树 $\text{DFS}$，将每一个遍历过的节点的权值进行回滚来做到。
另一个容易错的点是，如果一个位置上同时有矩形的结束与矩形的开始（即有区间加与区间减操作），那么应该先进行区间减操作，这样才能使历史 $\max$ 保持正确。
这样单次查询的复杂度就是 $\mathcal{O}(\log n)$ 的，$\mathcal{O}(q\log n)$ 的总复杂度可以接受。
但是修改的复杂度实际上是不太对的。在一般的分治中，其时间复杂度的保证基于每一个操作在进入分治树下一层的时候，都只会进入一边（一个分治树节点）。然而在这里，一个跨越了 $\text{mid}$ 的操作，可以同时向 $[\text{L},\text{mid}]$ 与 $[\text{mid+1},\text{R}]$ 进行递归。
也就是说，任意一个修改实际上是在分治的时间维度的一个区间上存在的，而分治的结构本身就类似一棵线段树，所以可以认为一个操作是存在在分治树的一个区间上的。
由于分治树是线段树结构，而操作存在在分治树的区间上，这让我们想到“线段树分治”。线段树分治的思想就是将一个存在在某个时间段的修改划分为 $\log$ 个部分，通过在 $\text{DFS}$ 整棵线段树的时候，维护当前线段树节点的祖先的所有修改操作，来保证复杂度。
于是，把这个思想套到本题上，就变成了：如果一个操作完全覆盖了当前的分治区间，则把他看作一个类似“初值”的部分。
因为在这个区间中这次操作永远存在，所以只需要在进入区间的时候将该操作执行，则分治树的子树中这个操作就一直存在了。
从而一个操作被拆分成了 $\mathcal{O}(\log n)$ 次操作，总复杂度是 $\mathcal{O}(m\log^2n+q\log n)$。
一个细节：由于进行分治的过程中可能需要进行状态的回滚，而状态的修改次数是 $\mathcal{O}(m\log^2 n)$ 的，直接记录的话空间将与时间同阶。
不过实际上，即使修改次数是 $\mathcal{O}(n\log^2 n)$，其修改的元素个数却是 $\mathcal{O}(n\log n)$，可以通过把可回退的部分较为精细地实现来保证空间复杂度。
//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define pb emplace_back
#define LL long long
#define mp make_pair
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1
const int MAXN = 5e4 + 10;
const int MAXQ = 5e5 + 10;
const int MAXD = 16;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
struct info {
int l, r, x;
info(int _l = 0, int _r = 0, int _x = 0) : l(_l), r(_r), x(_x) {}
bool operator < (const info &b) const { return x < b.x; }
};
int n, m, q;
LL Ans[MAXQ];
vec<info> qp[MAXN], add[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }
struct NODE {
int l1, l2, r1, r2, x, id;
void read(int i) { id = i, ::read(l1), ::read(l2), ::read(r1), ::read(r2); }
}; vec<NODE> qs[MAXN << 2], mdf[MAXN << 2];
inline LL max(const LL x, const LL y) { return x > y ? x : y; }
namespace SMT {
int D;
LL mx[MAXN << 2], hmx[MAXN << 2], tag[MAXN << 2], htag[MAXN << 2];
LL mx_bak[MAXD][MAXN << 2], hmx_bak[MAXD][MAXN << 2];
LL tag_bak[MAXD][MAXN << 2], htag_bak[MAXD][MAXN << 2];
bool vis[MAXD][MAXN << 2];
inline void pushup(const LL &x) {
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
hmx[x] = max(hmx[x], mx[x]);
}
inline void push(const int &x, const LL &v, const LL &hv) {
htag[x] = max(htag[x], tag[x] + hv);
tag[x] = tag[x] + v;
hmx[x] = max(hmx[x], mx[x] + hv);
mx[x] = mx[x] + v;
}
inline void pushdown(const LL &x) {
push(x << 1, tag[x], htag[x]);
push(x << 1 | 1, tag[x], htag[x]);
htag[x] = 0; tag[x] = 0;
}
void save(int x) {
if(!vis[D][x]) {
vis[D][x] = true;
mx_bak[D][x] = mx[x], hmx_bak[D][x] = hmx[x];
tag_bak[D][x] = tag[x], htag_bak[D][x] = htag[x];
}
}
void update(int x, int l, int r, int L, int R, int v) {
save(x);
if(L <= l && r <= R) return push(x, v, v), void();
int mid = (l + r) >> 1;
save(x << 1), save(x << 1 | 1); pushdown(x);
if(L <= mid) update(x << 1, l, mid, L, R, v);
if(R > mid) update(x << 1 | 1, mid + 1, r, L, R, v);
pushup(x);
}
LL query(int x, int l, int r, int L, int R) {
save(x);
if(L <= l && r <= R) return hmx[x];
int mid = (l + r) >> 1; LL res = 0;
save(x << 1), save(x << 1 | 1); pushdown(x);
if(L <= mid) res = max(res, query(x << 1, l, mid, L, R));
if(R > mid) res = max(res, query(x << 1 | 1, mid + 1, r, L, R));
return res;
}
void clear(int x, int l, int r) {
if(!vis[D][x]) return;
vis[D][x] = false;
if(l == r) return;
int mid = (l + r) >> 1;
clear(x << 1, l, mid), clear(x << 1 | 1, mid + 1, r);
}
void roll(int x, int l, int r) {
if(!vis[D][x]) return;
mx[x] = mx_bak[D][x], hmx[x] = hmx_bak[D][x];
tag[x] = tag_bak[D][x], htag[x] = htag_bak[D][x];
vis[D][x] = false;
if(l == r) return;
int mid = (l + r) >> 1;
roll(x << 1, l, mid), roll(x << 1 | 1, mid + 1, r);
}
}
using SMT::update;
using SMT::query;
using SMT::clear;
using SMT::roll;
using SMT::D;
void solve(int _x, int vL, int vR, int dep) {
if(vL > vR || !qs[_x].size()) return;
int mid = (vL + vR) >> 1; NODE cur;
for(auto x : qs[_x]) {
if(x.r1 < mid) qs[_x << 1].pb(x);
if(x.l1 > mid) qs[_x << 1 | 1].pb(x);
if(x.l1 <= mid && mid <= x.r1) {
qp[x.l1].pb(info(x.l2, x.r2, x.id));
qp[x.r1].pb(info(x.l2, x.r2, x.id));
}
}
for(auto x : mdf[_x]) {
if(x.r1 < mid) {
mdf[_x << 1].pb(x), add[x.r1].pb(info(x.l2, x.r2, x.x));
if(vL < x.l1) add[x.l1 - 1].pb(info(x.l2, x.r2, -x.x));
} else if(x.l1 > mid) {
mdf[_x << 1 | 1].pb(x), add[x.l1].pb(info(x.l2, x.r2, x.x));
if(x.r1 < vR) add[x.r1 + 1].pb(info(x.l2, x.r2, -x.x));
} else if(x.l1 <= mid && mid <= x.r1) {
add[mid].pb(info(x.l2, x.r2, x.x));
if(vL < x.l1) add[x.l1 - 1].pb(info(x.l2, x.r2, -x.x));
if(x.r1 < vR) add[x.r1 + 1].pb(info(x.l2, x.r2, -x.x));
}
} D = dep; clear(1, 1, n);
for(int i = mid; i >= vL; --i) {
sort(add[i].begin(), add[i].end());
for(auto x : add[i]) update(1, 1, n, x.l, x.r, x.x);
for(auto x : qp[i]) Ans[x.x] = max(Ans[x.x], query(1, 1, n, x.l, x.r));
} roll(1, 1, n);
for(int i = mid; i <= vR; ++i) {
sort(add[i].begin(), add[i].end());
for(auto x : add[i]) update(1, 1, n, x.l, x.r, x.x);
for(auto x : qp[i]) Ans[x.x] = max(Ans[x.x], query(1, 1, n, x.l, x.r));
} roll(1, 1, n);
for(int i = vL; i <= vR; ++i) add[i].clear(), qp[i].clear();
for(auto x : mdf[_x]) {
if(x.l1 < mid && mid <= x.r1) {
if(x.l1 <= vL) update(1, 1, n, x.l2, x.r2, x.x);
else { cur = x; cur.r1 = mid - 1; mdf[_x << 1].pb(cur); }
}
} solve(_x << 1, vL, mid - 1, dep + 1); D = dep; roll(1, 1, n);
for(auto x : mdf[_x]) {
if(x.l1 <= mid && mid < x.r1) {
if(x.r1 >= vR) update(1, 1, n, x.l2, x.r2, x.x);
else { cur = x; cur.l1 = mid + 1; mdf[_x << 1 | 1].pb(cur); }
}
} solve(_x << 1 | 1, mid + 1, vR, dep + 1); D = dep; roll(1, 1, n);
}
signed main () {
#ifdef FILE
freopen("P6109.in", "r", stdin);
freopen("P6109.out", "w", stdout);
#endif
read(n), read(m), read(q); mdf[1].resize(m), qs[1].resize(q);
for(int i = 0; i < m; ++i) mdf[1][i].read(i), read(mdf[1][i].x);
for(int i = 0; i < q; ++i) qs[1][i].read(i + 1);
solve(1, 1, n, 0);
for(int i = 1; i <= q; ++i) printf("%lld\n", Ans[i]);
return 0;
}
LATEX炸了
确实