大家好，又见面了，我是你们的朋友全栈君。
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
1 2
2 1
3 1 2
Q 1 3
C 1 2 2 2 3
Q 2 3
Sample Output
7
5
5
HINT
对于全部的数据，1<=N, M<=60000，任何时刻任何一条专用道路的修建费用不超过10^4。
Solution
这个题真的非常恶心啊……
首先这个题一看就是线段树= =……因为想了想别的好像做不了
就上线段树然后强行讨论过了样例，结果0分
拍了一下发现我讨论的好像并不全= =……
后来我看到一篇和我一样强行讨论的题解，
才发现我讨论的有点少QAQ
https://www.cnblogs.com/maijing/p/4832745.html
上面博客里那位大爷讨论的挺详细的
不过我写的比他短将近一半
Code
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define N (70000+100) 5 using namespace std; 6 7 struct node{ int X[6];}Segt[N<<2]; 8 int n,m,a[N],L[3][N]; 9 int Form[20][5]= 10 { 11 { 1,1,1},{ 1,2,2},{ 1,3,3}, 12 { 1,4,4},{ 1,5,5},{ 2,1,2}, 13 { 2,3,2},{ 2,5,4},{ 3,1,3}, 14 { 3,3,3},{ 3,5,5},{ 4,1,4}, 15 { 4,2,2},{ 4,4,4},{ 5,1,5}, 16 { 5,2,3},{ 5,4,5}, 17 }; 18 19 node operator + (node x,node y) 20 { 21 node z; 22 memset(z.X,0x3f,sizeof(z)); 23 for (int i=0; i<=16; ++i) 24 z.X[Form[i][2]]=min(z.X[Form[i][2]],x.X[Form[i][0]]+y.X[Form[i][1]]); 25 return z; 26 } 27 28 node calc(int s) 29 { 30 node ans; 31 ans.X[1]=L[1][s]+L[2][s]; 32 ans.X[2]=L[1][s]+L[2][s]+a[s]+a[s+1]-max(max(L[1][s],L[2][s]),max(a[s],a[s+1])); 33 ans.X[3]=a[s+1]+min(L[1][s],L[2][s]); 34 ans.X[4]=a[s]+min(L[1][s],L[2][s]); 35 ans.X[5]=min(L[1][s],L[2][s]); 36 return ans; 37 } 38 39 void Build(int now,int l,int r) 40 { 41 if (l==r) 42 { 43 Segt[now]=calc(l); 44 return; 45 } 46 int mid=(l+r)>>1; 47 Build(now<<1,l,mid); 48 Build(now<<1|1,mid+1,r); 49 Segt[now]=Segt[now<<1]+Segt[now<<1|1]; 50 } 51 52 node Query(int now,int l,int r,int l1,int r1) 53 { 54 if (l1<=l && r<=r1) 55 return Segt[now]; 56 int mid=(l+r)>>1; 57 if (r1<=mid) return Query(now<<1,l,mid,l1,r1); 58 if (l1>=mid+1) return Query(now<<1|1,mid+1,r,l1,r1); 59 return Query(now<<1,l,mid,l1,r1)+Query(now<<1|1,mid+1,r,l1,r1); 60 } 61 62 void Update(int now,int l,int r,int x) 63 { 64 if (l==r) 65 { 66 Segt[now]=calc(l); 67 return; 68 } 69 int mid=(l+r)>>1; 70 if (x<=mid) Update(now<<1,l,mid,x); 71 if (x>mid) Update(now<<1|1,mid+1,r,x); 72 Segt[now]=Segt[now<<1]+Segt[now<<1|1]; 73 } 74 75 int main() 76 { 77 scanf("%d%d",&n,&m); 78 for (int i=1; i<=n-1; ++i) scanf("%d",&L[1][i]); 79 for (int i=1; i<=n-1; ++i) scanf("%d",&L[2][i]); 80 for (int i=1; i<=n; ++i) scanf("%d",&a[i]); 81 82 Build(1,1,n-1); 83 for (int i=1; i<=m; ++i) 84 { 85 char opt[2]; int x0,y0,x1,y1,k; 86 scanf("%s",opt); 87 if (opt[0]=='Q') 88 { 89 scanf("%d%d",&x0,&y0); 90 if (x0==y0) printf("%d\n",a[x0]); 91 else printf("%d\n",Query(1,1,n-1,x0,y0-1).X[2]); 92 } 93 if (opt[0]=='C') 94 { 95 scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&k); 96 if (y0==y1) 97 { 98 a[y0]=k; 99 if (y0!=1) Update(1,1,n-1,y0-1); 100 if (y0!=n) Update(1,1,n-1,y0); 101 } 102 else 103 { 104 L[x0][min(y0,y1)]=k; 105 Update(1,1,n-1,min(y0,y1)); 106 } 107 } 108 } 109 }
转载于:https://www.cnblogs.com/refun/p/8888092.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107568.html原文链接：https://javaforall.net
