Post 21

Veröffentlicht am

菜是原罪，有bb,感叹人生以及给自己打气的时间不如现在就清楚的意识到自己是个渣渣的本质

然后去刷几道题来提升一下你本来就没多少的水平 — shadowice1984

今天脑子清醒了点，开始做题。

BZOJ2716. [Violet 3]天使玩偶

DESCRIPTION

img

Input

img

Output

img

题解

昨天看过这道题，结果由于太颓没有写完。

显然在纸上分类讨论四个象限后用线段树维护区间最值，然后CDQ分治即可。

感觉CDQ分治真的不是什么难东西啊，就是基础分治的思想而已。

简单来说就是每次递归然后用静态算法比如扫描线之类的去处理问题，复杂度昨天分析了。。。。

因此这道题可以在$O((n+m)log^2(n+m))$的时间里解决

上理论可以AC但实际卡常的代码。。换权值成树状数组维护前缀最大值或者换成对结构体基数排序应该都能AC。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 500005
#define maxv 1000005
#define INF 0x7ffffff
int ans[maxn<<1] , n , m , seg[maxv<<2] , mx;
inline void pushup(int x){
	seg[x] = std::max(seg[x<<1] , seg[x<<1|1]);
}
void update(int pos , int l , int r , int v , int node)
{
	if(l == r){
		seg[node] = v;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) update(pos , l , mid , v , node << 1);
	else update(pos , mid + 1 , r , v , node << 1 | 1);
	pushup(node);
}
int query(int l , int r , int L , int R , int node)
{
	if(L <= l && r <= R)	return seg[node];
	int mid = l + r >> 1 , ans = -0x7ffffff;
	if(L <= mid) ans = std::max(ans , query(l , mid , L , R , node << 1));
	if(R > mid) ans = std::max(ans , query(mid + 1 , r , L , R , node << 1|1));
	return ans;
}
struct Node{
	int x , y , ty ,num;
	bool operator<(const Node& k)const{
		if(x == k.x) return ty < k.ty;
		return x < k.x;
	}
}q[maxn<<1] , tmp[maxn<<1];
bool cmp(const Node& a , const Node& b){
	if(a.x == b.x) return a.ty < b.ty;
	return a.x > b.x;
}
inline void solve(int l , int r)
{
	if(l == r) return;
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid + 1, r);
	for(int i = l ; i <= r ; ++i)
		tmp[i] = q[i];
		
	std::sort(tmp+l,tmp+r+1);
	for(int i = l ; i <= r ; ++i)
	{
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , tmp[i].x + tmp[i].y , 1);
		else if(tmp[i].ty == 2 && tmp[i].num > mid)	
			ans[tmp[i].num] = std::min(ans[tmp[i].num] , tmp[i].x + tmp[i].y - query(0 , mx , 0 , tmp[i].y , 1));

	}
	for(int i = l ; i <= r ; ++i)
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , -INF , 1);
	
	for(int i = l ; i <= r ; ++i)
	{
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , tmp[i].x - tmp[i].y , 1);
		else if(tmp[i].ty == 2 && tmp[i].num > mid) ans[tmp[i].num] = std::min(ans[tmp[i].num] , tmp[i].x - tmp[i].y - query(0,mx,tmp[i].y,mx,1));
	}
	for(int i = l ; i <= r ; ++i)
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , -INF , 1);
		
	std::sort(tmp+l,tmp+r+1,cmp);
	for(int i = l ; i <= r ; ++i)
	{
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , tmp[i].y-tmp[i].x , 1);
		else if(tmp[i].ty == 2 && tmp[i].num > mid) ans[tmp[i].num] = std::min(ans[tmp[i].num] , tmp[i].y-tmp[i].x-query(0,mx,0,tmp[i].y,1));
	}
	for(int i = l ; i <= r ; ++i)
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , -INF , 1);
		
	for(int i = l ; i <= r ; ++i)
	{
		if(tmp[i].ty == 1 && tmp[i].num <= mid) update(tmp[i].y , 0 , mx , -tmp[i].y-tmp[i].x , 1);
		else if(tmp[i].ty == 2 && tmp[i].num > mid) ans[tmp[i].num] = std::min(ans[tmp[i].num] , -tmp[i].x-tmp[i].y-query(0 , mx , tmp[i].y , mx , 1));
	}
	for(int i = l ; i <= r ; ++i)
		if(tmp[i].ty == 1 && tmp[i].num <= mid)	update(tmp[i].y , 0 , mx , -INF , 1);
}
inline int read()
{
	register int x = 0;
	char ch = getchar();
	while(ch > '9' || ch < '0') ch = getchar();
	while(ch <= '9' && ch >= '0') x = (x<<3)+(x<<1) + ch - 48 , ch = getchar();
	return x;
}
int main()
{
	std::memset(ans,0x7f,sizeof(ans));
	n = read() , m = read();
	for(int i = 0 ; i <= (1000000<<2);++i)	seg[i] = -INF;
	for(int i = 1 ; i <= n ; ++i){
		q[i].x = read() , q[i].y = read() ,q[i].num = i ,  q[i].ty = 1 , mx = std::max(mx , q[i].x) , mx = std::max(mx , q[i].y);
	}
	for(int i = 1 ; i <= m ; ++i)
		q[n+i].ty = read() , q[n+i].x = read() , q[n+i].y = read() ,q[i+n].num = n+i,  mx = std::max(mx , q[n+i].x) , mx = std::max(mx , q[n+i].y);
	++mx;
	solve(1,n+m+1);
	for(int i = 1 ; i <= n + m ; ++i)
		if(q[i].ty == 2)
			printf("%d\n",ans[i]);			
	return 0;
}