<div class="post_brief"><p>
这么水的题居然还要写题解。要不要说我写了半个下午+半个晚上。</p>

 

丧心病狂想写一发zkw去抢速度rank。然后发现zkw怎么支持区间修改查询TT。课件根本没讲懂。而且max怎么区间加。

 

想了很久终于想出了来了。然后交上去发现常数巨大比普通线段树还要慢TT。到头来想想如果我直接写普通线段树说不定十多分钟就能过，而且代码量还会小一些。因为那个是可以直接通用的，但是这个比较麻烦。

 

其实写这个就题解就是想记录一下我yy出来的zkw区间修改区间查询的方法。

 

这道题是区间查询最大值+区间修改。如果是写一般的线段树，需要记录两个值a和v（至于为啥我用了这俩神奇的字母我也不知道），分别表示当前区间被完整覆盖的修改的最大值（又称lazy标记）和当前区间的最大值。然后所以zkw也要记这两个东西。

 

如果我们把zkw看作一棵树，那么每次修改和询问操作的时候都是对一些线段的a和v进行操作。（废话）

 

首先考虑修改。zkw经典的变为开区间取中间能处理a值的改变，但是不能处理v值的改变。因为v值改变的线段不一定会被当前区间包含。然后仔细考虑发现a值没有变但是v值变了的点只可能存在于两个端点到根的路径上。那就直接强行更新一发就好了啊。然后更新的区域就变成了一个有点像倒置漏斗的形状。

 

再考虑询问。a要覆盖当前区间，v要被当前区间覆盖。那不就是修改把a和v的做法反一下么。

 

然后好像也不是很麻烦的样子哈。

 

然后常数很大哈。

 

那还拿zkw做何用。

 

晕。

 

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;


const int buf_len = 4567;
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() { 

if (++ bufb == bufe) 

bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); 

}
#define readInt(x) { 

register int s(0); 

do { 

readBuf(); 

} while (!isdigit(*bufb)); 

do { 

s = s * 10 + *bufb - 48; 

readBuf(); 

} while (isdigit(*bufb)); 

x = s; 

}


const int maxn = 2049;


int q, n, m, bn, bm;


inline void upMax(int& a, int b) {
if (a < b)
a = b;
}
#define upMax_d(a,b) { 

if (a < b) 

a = b; 

}


struct zkw_tree_y {
int v[maxn], a[maxn];
zkw_tree_y() {
memset(v, 0, sizeof(v));
memset(a, 0, sizeof(a));
}
int qry(int lo, int ro) {
int s(0), l, r;
for (l = lo + bm; l; l >>= 1)
upMax_d(s, a[l]);
for (r = ro + bm; r; r >>= 1)
upMax_d(s, a[r]);
for (l = lo + bm - 1, r = ro + bm + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (!(l & 1))
upMax_d(s, v[l ^ 1]);
if (r & 1)
upMax_d(s, v[r ^ 1]);
}
return s;
}
void chg(int lo, int ro, int h) {
int l, r;
for (l = lo + bm; l; l >>= 1)
upMax_d(v[l], h);
for (r = ro + bm; r; r >>= 1)
upMax_d(v[r], h);
for (l = lo + bm - 1, r += ro + bm + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (!(l & 1)) {
upMax_d(a[l ^ 1], h);
upMax_d(v[l ^ 1], h);
}
if (r & 1) {
upMax_d(a[r ^ 1], h);
upMax_d(v[r ^ 1], h);
}
}
}
};


zkw_tree_y v[maxn], a[maxn];


int zkwQryX(int lo, int ro, int yl, int yr) {
int s(0), l, r;
for (l = lo + bn; l; l >>= 1)
upMax(s, a[l]. qry(yl, yr));
for (r = ro + bn; r; r >>= 1)
upMax(s, a[r]. qry(yl, yr));
for (l = lo + bn - 1, r = ro + bn + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (!(l & 1))
upMax(s, v[l ^ 1]. qry(yl, yr));
if (r & 1)
upMax(s, v[r ^ 1]. qry(yl, yr));
}
return s;
}
void zkwChgX(int lo, int ro, int yl, int yr, int h) {
int l, r;
for (l = lo + bn; l; l >>= 1)
v[l]. chg(yl, yr, h);
for (r = ro + bn; r; r >>= 1)
v[r]. chg(yl, yr, h);
for (l = lo + bn - 1, r = ro + bn + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (!(l & 1)) {
a[l ^ 1]. chg(yl, yr, h);
v[l ^ 1]. chg(yl, yr, h);
}
if (r & 1) {
a[r ^ 1]. chg(yl, yr, h);
v[r ^ 1]. chg(yl, yr, h);
}
}
}


int main() {
#ifndef ONLINE_JUDGE
//	freopen(“in.txt”, “r”, stdin);
#endif


readInt(n);
readInt(m);
readInt(q);
memset(a, 0, sizeof(a));
memset(v, 0, sizeof(v));
for (bn = 1; bn &lt; n + 2; bn &lt;&lt;= 1);
for (bm = 1; bm &lt; m + 2; bm &lt;&lt;= 1);
while (q --) {
	int x, y, p, q, h;
	readInt(p);
	readInt(q);
	readInt(h);
	readInt(x);
	readInt(y);
	p += x ++, q += y ++;
	h += zkwQryX(x, p, y, q);
	zkwChgX(x, p, y, q, h);
}
printf("%d\n", zkwQryX(1, n, 1, m));



}