Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

翻车笔记 2018-03-07考试 [线段树, 扫描线, 二维线段树, 标记持久化]

Posted on Edited on In

正难则反 非常常见的道理却非常难应用

转化查询和修改, 平衡复杂度往往会有意想不到的效果

懵逼的 题目

T1

T2

T3

扯淡的 题解

难得题目质量不错, 所以然而差点爆零

T1

感谢舒老师耐心的讲解

我们发现T1单点修改非常简单啊, 但是查询一个矩形非常不资瓷啊, 我们想一想, 这么坑的题怎么会让你只有单点修改这么简单??? 那么, 我们看看区间修改能不能套到这个题上面...

于是我们把一棵星星能影响到当前窗口的区间(纵向)都加上他的亮度, 不能影响当前的窗口后就都减去这个亮度, 这样我们只要查询整个区间的最大值就可以了, 然后上扫描线, 直接滑动窗口就可以搞出一个矩形来, 然后更新答案即可

大概是这个样子
  • 红色代表加上一颗星星的亮度, 绿色代表减去这颗星星的亮度
  • 蓝色代表那颗星星
  • 灰色虚线表示对齐(OneNote没有内置的虚线差评
  • 橙色的矩形代表窗户
  1. 一颗星星对答案的影响范围就是上下两个窗户宽的范围, 也就是说窗户只要下边界在红色底端点的上面, 上边界在红色上端点的下面, 就会对这个状态的窗户产生这颗星星亮度的贡献影响
  2. 而整个窗口中如果亮度会发生变化, 一定是在有星星看不见, 或者新加入一颗星星的时候, 那么我们只需要在红色和绿色的横坐标处统计亮度和 并 更新答案即可, 复杂度是\(\mathrm O(\mathrm T\, n\lg n)\)

T1代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define LL long long
using namespace std;
struct node
{
	int le, ri;
	LL maxz, lazy;
}b[MAXN << 3];
struct question
{
	int le, ri, zh, wz;
}q[MAXN];
int n, w, h;
LL sorx[MAXN], sory[MAXN], ans;
void push_up(int dq)
{ b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz); }
void push_down(int dq)
{
	LL& x = b[dq].lazy;
	b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
	b[LS(dq)].maxz += x, b[RS(dq)].maxz += x;
	x = 0;
}
void js(int dq, int le, int ri)
{
	b[dq].le = le, b[dq].ri = ri, b[dq].maxz = b[dq].maxz = 0;
	if (le == ri)
		return ;
	int mi = (le + ri) >> 1;
	js(LS(dq), le, mi);
	js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
	if (b[dq].le == le && b[dq].ri == ri)
	{
		b[dq].maxz += zh, b[dq].lazy += zh;
		return ;
	}
	push_down(dq);
	int mi = (b[dq].le + b[dq].ri) >> 1;
	if (le > mi)
		xg(RS(dq), le, ri, zh);
	else if (ri <= mi)
		xg(LS(dq), le, ri, zh);
	else
		xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
	push_up(dq);
}
void solve()
{
	int last = n + 1;
	for (int i = 1; i <= n; i++)
	{
		xg(1, q[i].le, q[i].ri, q[i].zh);
		while (q[last].wz + w <= q[i].wz)
			xg(1, q[last].le, q[last].ri, q[last].zh), ++last;
		ans = max(ans, b[1].maxz);
	}
}
bool cmp(question x, question y)
{ return x.wz < y.wz; }
void init()
{
	ans = 0;
	scanf("%d%d%d", &n, &w, &h);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d%d", &sorx[i], &sory[i], &q[i].zh);
		q[i].wz = sorx[i], sory[i + n] = q[i].le = sory[i], sory[i] = q[i].ri = sory[i] + h - 1;
		q[i + n] = q[i];
		q[i + n].zh = -q[i].zh;
	}
	sort(sorx + 1, sorx + n + 1);
	sort(sory + 1, sory + (n << 1) + 1);
	sorx[0] = unique(sorx + 1, sorx + n + 1) - sorx - 1;
	sory[0] = unique(sory + 1, sory + (n << 1) + 1) - sory - 1;
	for (int i = 1; i <= (n << 1); i++)
	{
		q[i].le = max(1, (int) (lower_bound(sory + 1, sory + sory[0] + 1, q[i].le) - sory));
		q[i].ri = min(MAXN - 1, (int) (lower_bound(sory + 1, sory + sory[0] + 1, q[i].ri) - sory));
	}
	sort(q + 1, q + n + 1, cmp);
	sort(q + n + 1, q + (n << 1) + 1, cmp);
	js(1, 1, MAXN - 1);
}
int main()
{
	freopen("stars.in", "r", stdin);
	freopen("stars.out", "w", stdout);
	int t = 1;
//	scanf("%d", &t);
	while (t--)
	{
		init();
		solve();
		printf("%lld\n", ans);
	}
	return 0;
}

/*
2
3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1
*/

T2

考试前一天Steven张dalao刚问我 矩形周长并 && 矩形面积并&& 矩形面积交 的一些问题...我就正好学了一波标记永久化的写法, 发现非常资瓷啊, 写起来非常方便啊...然后第二天就考了...

T2代码

注意这时候线段树的叶子节点代表的是一段区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (100000 + 5)
#define MAXJ (10000 + 1)
#define MAXQ ()
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-(a)) : (a))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct node // 叶子[le, le]实际代表线段[le, le + 1] 
{
	int cnt, zh, le, ri; // 那么其实这个节点代表的值是 [le, ri + 1] 
}b[MAXN << 4];
struct que
{
	int x, y, wz, zh;
	que(int a, int b, int w, int c): x(a), y(b), wz(w), zh(c) {}
};
void js(int, int, int);
void push_up(int);
void xg(int, int, int, int);
bool cmp(que, que);
int main()
{
//#define DEBUG
#ifndef DEBUG
	freopen("picture.in", "r", stdin);
	freopen("picture.out", "w", stdout);
#endif
	int n, inf = 0;
	vector<que> qx, qy;
	scanf("%d", &n);
	/*
	从左到右, 从下到上 
				xx, yy
	-------------
	|			|
	|			|
	-------------
	x, y
	*/
	for (int i = 1; i <= n; i++)
	{
		int x, y, xx, yy;
		scanf("%d%d%d%d", &x, &y, &xx, &yy);
		x += MAXJ, y += MAXJ, xx += MAXJ, yy += MAXJ;
		inf = max(inf, max(max(x, y), max(xx, yy)));
		qx.push_back(que(y, yy, x, 1));
		qx.push_back(que(y, yy, xx, -1));
		qy.push_back(que(x, xx, y, 1));
		qy.push_back(que(x, xx, yy, -1));
	}
	sort(qx.begin(), qx.end(), cmp);
	sort(qy.begin(), qy.end(), cmp);
	js(1, 1, inf);
	int ans = 0;
	for (int i = 0; i < qx.size(); i++)
	{
		int last = b[1].zh;
		xg(1, qx[i].x, qx[i].y - 1, qx[i].zh);
		ans += abs(b[1].zh - last);
	}
	js(1, 1, inf);
	for (int i = 0; i < qy.size(); i++)
	{
		int last = b[1].zh;
		xg(1, qy[i].x, qy[i].y - 1, qy[i].zh);
		ans += abs(b[1].zh - last);
	}
	printf("%d", ans);
	return 0;
}
void js(int dq, int le, int ri)
{
	b[dq].le = le, b[dq].ri = ri;
	b[dq].zh = b[dq].cnt = 0;
	if (le == ri)
		return ;
	int mi = (le + ri) >> 1;
	js(LS(dq), le, mi);
	js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
	if (b[dq].le == le && b[dq].ri == ri)
	{
		b[dq].cnt += zh;
		push_up(dq);
		return ;
	}
	int mi = (b[dq].le + b[dq].ri) >> 1;
	if (le > mi)
		xg(RS(dq), le, ri, zh);
	else if (ri <= mi)
		xg(LS(dq), le, ri, zh);
	else
		xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
	push_up(dq);
}
void push_up(int dq)
{
	b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
	if (b[dq].cnt > 0)
		b[dq].zh = (b[dq].ri - b[dq].le + 1);
}
bool cmp(que x, que y)
{
	if (x.wz == y.wz)
		return x.zh > y.zh;
	else
		return x.wz < y.wz;
}

/*
2
1 1 3 3
2 2 4 4


7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
*/

T3

裸的二维线段树 区间覆盖, 区间max

我们发现直接肛二维线段树下发标记非常不资瓷啊...比如我就直接写残了...

然后捏, 我们看(参悟)了看(参悟)po爷爷的blog发现"woc还有这种操作"

...

标记永久化

我们需要维护一个值: maxz代表区间的最大值

我们要记录两个标记,:

  • 一个rootdq代表当前的矩形被完全覆盖的贡献(也就是当前节点代表的矩形\(\in\)一次修改中的矩形)
  • 一个rootson代表自己的儿子节点中覆盖的贡献(也就是一次修改中的矩形不必完全覆盖当前节点代表的矩形, 而是覆盖到了当前节点的一个子矩形)

这样, 我们修改的时候, 沿途的节点都修改rootson, 最后完美覆盖的节点修改rootdq即可

而查询的时候相反, 沿途的节点都查询rootdq以更新要查找矩形最大被覆盖的值, 最后完美覆盖的节点查询rootson来看子矩形是否被覆盖过更大的值

还是挺妙的对吧?

T3代码

出了半天的错, 又WA又T发现是\(\max\)的锅...

如果这么写\(\max\)函数: #define max(a, b) ((a) > (b) ? (a) :(b)), 然后你又将函数的返回值当成变量放在了max()里, 而你的函数又恰好会对某些全局的值造成影响, 你就会发现你的值被改变了两次...\(\to \mathrm {GG}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define fa(dq) ((dq) >> 1)
//#define max(a, b) ((a) > (b) ? (a) : (b))
//#define min(a, b) ((a) < (b) ? (a) : (b))
#define MAXN (10000 + 5)
using namespace std;
struct nodex
{
	int ls, rs, le, ri, maxz, lazy; // [le, ri + 1]
	nodex(): ls(0), rs(0), maxz(0), lazy(0) {}
}bx[MAXN << 8];
struct nodey
{
	int le, ri, lazy, rootdq, rootson; // [le, ri + 1]
	nodey(): lazy(0) {}
}by[MAXN << 3];
int n, d, s;
static int cnt = 0;
inline int newnode(int le, int ri)
{
	bx[++cnt].le = le, bx[cnt].ri = ri;
	return cnt;
}
void jsy(int dq, int le, int ri)
{
	by[dq].le = le, by[dq].ri = ri;
	by[dq].rootdq = newnode(1, d);
	by[dq].rootson = newnode(1, d);
	if (le == ri)
		return ;
	int mi = (le + ri) >> 1;
	jsy(LS(dq), le, mi);
	jsy(RS(dq), mi + 1, ri);
}
int cxx(int dq, int le, int ri)
{
	if (!dq)
		return 0;
	int re = bx[dq].lazy;
	if (bx[dq].le == le && bx[dq].ri == ri)
		return max(re, bx[dq].maxz);
	int mi = (bx[dq].le + bx[dq].ri) >> 1;
	if (le > mi)
		return max(re, cxx(bx[dq].rs, le, ri));
	else if (ri <= mi)
		return max(re, cxx(bx[dq].ls, le, ri));
	else
		return max(re, max(cxx(bx[dq].ls, le, mi), cxx(bx[dq].rs, mi + 1, ri)));
}
int cxy(int dq, int le, int ri, int lx, int rx)
{
	int re = cxx(by[dq].rootdq, lx, rx);
	if (by[dq].le == le && by[dq].ri == ri)
		return max(re, cxx(by[dq].rootson, lx, rx));
	int mi = (by[dq].le + by[dq].ri) >> 1;
	if (ri <= mi)
		return max(re, cxy(LS(dq), le, ri, lx, rx));
	else if (le > mi)
		return max(re, cxy(RS(dq), le, ri, lx, rx));
	else
		return max(re, max(cxy(LS(dq), le, mi, lx, rx), cxy(RS(dq), mi + 1, ri, lx, rx)));
}
void xgx(int& dq, int le, int ri, int zh, int dql, int dqr)
{
	if (!dq)
		dq = newnode(dql, dqr);
	bx[dq].maxz = max(bx[dq].maxz, zh);
	if (dql == le && dqr == ri)
	{
		bx[dq].lazy = max(bx[dq].lazy, zh);
		return ;
	}
	int mi = (dql + dqr) >> 1;
	if (ri <= mi)
		xgx(bx[dq].ls, le, ri, zh, dql, mi);
	else if (le > mi)
		xgx(bx[dq].rs, le, ri, zh, mi + 1, dqr);
	else
		xgx(bx[dq].ls, le, mi, zh, dql, mi), xgx(bx[dq].rs, mi + 1, ri, zh, mi + 1, dqr);
}
void xgy(int dq, int le, int ri, int lx, int rx, int zh)
{
//	if (le > ri)	return ;
	xgx(by[dq].rootson, lx, rx, zh, 1, d);
	if (by[dq].le == le && by[dq].ri == ri)
	{
		xgx(by[dq].rootdq, lx, rx, zh, 1, d);
		return ;
	}
	int mi = (by[dq].le + by[dq].ri) >> 1;
	if (ri <= mi)
		xgy(LS(dq), le, ri, lx, rx, zh);
	else if (le > mi)
		xgy(RS(dq), le, ri, lx, rx, zh);
	else
		xgy(LS(dq), le, mi, lx, rx, zh), xgy(RS(dq), mi + 1, ri, lx, rx, zh);
}
int main()
{
//#define DEBUG
#ifndef DEBUG
	freopen("tet.in", "r", stdin);
	freopen("tet.out", "w", stdout);
#endif
	scanf("%d%d%d", &d, &s, &n);
	jsy(1, 1, s);
	for (int i = 1; i <= n; i++)
	{
		int chang, kuan, gao, x, y, xx, yy;
		scanf("%d%d%d%d%d", &chang, &kuan, &gao, &x, &y);
		++x, ++y;
		xx = x + chang, yy = y + kuan;
//		printf("case #%d: HI~ x: %d, xx: %d, y: %d, yy: %d, le: %d\n", i, x, xx, y, yy, by[1].le);
		int maxh = cxy(1, y, yy - 1, x, xx - 1);
//		printf("case #%d: %d x: %d, xx: %d, y: %d, yy: %d, le: %d\n", i, maxh, x, xx, y, yy, by[1].le);
		xgy(1, y, yy - 1, x, xx - 1, maxh + gao);
//		printf("case #%d: %d\n", i, by[1].le);
//		printf("case #%d: %d\n", i, cnt);
	}
	printf("%d", cxy(1, 1, s - 1, 1, d - 1));
	return 0;
}

/*
7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
*/

By 险些爆零并疯狂\(\bmod (AKfun + TreeLovesWater)\)的 Cansult