BZOJ 2388--旅行规划(分块&单调栈&二分)

2388: 旅行规划

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 405 Solved: 118
[Submit][Status][Discuss]

Description

OIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。

xkszltl希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而xkszltl的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl无法及时完成任务，于是找到了准备虐杀NOI2011的你，希望你能帮助他完成这个艰巨的任务。

Input

第一行给出一个整数n，接下来一行给出n的景区的初始美观度。

第三行给出一个整数m，接下来m行每行为一条指令：

1. 0 x y k：表示将x到y这段铁路边上的景区的美观度加上k；

2. 1 x y：表示有一名旅客想要在x到y这段（含x与y）中的某一站下车，你需要告诉他最大的旅行价值。

Output

对于每个询问，输出一个整数表示最大的旅行价值。

Sample Input

5
1 8 -8 3 -7
3
1 1 5
0 1 3 6
1 2 4

Sample Output

9
22

HINT

对于100%的数据，n，m≤100000。

题目链接：

　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=2388

Solution

　　　　刚开始一看这不是分块水题吗？。。。卒。。。。mdzz

　　　　然后就发现没那么简单，还要维护动态的前缀和。。。

　　　　首先肯定是要分块的。。块里的a [ i ] 表示的都是1到 i 的前缀和。。

　　　　然后对于每个块，维护还未更新的前缀fir [ i ] 和未加上的值 p [ i ] 。。

　　　　然后询问的话。。发现会很麻烦。。。。。

　　　　首先最左右两块肯定直接暴力枚举，而整块内的显然不能在枚举了。。

　　　　发现对于块内的从左到右3点 A(x1，y1)，B(x2，y2)，C(x3，y3)若满足(y3-y1)/(x3-x1)>(y2-y1)/(x2-x1)

　　　　就可以舍去B点，因为无论 fir[ i ] 怎么变B点不会成为最优点。

　　　　证明：

　　　　　　若有y3 + x3*fir [ i ] - y2 - x2*fir [ i ] >= 0 那么显然B不是最优点。

　　　　　　否则有 y3 + x3*fir [ i ] - y2 - x2*fir [ i ] < 0

　　　　　　那么说明 fir[ i ]满足 fir[ i ] < -(y3-y2) / (x3-x2)

　　　　　　那么y1+x1*fir[ i ] - y2 - x2*fir [ i ] > -(y1-y2)+(x1-x2)*( -(y3-y2) / (x3-x2) )

　　　　　　　　y1+x1*fir[ i ] - y2 - x2*fir [ i ] > ( (y2-y1)*(x3-x2)-(x1-x2)*(y3-y2) )/(x3-x2)

　　　　　　因为(y3-y1)/(x3-x1) - (y2-y1)/(x2-x1) > 0

　　　　　　而且(y3-y1)/(x3-x1) - (y2-y1)/(x2-x1) = (y2-y1)*(x3-x2)-(x1-x2)*(y3-y2)

　　　　　　所以( (y2-y1)*(x3-x2)-(x1-x2)*(y3-y2) )/(x3-x2) > 0

　　　　　　显然y1+x1*fir[ i ] - y2 - x2*fir [ i ]也大于0，B点也不是最优点

　　　　B点不是最优点得证。

　　　　所以只用单调栈维护这样一个凸包，询问时二分查找最大值即可。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#define N 100050
#define LL long long
using namespace std;
inline LL Read(){
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,Q,m,e,g[N];
LL inf=1LL<<60;
LL a[N],num[400],fir[400],p[400],q[400][400];
double slope(int x,int y){
	return (double)(a[x]-a[y])/(double)(x-y);
}
void reset(int k){
	int l=(k-1)*e+1,r=min(n,k*e),top=0;
	q[k][++top]=l;
	for(int i=l+1;i<=r;i++){
		while(top>=2 && slope(q[k][top-1],q[k][top])<slope(q[k][top-1],i)) top--;
		q[k][++top]=i;
	}
	q[k][0]=0;q[k][++top]=n+1;num[k]=top;
}
void pushdown(int k){
	int l=(k-1)*e+1,r=min(n,k*e);
	LL tmp=p[k];
	for(int i=l;i<=r;i++){
		tmp+=fir[k];a[i]+=tmp;
	}
	p[k]=fir[k]=0;
}
void update(int l,int r,LL w){
	LL tmp=0;
	if(g[l]==g[r]){
		pushdown(g[l]);
		for(int i=l;i<=r;i++) {tmp+=w;a[i]+=tmp;}
		for(int i=r+1;i<=min(g[r]*e,n);i++) a[i]+=tmp;
		for(int i=g[r]+1;i<=m;i++) p[i]+=tmp;
		reset(g[l]);return;
	}
	pushdown(g[l]);
	for(int i=l;i<=g[l]*e;i++) {tmp+=w;a[i]+=tmp;}
	reset(g[l]);
	for(int i=g[l]+1;i<g[r];i++){p[i]+=tmp;fir[i]+=w;tmp+=w*(LL)e;}
	pushdown(g[r]);
	for(int i=(g[r]-1)*e+1;i<=r;i++) {tmp+=w;a[i]+=tmp;}
	for(int i=r+1;i<=min(g[r]*e,n);i++) a[i]+=tmp;
	for(int i=g[r]+1;i<=m;i++) p[i]+=tmp;
	reset(g[r]);return;
}
LL calc(int x){
	return a[x]+p[g[x]]+fir[g[x]]*(LL)(x-(g[x]-1)*e);
}
LL get(int k){
	LL re1,re2,re3;
	int l=1,r=num[k];
	while(l<=r){
		int mid=(l+r)>>1;
		re1=calc(q[k][mid-1]);re2=calc(q[k][mid]);re3=calc(q[k][mid+1]);
		if(re1>re2 && re2>re3) r=mid;
		else if(re2>re1 && re3>re2) l=mid;
		else return re2;
	}
}
LL solve(int l,int r){
	LL re=-inf;
	if(g[l]==g[r]){
		for(int i=l;i<=r;i++) re=max(re,calc(i));
		return re;
	}
	for(int i=l;i<=g[l]*e;i++) re=max(re,calc(i));
	for(int i=(g[r]-1)*e+1;i<=r;i++) re=max(re,calc(i));
	for(int i=g[l]+1;i<g[r];i++) re=max(re,get(i));
	return re;
}
int main(){
	char ch;
	LL l,r,w;
	n=(int)Read();e=ceil(sqrt(n));
	for(int i=1;i<=n;i++) {
		a[i]=a[i-1]+Read();g[i]=(i+e-1)/e;
	}
	a[0]=a[n+1]=-inf;m=g[n];
	for(int i=1;i<=m;i++) reset(i);
	Q=Read();
	for(int i=1;i<=Q;i++){
		ch=getchar();
		while(ch!='0' && ch!='1') ch=getchar();
		if(ch=='0'){
			l=(int)Read();r=(int)Read();w=Read();
			update(l,r,w);
		}
		else {
			l=Read();r=Read();
			printf("%lld
",solve(l,r));
		}
	}
	return 0;
}

This passage is made by Iscream-2001.