BZOJ3995:[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。

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 }