2016 Multi-University Training Contest 10 [HDU 5861] Road （线段树：区间覆盖+单点最大小）...

HDU 5861

题意

在n个村庄之间存在n-1段路，令某段路开放一天需要交纳wi的费用，但是每段路只能开放一次，一旦关闭将不再开放。现在给你接下来m天内的计划，在第i天，需要对村庄ai到村庄bi的道路进行开放。在满足m天内花费最小的情况下，求出每天的花销。

 

分析：

我们可以想到用线段树想到记录每一段路的开始时间与结束时间，开始时间很简单，就是一开始的时间，结束的时间求法可以参考区间覆盖，这是类似的；

然后我们在转化哪一天开哪些，哪一天关哪些，那这天的贡献sum = 开-关 ;

 

这很关键，我在比赛就没有想出来。。   

例：如st[1]=3，表示第1段道路的最早开始时间是第3天，那么你可以start[3].push_back(1)，表示第3天开启第1段道路，这样扫一遍过去就行了；

这是一种，要不就用d[be[i]]+=w[i] , d[en[i]]-=w[i];  其实差不多

 

#include<bits/stdc++.h>using namespace std ; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn = 200020; int Begin[maxn << 2], End[maxn << 2]; int be[maxn],en[maxn],w[maxn]; long long sum[maxn],d[maxn]; void pushdown(int rt)//向下跟新 {if(!Begin[rt<<1])Begin[rt<<1]=Begin[rt];if(!Begin[rt<<1|1])Begin[rt<<1|1]=Begin[rt];if(!End[rt])return ;End[rt<<1]=End[rt<<1|1]=End[rt];End[rt]=0;///优化用过了就可以不用了 } void build(int l , int r , int rt) {Begin[rt]=End[rt]=0;if(l==r)return ;int m = (l+r) >> 1 ;build(lson);build(rson); }void update(int L , int R , int k , int l , int r , int rt) {if(L<=l && r<=R){if(!Begin[rt])///很简单的道理,我跟新过了就不跟新了;Begin[rt]=k;End[rt]=k;return ;}pushdown(rt);int m=(l+r) >> 1;if(m>=L)update(L,R,k,lson);if(m<R)update(L,R,k,rson); } void pushall(int l , int r , int rt) {if(l==r){be[l]=Begin[rt],en[l]=End[rt];return ;}pushdown(rt);int m=(l+r)>>1;pushall(lson);pushall(rson); } int main() {int n,m;while(~scanf("%d%d",&n,&m)){n--;build(1,n,1);///建树for(int i=1 ; i<=n ; i++)scanf("%d",&w[i]);for(int i=1 ; i<=m ; i++){int u,v;scanf("%d%d",&u,&v);if(u>v)//防止意外 swap(u,v);update(u,v-1,i,1,n,1);///u到v区间更新为i(天); }pushall(1,n,1);//找到每一段路的开始时间与结束时间memset(d,0,sizeof(d));for(int i=1 ; i<=n ; i++)//每一段路的开始费用与结束费用 {if(be[i]){d[be[i]]+=w[i];d[en[i]+1]-=w[i];}}sum[0]=0;for(int i=1 ; i<=m ; i++)///类似与扫描线，一天一天的扫过去 {sum[i]=sum[i-1]+d[i];printf("%lld\n",sum[i]);}} } View Code

 

线段树真厉害，以后就不要只是固定与模板，要与线段树的结构与自己需要用的功能结合

转载于:https://www.cnblogs.com/shuaihui520/p/9795013.html

总结

以上是生活随笔为你收集整理的2016 Multi-University Training Contest 10 [HDU 5861] Road （线段树：区间覆盖+单点最大小）...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。