bzoj 3995 [SDOI2015]道路修建
内容
真沉静呵
Description
某国有2N个城市，这2N个城市构成了一个2行N列的方格网。现在该国政府有一个旅游发展计划，这个计划需要选定L、R两列(L<=R)，修建若干条专用道路，使得这两列之间（包括这两列）的所有2(R-L+1)个城市中每个城市可以只通过专用道路就可以到达这2(R-L+1)个城市中的任何一个城市。这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用。由于该国政府决定尽量缩减开支，因此政府决定，选定L、R后，只修建2(R-L+1)-1条专用道路，使得这些专用道路构成一个树结构。现在你需要帮助该国政府写一个程序，完成这个任务。具体地，该任务包含M个操作，每个操作的格式如下：
1. C x0 y0 x1 y1 w：由于重新对第x0行第y0列的城市和第x1行第y1列的城市之间的情况进行了考察，它们之间修建一条专用道路的花费变成了w；
2. Q L R：若政府选定的两列分别为L、R，询问政府的最小开支。
Input
第一行，两个整数N、M。
第二行，N-1个整数，其中第i个整数表示初始时第1行第i列的城市和第1行第i+1列的城市之间修建一条专用道路的费用。
第三行，N-1个整数，其中第i个整数表示初始时第2行第i列的城市和第2行第i+1列的城市之间修建一条专用道路的费用。
第四行，N个整数，其中第i个整数表示初始时第1行第i列的城市和第2行第i列的城市之间修建一条专用道路的费用。
接下来的M行，每行一个操作。
Output
对于每个询问操作，输出一行，表示你计算出的政府的最小开支。
Sample Input
3 3
1 2
2 1
3 1 2
Q 1 3
C 1 2 2 2 3
Q 2 3
Sample Output
7
5
HINT
对于全部的数据，1<=N, M<=60000，任何时刻任何一条专用道路的修建费用不超过10^4。
Source
Round 1
题解
写了一下午，我真是舒(sha)爽(bi)啊。
一眼的感觉是LCT，但是好像并写不了。那就是应该用线段树来维护MST。
考虑合并的时候，一般的线段树要考虑两个区间之间连边。发现好麻烦，换种思路。
我们合并的时候两个区间中间会有一列点的交集。这样发现连完后会成一个环。
这样就可以在这个环上断边。
这样我们就要记这几个值：
最左边的竖线位置
最右边的竖线位置
横线的最大值
左端点到最左边竖线中横线最大值
右端点到最右边竖线中横线最大值
答案
要断边的时候先找这两个区间的横线最大值和左右竖线的最大值。横线直接减掉就可以了。
竖线的话还要考虑这个左/右区间只有一条竖线的情况。还要更新一些东西。。
这就是$update$写法。。
单点更新就直接暴力改，一路$update$下去。
然后还有一个问题就是$query$。
本来想用单纯的线段树来搞搞，结果发现这个线段树已经没有树样了。
然后就yy出了一个诡异的$query$方法。不是返回答案，返回答案所在区间的地址。
那假如不是恰好在区间中呢？
暴力$update$！提出两个点，放在一个新申请的地址中(内存池)，暴力$update$，再把这个地址传给下面。
想到这里好像用结构体比较方便一些。但是懒得重构。（flag
30min码完后，开始莫名的wa。开始对拍，3h没错。
静下心想一下，我的新申请的地址是从后往前用内存池，线段树是从前往后用内存池。好像会吞掉！
数据范围加了个0就a了。。
一开始wa了就没往内存方面想，对拍范围还开小了。活该啊。
#include <cstdio>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid,r
#define N 1000050
#define Maxn 1000010
using namespace std;
int lpos[N],rpos[N],mx[N],lmx[N],rmx[N],ans[N];
int v[N/10],v1[N/10],v2[N/10];
int n,m,l,r,x1,x2,y1,y2,w;
int num=0;
void debug()
{
int n=20;
for (int i=1;i<=n;i++)
printf("%d:l %d,r %d,lmx %d,rmx %d,mx %d,ans %d\n",i,lpos[i],rpos[i],lmx[i],rmx[i],mx[i],ans[i]);
}
void update(int rt,int lrt,int rrt)
{
mx[rt]=max(mx[lrt],mx[rrt]);
ans[rt]=ans[lrt]+ans[rrt];
lpos[rt]=lpos[lrt],rpos[rt]=rpos[rrt];
lmx[rt]=lmx[lrt],rmx[rt]=rmx[rrt];
int maxs=max(rmx[lrt],lmx[rrt]);
if (maxs>=max(v[rpos[lrt]],v[lpos[rrt]]))
ans[rt]-=maxs;
else if (v[rpos[lrt]]>v[lpos[rrt]])
{
ans[rt]-=v[rpos[lrt]];
if (lpos[lrt]==rpos[lrt])
lpos[rt]=lpos[rrt],lmx[rt]=max(mx[lrt],lmx[rrt]);
}
else
{
ans[rt]-=v[lpos[rrt]];
if (lpos[rrt]==rpos[rrt])
rpos[rt]=rpos[lrt],rmx[rt]=max(mx[rrt],rmx[lrt]);
}
}
void update_two(int rt,int l,int r)
{
mx[rt]=max(v1[l],v2[l]);
if (mx[rt]>=max(v[l],v[r]))
lpos[rt]=l,rpos[rt]=r,lmx[rt]=rmx[rt]=0,ans[rt]=v1[l]+v2[l]+v[l]+v[r]-mx[rt];
else if (v[l]>v[r])
lpos[rt]=rpos[rt]=r,lmx[rt]=mx[rt],rmx[rt]=0,ans[rt]=v1[l]+v2[l]+v[r];
else
lpos[rt]=rpos[rt]=l,rmx[rt]=mx[rt],lmx[rt]=0,ans[rt]=v1[l]+v2[l]+v[l];
}
void build(int rt,int l,int r)
{
if (l+1==r)
update_two(rt,l,r);
else
{
int mid=l+r>>1;
build(lson);
build(rson);
update(rt,rt<<1,rt<<1|1);
}
}
void copyseg(int x,int y)
{
lpos[y]=lpos[x],rpos[y]=rpos[x],lmx[y]=lmx[x],rmx[y]=rmx[x],ans[y]=ans[x],mx[y]=mx[x];
}
int query(int rt,int l,int r,int L,int R)
{
if (l==L && r==R)
return rt;
int mid=l+r>>1;
if (R<=mid) return query(lson,L,R);
else if (L>=mid) return query(rson,L,R);
else
{
int a=query(lson,L,mid),b=query(rson,mid,R);
num+=2;
copyseg(a,Maxn-2-num),copyseg(b,Maxn-1-num);
update(Maxn-num,Maxn-2-num,Maxn-1-num);
return Maxn-num;
}
}
void change(int rt,int l,int r,int L,int R)
{
if (L>R) return;
if (l+1==r)
update_two(rt,l,r);
else
{
int mid=l+r>>1;
change(lson,L,min(mid,R));
change(rson,max(L,mid),R);
update(rt,rt<<1,rt<<1|1);
}
}
main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++)
scanf("%d",&v1[i]);
for (int i=1;i<n;i++)
scanf("%d",&v2[i]);
for (int i=1;i<=n;i++)
scanf("%d",&v[i]);
build(1,1,n);
for (int i=1;i<=m;i++)
{
char com[10];
scanf("%s",com);
if (com[0]=='Q')
{
scanf("%d%d",&l,&r);
if (l==r)
printf("%d\n",v[l]);
else
printf("%d\n",ans[query(1,1,n,l,r)]);
}
else
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&w);
if (x1>x2) swap(x1,x2);
if (y1>y2) swap(y1,y2);
if (x1==x2)
if (x1==1) v1[y1]=w;
else v2[y1]=w;
else
v[y2]=w;
change(1,1,n,y1,y2);
}
// debug();
}
}
生成器
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <sstream>
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;
stringstream ss;
int main(int a1,char *a2[])
{
int seed=time(0);
if (a1)
{
ss.clear();
ss<<a2[1];
ss>>seed;
}
srand(seed);
int n=random(5,10),m=random(5,8);
printf("%d %d\n",n,m);
for (int i=1;i<n;i++)
printf("%d ",random(1,10));
puts("");
for (int i=1;i<n;i++)
printf("%d ",random(1,10));
puts("");
for (int i=1;i<=n;i++)
printf("%d ",random(1,10));
puts("");
for (int i=1;i<=m;i++)
{
int p=random(0,1);
if (p)
{
int x=random(1,n-1),y=random(x,n);
printf("Q %d %d\n",x,y);
}
else
{
int x1=random(1,2),x2=random(1,2),y1,y2;
if (x1==x2) y1=random(1,n),y2=y1+1;
else y1=y2=random(1,n);
printf("C %d %d %d %d %d\n",x1,y1,x2,y2,random(1,10));
}
}
}