BZOJ 3995 道路修建

发表于 | 更新于

Link

Solution

嗯。我经过一个来小时的思考，搞出来一种状态表示：在线段树的每个节点记录一个2x2的矩阵，表示a[0][1]表示左端两点不联通，右端两点联通，a[1][1]表示左端两点联通，右端两点联通，etc。画了几个图，感觉比较资磁，开始写。写了一会儿发现被一些细节边界什么的卡住了，觉得自己方法可能错了。 一看果然和标解不同。标解特别特别复杂，网上的题解也都很麻烦。于是%faebdc的AC程序（在考场上写出的程序中他的是最快的，比std快三倍orz。。）。看懂之后发现姜志豪大爷的做法跟我的想法是一样的！！ 然后发现，我是因为想用一些简单的办法算出后继状态而被自己克死的（见注释）。。。 改成正常的推法，枚举一下，就A了。。

Tips

开始写之前尽量把边界情况想出来 不要怕麻烦 用最直观的方法先实现出来，再考虑合并代码

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
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=60000+10,CON=1,DIC=0,INF=INT_MAX;
using std::swap;
using std::min;

struct iMe
{
	int v[2][2];
	int mind,sumd;
	int *operator [](int x){return v[x];}
};
/*
iMe Merge(const iMe &a,const iMe &b)
{
	iMe r=iMe(INF);
	for(int al=0;al<=1;al++)for(int ar=0;ar<=1;ar++)
		for(int bl=0;bl<=1;bl++)for(int br=0;br<=1;br++)
		{
			int temp=(ar && bl)?a.mind:a.sumd;
			int rl=al | bl,rr=ar | br;
			chkmn(r[rl][rr],a[al][ar]+b[bl][br]+temp);
		}
	return r;
}*/
iMe Merge(iMe a,iMe b)
{
	iMe r;r.mind=b.mind;r.sumd=b.sumd;
	r[1][1]=min(a[1][1]+b[1][1]+a.mind,
				a.sumd+min(a[1][0]+b[1][1],a[1][1]+b[0][1]));
	r[1][0]=min(a[1][1]+b[1][0]+a.mind,
				a.sumd+min(a[1][1]+b[0][0],a[1][0]+b[1][0]));
	r[0][1]=min(a[0][1]+b[1][1]+a.mind,
				a.sumd+min(a[0][0]+b[1][1],a[0][1]+b[0][1]));
	r[0][0]=min(a[0][1]+b[1][0]+a.mind,
				a.sumd+min(a[0][0]+b[1][0],a[0][1]+b[0][0]));
				//a.sumd+min(a[0][0]+b[0][0],
	return r;
}
struct SegmentTree
{
	struct Node
	{
		Node *son[2];
		iMe rec;
		void Fill(int);
		void up(){rec=Merge(son[0]->rec,son[1]->rec);}
	}*null,*root,*ME;int TL,TR;
	SegmentTree()
	{
		null=new Node;
		ME=new Node[MAXN<<2];
		null->son[0]=null->son[1]=null;
		root=null;
	}
	Node *newNode()
	{
		Node *cur=ME++;
		cur->son[0]=cur->son[1]=null;
		return cur;
	}
	void Build(Node *&,int,int);
	void Build(int n)
	{
		TL=1,TR=n;
		Build(root,1,n);
	}
	void Edit(Node *,int,int,int);
	void F5(int pos){Edit(root,TL,TR,pos);}
	iMe Access(Node*,int,int,int,int);
	iMe Access(int L,int R){return Access(root,TL,TR,L,R);}
}Tree;
int tor[3][MAXN],tod[MAXN];
void SegmentTree::Node::Fill(int pos)
{
	rec.mind=min(tor[1][pos],tor[2][pos]);
	rec.sumd=tor[1][pos]+tor[2][pos];
	rec[0][0]=rec[0][1]=rec[1][0]=0;
	rec[1][1]=tod[pos];
}
void SegmentTree::Build(Node *&pos,int L,int R)
{
	pos=newNode();
	if(L==R)
		pos->Fill(L);
	else
	{
		int MID=(L+R)>>1;
		Build(pos->son[0],L,MID);
		Build(pos->son[1],MID+1,R);
		pos->up();
	}
}
void SegmentTree::Edit(Node *pos,int L,int R,int goal)
{
	if(L==R)
		pos->Fill(L);
	else
	{
		int MID=(L+R)>>1;
		if(goal<=MID)
			Edit(pos->son[0],L,MID,goal);
		else
			Edit(pos->son[1],MID+1,R,goal);
		pos->up();
	}
}
iMe SegmentTree::Access(Node *pos,int L,int R,int l,int r)
{
	if(L==l && R==r) return pos->rec;
	else
	{
		int MID=(L+R)>>1;
		if(r<=MID) return Access(pos->son[0],L,MID,l,r);
		else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
		else return Merge(Access(pos->son[0],L,MID,l,MID),Access(pos->son[1],MID+1,R,MID+1,r));
	}
}
int main()
{
	//freopen("input","r",stdin);
	int n,m;get(n),get(m);
	for(int i=1;i<=n-1;i++) get(tor[1][i]);
	for(int i=1;i<=n-1;i++) get(tor[2][i]);
	for(int i=1;i<=n;i++) get(tod[i]);
	Tree.Build(n);
	for(int i=1;i<=m;i++)
	{
		char opt;int x0,y0,x1,y1,w,L,R;
		while(!isalpha(opt=getchar()));
		if(opt=='Q')
		{
			get(L),get(R);
			printf("%d\n",Tree.Access(L,R)[1][1]);
		}
		else
		{
			get(x0),get(y0),get(x1),get(y1),get(w);
			if(x0>x1 || (x0==x1 && y0>y1)) swap(x0,x1),swap(y0,y1);
			if(x0+1==x1) tod[y0]=w;
			else tor[x0][y0]=w;
			Tree.F5(y0);
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */