bzoj 3995 道路修建

Posted on | Views:

线段树维护区间信息.

利用线段树维护每个区间的答案.

合并两个区间时,把连接处的两条横边都连上,会和两边的竖边形成一个矩形的环,再把这个环的最大边断掉.

对于一个区间,需要维护它的答案,这棵生成树的最左/右的竖边,竖边内横边的最大值,所有横边的最大值.

合并时大力讨论删掉的是哪条边,把参数转移一下,时间复杂度 $O(n\log n)$ .

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=6e4+10;
int n,m;
int rval[2][MAXN],cval[MAXN];
struct node
{
	int l,r,ans,lc,rc,lmx,rmx,mx;
	node(){ans=lmx=rmx=0;}
	friend node operator + (const node &lson,const node &rson)
	{
		node root;
		root.l=lson.l,root.r=rson.r;
		root.mx=max(max(lson.mx,rson.mx),max(rval[0][lson.r],rval[1][lson.r]));
		root.ans=lson.ans+rval[0][lson.r]+rval[1][lson.r]+rson.ans;
		int mx=max(max(rval[0][lson.r],rval[1][lson.r]),max(lson.rmx,rson.lmx));
		if(cval[lson.rc]<mx && cval[rson.lc]<mx)
		{
			root.ans-=mx;
			root.lc=lson.lc,root.lmx=lson.lmx;
			root.rc=rson.rc,root.rmx=rson.rmx;
		}
		else
		{
			root.ans-=max(cval[lson.rc],cval[rson.lc]);
			if(cval[lson.rc]<cval[rson.lc])
			{
				if(rson.lc==rson.rc)
				{
					root.rc=lson.rc;
					root.rmx=max(max(lson.rmx,rson.mx),max(rval[0][lson.r],rval[1][lson.r]));
				}
				else
				{
					root.rc=rson.rc;
					root.rmx=rson.rmx;
				}
				root.lc=lson.lc;
				root.lmx=lson.lmx;
			}
			else
			{
				if(lson.lc==lson.rc)
				{
					root.lc=rson.lc;
					root.lmx=max(max(lson.mx,rson.lmx),max(rval[0][lson.r],rval[1][lson.r]));
				}
				else
				{
					root.lc=lson.lc;
					root.lmx=lson.lmx;
				}
				root.rc=rson.rc;
				root.rmx=rson.rmx;
			}
		}
		return root;
	} 
}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
void pushup(int o)
{
	root=lson+rson;
}
void BuildTree(int o,int l,int r)
{
	if(l==r)
	{
		root.ans=cval[l];
		root.l=root.r=l;
		root.lc=root.rc=l;
		root.mx=root.lmx=root.rmx=0;
		return;
	}
	int mid=(l+r)>>1;
	BuildTree(o<<1,l,mid);
	BuildTree(o<<1|1,mid+1,r);
	pushup(o);
}
void upd(int o,int l,int r,int pos)
{
	if(l==r)
	{
		root.ans=cval[l];
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)
		upd(o<<1,l,mid,pos);
	else
		upd(o<<1|1,mid+1,r,pos);
	pushup(o);
}
node query(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
		return root;
	int mid=(l+r)>>1;
	if(R<=mid)
		return query(o<<1,l,mid,L,R);
	if(L>mid)
		return query(o<<1|1,mid+1,r,L,R);
	return query(o<<1,l,mid,L,R)+query(o<<1|1,mid+1,r,L,R);
}
char op[10];
int main()
{
	n=read(),m=read();
	for(int i=1;i<n;++i)
		rval[0][i]=read();
	for(int i=1;i<n;++i)
		rval[1][i]=read();
	for(int i=1;i<=n;++i)
		cval[i]=read();
	BuildTree(1,1,n);
	for(int i=1;i<=m;++i)
	{
		scanf("%s",op);
		if(op[0]=='C')
		{
			int x0=read(),y0=read(),x1=read(),y1=read(),w=read();
			if(y0>y1)
			{
				swap(x0,x1);
				swap(y0,y1);
			}
			if(y0==y1)
			{
				cval[y0]=w;
				upd(1,1,n,y0);
			}	
			else if(x0==x1)
			{
				rval[x0-1][y0]=w;
				upd(1,1,n,y0);
				upd(1,1,n,y1);
			}					
		}
		else
		{
			int L=read(),R=read();
			node tmp=query(1,1,n,L,R);
			printf("%d\n",tmp.ans);
		}
	}
	return 0;
}