题目链接:

http://acm.split.hdu.edu.cn/showproblem.php?pid=5861

Road

Time Limit: 12000/6000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

问题描述

输入

输出

样例

题意

题解

代码

这里用的是一种不需要打懒惰标记的方法,并且由于是单点查询,所以只需要往下更新,不用回溯回来。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++) typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII; const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0); //start---------------------------------------------------------------------- const int maxn=2e5+10; int road[maxn]; //这里maxv,minv是一颗线段树,sumv是另一颗线段树,偷懒写在一起了
int maxv[maxn<<2],minv[maxn<<2];
int sumv[maxn<<2]; int ql,qr,_v,_v2;
void update(int o,int l,int r,int type) {
if(ql<=l&&r<=qr) {
if(type==-1) {
maxv[o]=max(maxv[o],_v);
minv[o]=min(minv[o],_v);
} else {
sumv[o]+=_v2;
}
} else {
if(ql<=mid) update(lson,l,mid,type);
if(qr>mid) update(rson,mid+1,r,type);
} } int _p,_ma,_mi,_sum;
void query(int o,int l,int r,int add,int ma,int mi) {
if(l==r) {
_ma=max(ma,maxv[o]);
_mi=min(mi,minv[o]);
_sum=add+sumv[o];
} else {
if(_p<=mid) query(lson,l,mid,add+sumv[o],max(ma,maxv[o]),min(mi,minv[o]));
else query(rson,mid+1,r,add+sumv[o],max(ma,maxv[o]),min(mi,minv[o]));
}
} void init() {
clr(sumv,0);
clr(maxv,-1);
clr(minv,0x3f);
} int main() {
int n,m;
while(scanf("%d%d",&n,&m)==2&&n) {
init();
for(int i=1; i<=n-1; i++) scanf("%d",&road[i]); ///求每条路开放的最早和最迟时间
for(int i=1; i<=m; i++) {
int u,v;
scanf("%d%d",&u,&v);
if(u>v) swap(u,v);
v--;
ql=u,qr=v,_v=i;
update(1,1,n-1,-1);
}
for(int i=1; i<=n-1; i++) {
_p=i,_ma=-1,_mi=INF;
query(1,1,n-1,0,_ma,_mi);
// printf("%d,%d\n",_mi,_ma);
if(_mi>_ma) continue;
ql=_mi,qr=_ma,_v2=road[i];
update(1,1,m,1);
} ///求每天的花费是多少
for(int i=1; i<=m; i++) {
_p=i,_sum=0;
query(1,1,m,0,_ma,_mi);
printf("%d\n",_sum);
}
}
return 0;
} //end-----------------------------------------------------------------------
05-11 09:43
查看更多