题意
有n个村庄排成一排，有n-1条路将他们连在一起。每条路开放一天都会花费一定数量的钱。你可以选择打开或者关上任意条路在任意一天，但是每条路只能打开和关闭一次。我们知道m天的运输计划。每天都有一辆马车从村庄ai到存在bi。你需要保证从ai到bi的路在第i天全部打开。如果要使花费最少，每天的花费应该是多少？n,m<=200000。
分析
这个题应该有各种各样的做法吧。
注意到，每条路只能打开和关上一次，我们可以很容易想到一个朴素的算法。
记录下每条路最后一次用到的是哪一天。然后每一天如果需要的路是关闭的就打开它，如果这一天是某条路最后一次用，那么就关闭掉它。
但是呢，暴力肯定是会超时的。我们发现，这n-1条路排成一排，而且每天的运输集合也是连续的一些路。我们把这些看作区间的话，就可以很容易的想到用线段树来维护。
我这个题是用了两个线段树。
第一棵线段树用来维护每一条路最后一次使用是哪一天。
第二棵线段树用来维护当前开着的道路的花费总和。
因为每条路只能打开和关闭一次，所以第二棵线段树的更新不需要打延时标记。
每次查询的结果是当前的sumv[1]
哇这样说好像说不明白哇。直接上代码好了···
对了，我调了很久还是wa，最后发现，输入的时候要判断l,r的顺序，如果l>r的话需要swap(l,r)
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <set> 6 #include <vector> 7 8 using namespace std; 9 const int maxn=200000+10; 10 vector<int>days[maxn]; 11 struct Node{ 12 int l,r; 13 }a[maxn]; 14 int n,m; 15 long long w[maxn]; 16 long long sumv[4*maxn],numv[4*maxn]; 17 int ql,qr; 18 void update(int o,int L,int R){ 19 if(numv[o]==R-L+1) 20 return; 21 if(L==R){ 22 sumv[o]=w[L]; 23 numv[o]=1; 24 return; 25 } 26 int M=L+(R-L)/2; 27 if(ql<=M) 28 update(2*o,L,M); 29 if(qr>M) 30 update(2*o+1,M+1,R); 31 sumv[o]=sumv[2*o]+sumv[2*o+1]; 32 numv[o]=numv[2*o]+numv[2*o+1]; 33 return; 34 } 35 int v; 36 void update2(int o,int L,int R){ 37 if(L==R){ 38 sumv[o]=0; 39 numv[o]=0; 40 return; 41 } 42 int M=L+(R-L)/2; 43 if(v<=M) 44 update2(2*o,L,M); 45 else 46 update2(2*o+1,M+1,R); 47 sumv[o]=sumv[2*o]+sumv[2*o+1]; 48 numv[o]=numv[2*o]+numv[2*o+1]; 49 return; 50 } 51 int setv[4*maxn]; 52 void update3(int o,int L,int R){ 53 if(ql<=L&&qr>=R){ 54 setv[o]=v; 55 return; 56 } 57 if(setv[o]){ 58 setv[2*o]=setv[o]; 59 setv[2*o+1]=setv[o]; 60 setv[o]=0; 61 } 62 int M=L+(R-L)/2; 63 if(ql<=M) 64 update3(2*o,L,M); 65 if(qr>M) 66 update3(2*o+1,M+1,R); 67 return; 68 } 69 int query(int o,int L,int R){ 70 if(setv[o])return setv[o]; 71 if(L==R) 72 return 0; 73 int M=L+(R-L)/2; 74 if(v<=M) 75 return query(2*o,L,M); 76 else 77 return query(2*o+1,M+1,R); 78 } 79 int main(){ 80 while(scanf("%d%d",&n,&m)!=EOF){ 81 for(int i=1;i<=m;i++)days[i].clear(); 82 for(int i=1;i<n;i++) 83 scanf("%lld",&w[i]); 84 for(int i=1;i<=m;i++){ 85 scanf("%d%d",&a[i].l,&a[i].r); 86 if(a[i].r<a[i].l) 87 swap(a[i].r,a[i].l); 88 89 a[i].r--; 90 } 91 memset(setv,0,sizeof(setv)); 92 memset(sumv,0,sizeof(sumv)); 93 memset(numv,0,sizeof(numv)); 94 for(int i=1;i<=m;i++){ 95 ql=a[i].l,qr=a[i].r,v=i; 96 update3(1,1,n-1); 97 } 98 for(int i=1;i<n;i++){ 99 v=i; 100 int res=query(1,1,n-1); 101 days[res].push_back(i); 102 } 103 for(int i=1;i<=m;i++){ 104 ql=a[i].l,qr=a[i].r; 105 update(1,1,n-1); 106 printf("%lld ",sumv[1]); 107 for(int j=0;j<days[i].size();j++){ 108 v=days[i][j]; 109 update2(1,1,n-1); 110 } 111 } 112 } 113 return 0; 114 }