首页 > 其他 > 详细

BZOJ2388:旅行规划(travel)——分块凸包

时间:2019-03-22 18:50:45      阅读:119      评论:0      收藏:0      [点我收藏+]

题目

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

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

【输入格式】

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

第三行给出一个整数 $m$,接下来 $m$ 行每行为一条指令:

$1.~~~0~x~y~k$:表示将 $x$ 到 $y$ 这段铁路边上的景区的美观度加上 $k$;

$2.~~~1~x~y$:表示有一名旅客想要在 $x$ 到 $y$ 这段(含 $x$ 与 $y$ )中的某一站下车,你需要告诉他最大的旅行价值。

【输出格式】

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

【样例输入】

5

1 8 -8 3 -7

3

1 1 5

0 1 3 6

1 2 4

【样例输出】

9

22

【数据范围与提示】

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

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

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

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

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

题解

无力吐槽这组孱弱的样例(过了样例还是调出了 INF 个错)

题目求得是区间最大前缀和,带区间加值操作

然后发现线段树无法在 $ O(\log n) $ 的时间内维护区间加上一次函数后的最大值

考虑分块维护最大值

记 $ sum(i) $ 表示前缀和,$ num(i) $ 表示块 $ i $ 加上的一次函数,$ d(i) $ 表示这个块需要加上的常数,

那么 $ sum(i)=num(i)\times i +d(i) $

发现最大值形如 $ y=kx+b $,然后就可以在块上维护一个凸包

当块上加一个一次函数时,凸包的点是不会改变的,那么每次加值时就只要每次重构左右两边的两个凸包即可

查询时只要在每一个块的凸包上二分即可

时间:修改时$ O(\sqrt{n}) $,查询时 $ O(\sqrt{n}) $,所以总时间 $ O(m\sqrt{n}\log n) $

代码

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define db double
 4 #define _(d) while(d(isdigit(ch=getchar())))
 5 using namespace std;
 6 int R(){
 7     int x;bool f=1;char ch;_(!)if(ch==-)f=0;x=ch^48;
 8     _()x=(x<<3)+(x<<1)+(ch^48);return f?x:-x;}
 9 const int N=1e5+5,M=1002;
10 int n,m,a[N],Sz,Mx,p[N],sz[M],tb[M][M];
11 LL w[N],num[N],f[N],d[N];
12 db getK(int i,int j){return (db)(w[i]-w[j])/(db)(i-j);}
13 void update(int x){
14     int l=(x-1)*Sz+1,r=min(x*Sz,n),tot=0;
15     p[++tot]=l;
16     for(int i=l+1;i<=r;i++){
17         while(tot>1&&getK(p[tot],p[tot-1])<getK(p[tot-1],i))
18             tot--;
19         p[++tot]=i;
20     }
21     sz[x]=tot;
22     for(int i=1;i<=tot;i++)tb[x][i]=p[i];
23     return;
24 }
25 void pushdown(int x){
26     LL o=num[x];
27     for(int i=(x-1)*Sz+1;i<=min(x*Sz,n);i++)
28         o+=d[x],w[i]+=o;
29     num[x]=d[x]=0;
30     return;
31 }
32 void change(int l,int r,int k){
33     int x=a[l],y=a[r];LL o=0;
34     pushdown(x);
35     for(int i=l;i<=min(x*Sz,r);i++)
36         o+=k,w[i]+=o;
37     update(x);
38     for(int i=x+1;i<y;i++)
39         num[i]+=o,d[i]+=k,o+=1ll*Sz*k;
40     if(x!=y){
41         pushdown(y);
42         for(int i=(y-1)*Sz+1;i<=r;i++)
43             o+=k,w[i]+=o;
44     }
45     o=(r-l+1)*k;
46     for(int i=r+1;i<=min(n,y*Sz);i++)w[i]+=o;
47     update(y);
48     for(int i=y+1;i<=Mx;i++)num[i]+=o;
49     return;
50 }
51 LL find(int i){
52     if(!i||i>n)return (LL)-2e18;
53     return (w[i]+num[a[i]]+d[a[i]]*(i-(a[i]-1)*Sz));
54 }
55 LL work(int x){
56     int l=1,r=sz[x];
57     while(l<=r){
58         int mid=(l+r)>>1;
59         LL t1=find(tb[x][mid-1]);
60         LL t2=find(tb[x][mid]);
61         LL t3=find(tb[x][mid+1]);
62         if (t1<t2 && t2<t3) l=mid+1;
63         else if (t1>t2 && t2>t3) r=mid-1;
64         else return t2;
65     }
66     return l;
67 }
68 LL query(int l,int r){
69     int x=a[l],y=a[r];LL ans=-2e18;
70     for(int i=x+1;i<y;i++)
71         ans=max(ans,work(i));
72     for(int i=l;i<=min(x*Sz,r);i++)
73         ans=max(ans,find(i));
74     if(x!=y)
75         for(int i=(y-1)*Sz+1;i<=r;i++)
76             ans=max(ans,find(i));
77     return ans;
78 }
79 int main(){
80     n=R(),Sz=sqrt(n);
81     for(int i=1;i<=n;i++)
82         w[i]=w[i-1]+R(),a[i]=(i-1)/Sz+1;
83     Mx=a[n],m=R();
84     for(int i=1;i<=Mx;i++)update(i);
85     for(int i=1;i<=m;i++){
86         int op=R(),x=R(),y=R(),k;
87         if(op==1)printf("%lld\n",query(x,y));
88         if(!op)k=R(),change(x,y,k);
89     }
90     return 0;
91 }
View Code

 

BZOJ2388:旅行规划(travel)——分块凸包

原文:https://www.cnblogs.com/chmwt/p/10579511.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!