BZOJ1513 [POI2006]Tet-Tetris 3D

这么水的题居然还要写题解。要不要说我写了半个下午+半个晚上。

丧心病狂想写一发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 < n + 2; bn <<= 1);
	for (bm = 1; bm < m + 2; bm <<= 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));
}