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
",sum[i]);
}
}
}
线段树真厉害，以后就不要只是固定与模板，要与线段树的结构与自己需要用的功能结合