【bzoj2388】旅行规划

2014年5月29日2,3854

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

Data Limit:

对于20%的数据,n,m≤3000;

对于40%的数据,n,m≤30000;

对于50%的数据,n,m≤50000;

另外20%的数据,n,m≤100000,修改操作≤20;

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

题解

桌神:论n*sqrtn*logn大法。

此题可以分块。。。

对于一块内维护一个凸壳

查询每一块内可以二分

修改头尾暴力重构,如果将一整块加上一个值,那么最优的点是不会变的,因为相当于将每两点间的斜率加上一个定值

然后就是分块写起来比较烦,不过我有善良的学长。。。

 

  • 黑暗世界2014年5月29日 下午9:43 回复

    那个也得是三分啊T_T

    #1  
  • Mektpoy2014年5月30日 上午1:46 回复

    orz各位学长

    #2  
  • Mektpoy2014年5月30日 上午1:50 回复

    话说神犇们为何不顺便写一下BZOJ3005呢 明明是一样的水题呀。。

    #3  
    • 黑暗世界2014年5月30日 上午7:43 回复

      给副队跪了,全部都是“水题”

      #31