首页 > 代码库 > 有趣的凸壳问题~
有趣的凸壳问题~
PART I BZOJ 1249
1249: SGU277 HERO 动态凸包
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 406 Solved: 123
[Submit][Status]Description
平面上最开始只包含3个点，然后还会依次出现N个点。每新增一个点，请你求出包含这些点的周长最小的多边形的面积（也就是凸包的面积）。Input
第一行为6个整数，表示最初的三个点的坐标(x1,y1),(x2,y2),(x3,y3)。 第二行仅一个数N。 以下N行，每行两个整数(xi,yi)，表示新增的点的坐标。Output
对于每次新增点的操作，请你输出新增完此点后当前的凸包的面积的两倍。Sample Input
0 0 0 2 2 0
3
2 2
1 1
2 4Sample Output
8
8
12HINT
N<=100000
点的坐标巨大,目测在[-10^9,10^9]
支持插入操作的凸包。每次插入以后求出凸包面积。
还记得Graham水平扫描法吗？我们分别维护上凸壳和下凸壳，同时更新面积。
假如维护上凸壳，新增点P(X,Y)，找到相邻两点使得Xi<X<Xj，当且仅当向量P→Pj 在Pi→P的顺时针方向，点P插在凸壳上。
顺时针<==>cross(PiP,PPj)<0，叉积就点到为止。
若插入，向左维护向右维护。
下凸壳反之。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#include<set>#define MAXN 100010using namespace std;typedef long long LL;LL n,area,sum; struct point{ LL x,y; bool operator<(const point&b)const{ return (x<b.x||x==b.x&&y<b.y); } point operator-(const point&b)const{ return (point){x-b.x,y-b.y}; }};typedef point vector;set<point>U,D;set<point>::iterator l,r,it; LL sqr(LL x){return x*x;} LL cross(vector a,vector b){ return a.x*b.y-b.x*a.y;} void maintain_U(point p){ it=U.lower_bound(p); if(it==U.begin()){ r=it;it++; while(it!=U.end()){ if(cross(*r-p,*it-p)<0) break; sum+=cross(*r,*it); U.erase(r);r=it;it++; } sum-=cross(p,*r); U.insert(p); }else if(it==U.end()){ it--;l=it; while(it!=U.begin()){ it--;if(cross(*l-*it,p-*it)<0) break; sum+=cross(*it,*l); U.erase(l);l=it; } sum-=cross(*l,p); U.insert(p); }else{ r=it;it--;l=it; if(cross(p-*l,*r-*l)<0){ sum+=cross(*l,*r); while(it!=U.begin()){ it--;if(cross(*l-*it,p-*it)<0) break; sum+=cross(*it,*l); U.erase(l);l=it; } sum-=cross(*l,p); it=r;it++; while(it!=U.end()){ if(cross(*r-p,*it-p)<0) break; sum+=cross(*r,*it); U.erase(r);r=it;it++; } sum-=cross(p,*r); U.insert(p); } }} void maintain_D(point p){ it=D.lower_bound(p); if(it==D.begin()){ r=it;it++; while(it!=D.end()){ if(cross(*r-p,*it-p)>0) break; sum-=cross(*r,*it); D.erase(r);r=it;it++; } sum+=cross(p,*r); D.insert(p); }else if(it==D.end()){ it--;l=it; while(it!=D.begin()){ it--;if(cross(*l-*it,p-*it)>0) break; sum-=cross(*it,*l); D.erase(l);l=it; } sum+=cross(*l,p); D.insert(p); }else{ r=it;it--;l=it; if(cross(p-*l,*r-*l)>0){ sum-=cross(*l,*r); while(it!=D.begin()){ it--;if(cross(*l-*it,p-*it)>0) break; sum-=cross(*it,*l); D.erase(l);l=it; } sum+=cross(*l,p); it=r;it++; while(it!=D.end()){ if(cross(*r-p,*it-p)>0) break; sum-=cross(*r,*it); D.erase(r);r=it;it++; } sum+=cross(p,*r); D.insert(p); } }} int main(){ //freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); point p1,p2,p3,p; scanf("%lld%lld%lld%lld%lld%lld",&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y); if(p2<p1) swap(p1,p2); if(p3<p1) swap(p1,p3); if(p3<p2) swap(p2,p3); U.insert(p1);D.insert(p1); U.insert(p3);D.insert(p3); area=cross(p2-p1,p3-p1); if(area<0) U.insert(p2),sum-=area; if(area>0) D.insert(p2),sum+=area; scanf("%d",&n); while(n--){ scanf("%lld%lld",&p.x,&p.y); maintain_U(p); maintain_D(p); printf("%lld\n",sum); } return 0;}
PART II BZOJ 2300
2300: [HAOI2011]防线修建
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 394 Solved: 191
[Submit][Status]Description
近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：
1. 给出你所有的A国城市坐标
2. A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了
3. A国上层询问对于剩下要保护的城市，修建防线的总经费最少是多少
你需要对每次询问作出回答。注意单位1长度的防线花费为1。
A国的地形是这样的，形如下图，x轴是一条河流，相当于一条天然防线，不需要你再修建
A国总是有两个城市在河边，一个点是(0,0)，一个点是(n,0)，其余所有点的横坐标均大于0小于n，纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。
上图中，A,B,C,D,E点为A国城市，且目前都要保护，那么修建的防线就会是A-B-C-D，花费也就是线段AB的长度+线段BC的长度+线段CD的长度
如果，这个时候撤销B点的保护，那么防线变成下图
Input
第一行，三个整数n,x,y分别表示河边城市和首都是(0,0)，(n,0)，(x,y)。
第二行，一个整数m。
接下来m行，每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。
再接下来一个整数q，表示修改和询问总数。
接下来q行每行要么形如1 i，要么形如2，分别表示撤销第i个城市的保护和询问。
Output
对于每个询问输出1行，一个实数v，表示修建防线的花费，保留两位小数
Sample Input
4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2
Sample Output
6.47
5.84
4.47HINT
数据范围：
30%的数据m<=1000,q<=1000
100%的数据m<=100000,q<=200000,n>1
所有点的坐标范围均在10000以内, 数据保证没有重点
支持删除操作的凸包。求出每次删除以后的凸包周长。没有强制在线。
做法很显然，离线，从后往前逐个插入。维护上凸壳即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<set> 8 #define MAXN 200010 9 using namespace std; 10 double sum; 11 int op[MAXN],t[MAXN],vis[MAXN];double ans[MAXN]; 12 13 struct point{ 14 int x,y; 15 bool operator<(const point&b)const{ 16 return (x<b.x||x==b.x&&y<b.y); 17 } 18 point operator-(const point&b)const{ 19 return (point){x-b.x,y-b.y}; 20 } 21 }p[MAXN]; 22 typedef point vector; 23 set<point>U; 24 set<point>::iterator l,r,it; 25 26 double sqr(double x){return x*x;} 27 double dist(point a,point b){ 28 return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); 29 } 30 int cross(vector a,vector b){ 31 return a.x*b.y-b.x*a.y; 32 } 33 34 void maintain_U(point p){ 35 it=U.lower_bound(p); 36 if(it==U.begin()){ 37 r=it;it++; 38 while(it!=U.end()){ 39 if(cross(*r-p,*it-p)<0) break; 40 sum-=dist(*r,*it); 41 U.erase(r);r=it;it++; 42 } 43 sum+=dist(p,*r); 44 U.insert(p); 45 }else if(it==U.end()){ 46 it--;l=it; 47 while(it!=U.begin()){ 48 it--;if(cross(*l-*it,p-*it)<0) break; 49 sum-=dist(*it,*l); 50 U.erase(l);l=it; 51 } 52 sum+=dist(*l,p); 53 U.insert(p); 54 }else{ 55 r=it;it--;l=it; 56 if(cross(p-*l,*r-*l)<0){ 57 sum-=dist(*l,*r); 58 59 while(it!=U.begin()){ 60 it--;if(cross(*l-*it,p-*it)<0) break; 61 sum-=dist(*it,*l); 62 U.erase(l);l=it; 63 } 64 sum+=dist(*l,p); 65 66 it=r;it++; 67 while(it!=U.end()){ 68 if(cross(*r-p,*it-p)<0) break; 69 sum-=dist(*r,*it); 70 U.erase(r);r=it;it++; 71 } 72 sum+=dist(p,*r); 73 U.insert(p); 74 } 75 } 76 } 77 78 int main(){ 79 freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); 80 int n,m,q,x,y; 81 scanf("%d%d%d",&n,&x,&y); 82 point A={0,0},B={n,0},C={x,y}; 83 U.insert(A);U.insert(B);U.insert(C); 84 sum=dist(A,C)+dist(B,C); 85 86 scanf("%d",&m); 87 for(int i=1;i<=m;i++) scanf("%d%d",&p[i].x,&p[i].y); 88 89 memset(vis,0,sizeof(vis)); 90 scanf("%d",&q); 91 for(int i=1;i<=q;i++){ 92 scanf("%d",&op[i]); 93 if(op[i]==1){ 94 scanf("%d",&t[i]); 95 vis[t[i]]=1; 96 } 97 } 98 99 for(int i=1;i<=m;i++) if(!vis[i]) maintain_U(p[i]);100 for(int i=q;i>=1;i--)101 if(op[i]==1)102 maintain_U(p[t[i]]);103 else104 ans[i]=sum;105 for(int i=1;i<=q;i++)106 if(op[i]==2)107 printf("%.2lf\n",ans[i]); 108 return 0;109 }
PART III（简单应用） BZOJ 1492
1492: [NOI2007]货币兑换Cash
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1542 Solved: 719
[Submit][Status]Description
Input
第一行两个正整数N、S，分别表示小Y 能预知的天数以及初始时拥有的钱数。 接下来N 行，第K 行三个实数AK、BK、RateK，意义如题目中所述Output
只有一个实数MaxProfit，表示第N 天的操作结束时能够获得的最大的金钱 数目。答案保留3 位小数。Sample Input
3 100
1 1 1
1 2 2
2 2 3Sample Output
225.000HINT
测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 1 000；
对于100%的测试数据，满足N ≤ 100 000；
简要做法：
令F[i]表示第i天获得的最大B卷数量。
枚举上一次交易日j
F[i]=max{ans,Rate[j]*F[j]*A[i]+F[j]*B[i]}/(rate[i]*a[i]+b[i])
O(n^2)
观察括号内的表达式，可以发现决策J优于决策K的条件：(rate[j]*f[j]-rate[k]*f[k])/(f[j]-f[k])>-b[i]/a[i]
上面这个式子的左边，一般记成slope(j,k)
Slope(j,k) > -b[i]/a[i]
令G[i] = rate[i]*f[i]，在二维平面上定义点Xi=(Fi,Gi)
Slope(j,k)就是通过Xj和Xk的斜率
维护一个点集X，支持以下两个操作：
?1)在第一象限的任意位置插入一个点
?2)给定负数斜率K，求所有斜率为K且过点集中任意点的直线在Y轴上的最大截距
操作2最终用到的点都会在点集的上凸壳上
?维护点集X的凸包，支持动态插入和斜率查询
?平衡树结构 O(nlogn)
很喜闻乐见的是，本题需要查询斜率，笔者太弱不会用set实现。splay维护凸壳模板题~
第一次写，代码很翔。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define eps 1e-7 8 #define MAXN 100010 9 #define LR ch[ch[root][0]][1] 10 #define RL ch[ch[root][1]][0] 11 #define INF 0x3f3f3f3f 12 using namespace std; 13 double a[MAXN],b[MAXN],rate[MAXN]; 14 double s,ans; int n; 15 16 struct point{ 17 double x,y; 18 bool operator<(const point&b)const{ 19 return (x<b.x||x==b.x&&y<b.y); 20 } 21 bool operator>(const point&b)const{ 22 return (x>b.x||x==b.x&&y>b.y); 23 } 24 point operator-(const point&b)const{ 25 return (point){x-b.x,y-b.y}; 26 } 27 }; 28 typedef point vector; 29 30 double sqr(double x){return x*x;} 31 32 double dist(point a,point b){ 33 return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); 34 } 35 36 double cross(vector a,vector b){ 37 return a.x*b.y-b.x*a.y; 38 } 39 40 struct Splay_ConvexHull{ 41 point key[MAXN];int pre[MAXN],suc[MAXN]; 42 int ch[MAXN][2],f[MAXN],queue[MAXN],pool[MAXN]; 43 int root,cnt,top; 44 void clear(){ 45 root=cnt=top=0; 46 } 47 int newnode(point v,int fa){ 48 int x=top?pool[top--]:(++cnt); 49 key[x]=v;f[x]=fa;ch[x][0]=ch[x][1]=0; 50 return x; 51 } 52 void rotate(int x,int t){ 53 int y=f[x]; 54 f[x]=f[y];if(f[y]) ch[f[y]][ch[f[y]][1]==y]=x; 55 ch[y][t]=ch[x][!t];if(ch[x][!t]) f[ch[x][!t]]=y; 56 f[ch[x][!t]=y]=x; 57 } 58 void splay(int x,int goal){ 59 while(f[x]!=goal){ 60 if(f[f[x]]==goal){ 61 rotate(x,ch[f[x]][1]==x); 62 }else{ 63 int y=f[x],t=(ch[f[y]][1]==y); 64 if(ch[y][t]==x) rotate(y,t),rotate(x,t); 65 else rotate(x,!t),rotate(x,t); 66 } 67 } 68 if(goal==0) root=x; 69 } 70 void erase(int x){ 71 if(!x) return; 72 int h=0,t=0; 73 for(queue[t++]=x;h<t;h++){ 74 int v=queue[h];pool[++top]=v; 75 if(ch[v][0]) queue[t++]=ch[v][0]; 76 if(ch[v][1]) queue[t++]=ch[v][1]; 77 } 78 } 79 void maintain(int x){ 80 int p; 81 if(ch[x][0]){ 82 for(p=ch[x][0];ch[p][1];p=ch[p][1]); 83 suc[p]=x;pre[x]=p; 84 }else 85 pre[x]=0; 86 if(ch[x][1]){ 87 for(p=ch[x][1];ch[p][0];p=ch[p][0]); 88 pre[p]=x;suc[x]=p; 89 }else 90 suc[x]=0; 91 } 92 int _insert(point v){ 93 if(!root){ 94 root=newnode(v,0);pre[root]=suc[root]=0; 95 return root; 96 } 97 int x=root; 98 for(;ch[x][key[x]<v];x=ch[x][key[x]<v]); 99 ch[x][key[x]<v]=newnode(v,x);100 x=ch[x][key[x]<v];101 splay(x,0);102 maintain(x);103 return x;104 }105 int getsuc(point v){106 int x=root,ret=0;point min={INF,INF};107 while(x){108 if(!(key[x]<v)) if(key[x]<min) min=key[x],ret=x;109 x=ch[x][key[x]<v];110 }111 return ret;112 }113 void maintain_U(point v){114 int _=getsuc(v),p,x,y,t;115 if(_)116 if(pre[_]){117 if(cross(v-key[pre[_]],key[_]-key[pre[_]])>-eps) return;118 p=_insert(v);119 120 x=ch[p][1],y=p,t=1;121 while(x){122 if(suc[x]==0||(cross(key[x]-v,key[suc[x]]-v)<-eps)){123 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];124 }else{125 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];126 }127 }128 ch[y][t]=0;129 130 x=ch[p][0],y=p,t=0;131 while(x){132 if(pre[x]==0||(cross(key[x]-key[pre[x]],v-key[pre[x]])<eps)){133 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];134 }else{135 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];136 }137 }138 ch[y][t]=0;139 }else{140 p=_insert(v);x=ch[p][1],y=p,t=1;141 while(x){142 if(suc[x]==0||(cross(key[x]-v,key[suc[x]]-v)<eps)){143 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];144 }else{145 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];146 }147 }148 ch[y][t]=0;149 }150 else{151 p=_insert(v);x=ch[p][0],y=p,t=0;152 while(x){153 if(pre[x]==0||(cross(key[x]-key[pre[x]],v-key[pre[x]])<-eps)){154 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];155 }else{156 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];157 }158 }159 ch[y][t]=0;160 }161 maintain(p);162 }163 int getpre_U(double slope){164 int x=root,ret=0;165 double dy=10000,dx=0.0001,ey,ex;166 while(x){167 if(pre[x]){168 ey=key[x].y-key[pre[x]].y;ex=key[x].x-key[pre[x]].x;169 if(ey>ex*slope){170 if(ey*dx<dy*ex){171 ret=x;dy=ey;dx=ex;172 }173 x=ch[x][1];174 }else175 x=ch[x][0];176 }177 else{178 if(!ret) ret=x;179 x=ch[x][1];180 }181 }182 return ret;183 }184 }T;185 186 int main(){187 //freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);188 scanf("%d%lf",&n,&s);189 for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]); 190 ans=s;double fi=ans/(rate[1]*a[1]+b[1]);191 T._insert((point){fi,rate[1]*fi});192 for(int i=2;i<=n;i++){193 int x=T.getpre_U(-b[i]/a[i]);194 ans=max(T.key[x].x*b[i]+T.key[x].y*a[i],ans);195 fi=ans/(rate[i]*a[i]+b[i]);196 T.maintain_U((point){fi,rate[i]*fi});197 }198 printf("%.3lf\n",ans);199 return 0;200 }
PART IV (crazy~) BZOJ 3461
3461: Jry的时间表
Time Limit: 60 Sec Memory Limit: 512 MB
Submit: 14 Solved: 4
[Submit][Status]Description
吉丽(JRY)的电脑里有一份时间表，表上有n个时间段，每个时间段吉丽都要和一个妹子约会。每个妹子都有一个属性a_i，表示吉丽和第i个妹子约会至少需要带的money。吉丽特意把a_i标在了第i行，以作备忘。
你听说了吉丽的这张时间表，决定篡改一下数据，让吉丽花更多的money。当然，你对这n个妹子也有不同的好感度，所以你准备把第i行的数改为b_i。
有一天你趁机接触到了吉丽的时间表，可是时间紧迫，你最多只能输入两个数据，其他只能通过复制得到了。
定义“一次操作”为：修改第i行的数据，将a_i改为b_i，选中这个数向上或向下拖动到第j行，这样就使得第min(i,j)至第max(i,j)行的数都被覆盖成了b_i。
注意：为了提高效率，你不会修改或覆盖同一行两次以上（包括两次）。
你的时间只够你完成两次操作，你在这么短的时间内仍不忘让吉丽花的money越多越好。请你回答：在最多操作两次的情况下，吉丽最多要花多少money。
Input
第一行n。第二行n个数，表示ai。第三行n个数，表示bi。
Output
一个数，表示吉丽最多要花的money。
Sample Input
7
1 3 4 7 6 1 2
1 1 3 1 5 1 1Sample Output
31
【其他】
第一次操作：修改第3行，向上拖动到第1行。
第二次操作：修改第5行，向下拖动到第7行。
修改后的数列：3 3 3 7 5 5 5，money和为31，可以验证这是最大值。
【数据范围】
1≤n≤500000,1≤ai,bi≤10^9HINT
数据已加强，By evil佂菡
Source
XXY杯省选模拟题
复制是两个很有趣的DP。至于两次操作只要翻转一次，两次答案合并就好。
来看看我的逗比做法。
1）枚举到 i 时，j~i 都变为b[i]的策略。
k<j，j比k优当且仅当：
b[i]×(i-j+1)-(sum[i]-sum[j-1])>b[i]×(i-k+1)-(sum[i]-sum[k-1])
……
(j-k)×b[i]<sum[j-1]-sum[k-1]
(sum[j-1]-sum[k-1])/(j-k)>b[i]
与上题类似的做法，维护上凸壳。
2）枚举到 i 时，j~i都变为b[j]的策略。
k<j，j比k优当且仅当：
b[j]×(i-j+1)-(sum[i]-sum[j-1])>b[k]×(i-k+1)-(sum[i]-sum[k-1])
……
(b[j]-b[k])×i>{(j-1)b[j]-sum[j-1]}-{(k-1)b[k]-sum[k-1]}
注意到b[]不递增，没法移项sad~
再移过来，(b[j]-b[k])×i-{(j-1)b[j]-sum[j-1]}+{(k-1)b[k]-sum[k-1]}>0
注意到这是ax+b>0的直线形式，很本能地认为，这题是插直线维护凸壳。
这样的凸壳有个显然的性质，凸壳上的直线斜率单调递增，截距递减。
插入某条直线L=ax+b，找到相邻的直线使得ai<a<aj。
直线合法仅当L与Li的交点在L与Lj的交点左侧。维护时与插入点维护凸壳类似。
斜率相等的直线直接判截距。
于是这道题目我写了两个splay~喜闻乐见。你会发现前面一问也是直线啊！
（事后他们告诉我，这叫动态半平面交！我真弱我连半平面交都不会）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define MAXN 500010 8 #define INF 10000000000 9 #define eps 1e-8 10 using namespace std; 11 typedef double LD; 12 typedef long long LL; 13 14 LL a[MAXN],b[MAXN],s[MAXN],f[MAXN],g[MAXN]; 15 int n; 16 17 struct point{ 18 LL x,y; 19 bool operator<(const point&b)const{ 20 return (x<b.x||x==b.x&&y<b.y); 21 } 22 bool operator>(const point&b)const{ 23 return (x>b.x||x==b.x&&y>b.y); 24 } 25 point operator-(const point&b)const{ 26 return (point){x-b.x,y-b.y}; 27 } 28 }; 29 typedef point vector; 30 31 LL cross(vector a,vector b){ 32 return a.x*b.y-b.x*a.y; 33 } 34 35 //带插入单点的凸壳（动态凸壳？） 36 struct Splay_ConvexHull_Point{ 37 point key[MAXN];int pre[MAXN],suc[MAXN]; 38 int ch[MAXN][2],f[MAXN],queue[MAXN],pool[MAXN]; 39 int root,cnt,top; 40 void clear(){ 41 root=cnt=top=0; 42 } 43 int newnode(point v,int fa){ 44 int x=top?pool[top--]:(++cnt); 45 key[x]=v;f[x]=fa;ch[x][0]=ch[x][1]=0; 46 return x; 47 } 48 void rotate(int x,int t){ 49 int y=f[x]; 50 f[x]=f[y];if(f[y]) ch[f[y]][ch[f[y]][1]==y]=x; 51 ch[y][t]=ch[x][!t];if(ch[x][!t]) f[ch[x][!t]]=y; 52 f[ch[x][!t]=y]=x; 53 } 54 void splay(int x,int goal){ 55 while(f[x]!=goal){ 56 if(f[f[x]]==goal){ 57 rotate(x,ch[f[x]][1]==x); 58 }else{ 59 int y=f[x],t=(ch[f[y]][1]==y); 60 if(ch[y][t]==x) rotate(y,t),rotate(x,t); 61 else rotate(x,!t),rotate(x,t); 62 } 63 } 64 if(goal==0) root=x; 65 } 66 void erase(int x){ 67 if(!x) return; 68 int h=0,t=0; 69 for(queue[t++]=x;h<t;h++){ 70 int v=queue[h];pool[++top]=v; 71 if(ch[v][0]) queue[t++]=ch[v][0]; 72 if(ch[v][1]) queue[t++]=ch[v][1]; 73 } 74 } 75 void maintain(int x){ 76 int p; 77 if(ch[x][0]){ 78 for(p=ch[x][0];ch[p][1];p=ch[p][1]); 79 suc[p]=x;pre[x]=p; 80 }else 81 pre[x]=0; 82 if(ch[x][1]){ 83 for(p=ch[x][1];ch[p][0];p=ch[p][0]); 84 pre[p]=x;suc[x]=p; 85 }else 86 suc[x]=0; 87 } 88 int _insert(point v){ 89 if(!root){ 90 root=newnode(v,0);pre[root]=suc[root]=0; 91 return root; 92 } 93 int x=root; 94 for(;ch[x][key[x]<v];x=ch[x][key[x]<v]); 95 ch[x][key[x]<v]=newnode(v,x); 96 x=ch[x][key[x]<v]; 97 splay(x,0); 98 maintain(x); 99 return x;100 }101 int lower_bound(point v){102 int x=root,ret=0;point min={INF,INF};103 while(x){104 if(!(key[x]<v)) if(key[x]<min) min=key[x],ret=x;105 x=ch[x][key[x]<v];106 }107 return ret;108 }109 void maintain_U(point v){110 int _=lower_bound(v),p,x,y,t;111 if(_)112 if(pre[_]){113 if(cross(v-key[pre[_]],key[_]-key[pre[_]])>=0) return;114 p=_insert(v);115 116 x=ch[p][1],y=p,t=1;117 while(x){118 if(suc[x]==0||(cross(key[x]-v,key[suc[x]]-v)<0)){119 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];120 }else{121 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];122 }123 }124 ch[y][t]=0;125 126 x=ch[p][0],y=p,t=0;127 while(x){128 if(pre[x]==0||(cross(key[x]-key[pre[x]],v-key[pre[x]])<0)){129 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];130 }else{131 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];132 }133 }134 ch[y][t]=0;135 }else{136 p=_insert(v);x=ch[p][1],y=p,t=1;137 while(x){138 if(suc[x]==0||(cross(key[x]-v,key[suc[x]]-v)<0)){139 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];140 }else{141 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];142 }143 }144 ch[y][t]=0;145 }146 else{147 p=_insert(v);x=ch[p][0],y=p,t=0;148 while(x){149 if(pre[x]==0||(cross(key[x]-key[pre[x]],v-key[pre[x]])<0)){150 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];151 }else{152 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];153 }154 }155 ch[y][t]=0;156 }157 maintain(p);158 }159 int find_U(LD slope){160 int x=root,ret=0;161 LD dy=10000000000,dx=0.000000001,ey,ex;162 while(x){163 if(pre[x]){164 ey=key[x].y-key[pre[x]].y;ex=key[x].x-key[pre[x]].x;165 if(ey-ex*slope>eps){166 if(ey*dx-dy*ex<-eps){167 ret=x;dy=ey;dx=ex;168 }169 x=ch[x][1];170 }else171 x=ch[x][0];172 }173 else{174 if(!ret) ret=x;175 x=ch[x][1];176 }177 }178 return ret;179 }180 }P;181 182 struct line{183 LL a,b;184 bool operator<(const line&L)const{185 return (a<L.a);186 }187 };188 LD cross(line L1,line L2){189 return (LD)(L2.b-L1.b)/(L1.a-L2.a);190 }191 192 //带插入直线的凸壳（动态半平面交？） 193 struct Splay_ConvexHull_Line{194 line key[MAXN];int pre[MAXN],suc[MAXN];195 int ch[MAXN][2],f[MAXN],queue[MAXN],pool[MAXN];196 int root,cnt,top;197 void clear(){198 root=cnt=top=0;199 }200 int newnode(line v,int fa){201 int x=top?pool[top--]:(++cnt);202 key[x]=v;f[x]=fa;ch[x][0]=ch[x][1]=0;203 return x;204 }205 void rotate(int x,int t){206 int y=f[x];207 f[x]=f[y];if(f[y]) ch[f[y]][ch[f[y]][1]==y]=x;208 ch[y][t]=ch[x][!t];if(ch[x][!t]) f[ch[x][!t]]=y;209 f[ch[x][!t]=y]=x;210 }211 void splay(int x,int goal){212 while(f[x]!=goal){213 if(f[f[x]]==goal){214 rotate(x,ch[f[x]][1]==x);215 }else{216 int y=f[x],t=(ch[f[y]][1]==y);217 if(ch[y][t]==x) rotate(y,t),rotate(x,t);218 else rotate(x,!t),rotate(x,t);219 }220 }221 if(goal==0) root=x;222 }223 void erase(int x){224 if(!x) return;225 int h=0,t=0;226 for(queue[t++]=x;h<t;h++){227 int v=queue[h];pool[++top]=v;228 if(ch[v][0]) queue[t++]=ch[v][0];229 if(ch[v][1]) queue[t++]=ch[v][1];230 }231 }232 void maintain(int x){233 int p;234 if(ch[x][0]){235 for(p=ch[x][0];ch[p][1];p=ch[p][1]);236 suc[p]=x;pre[x]=p;237 }else238 pre[x]=0;239 if(ch[x][1]){240 for(p=ch[x][1];ch[p][0];p=ch[p][0]);241 pre[p]=x;suc[x]=p;242 }else243 suc[x]=0; 244 }245 int _insert(line v){246 if(!root){247 root=newnode(v,0);pre[root]=suc[root]=0;248 return root;249 }250 int x=root;251 for(;ch[x][key[x]<v];x=ch[x][key[x]<v]);252 ch[x][key[x]<v]=newnode(v,x);253 x=ch[x][key[x]<v];254 splay(x,0);255 maintain(x);256 return x;257 }258 int lower_bound(line v){259 int x=root,ret=0;line min={INF,INF};260 while(x){261 if(!(key[x]<v)) if(key[x]<min) min=key[x],ret=x;262 x=ch[x][key[x]<v];263 }264 return ret;265 }266 void maintain_D(line v){267 int _=lower_bound(v),p,x,y,t;268 if(_)269 if(v.a==key[_].a){270 if(v.b<=key[_].b) return;p=_;key[p].b=v.b;splay(_,0);271 x=ch[p][1],y=p,t=1;272 while(x){273 if(suc[x]==0||cross(v,key[x])-cross(key[x],key[suc[x]])<-eps){274 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];275 }else{276 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];277 }278 }279 ch[y][t]=0;280 x=ch[p][0],y=p,t=0;281 while(x){282 if(pre[x]==0||cross(key[pre[x]],key[x])-cross(key[pre[x]],v)<-eps){283 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];284 }else{285 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];286 }287 }288 ch[y][t]=0;289 290 }else if(pre[_]){291 if(cross(key[pre[_]],v)-cross(v,key[_])>-eps) return;292 p=_insert(v);293 x=ch[p][1],y=p,t=1;294 while(x){295 if(suc[x]==0||cross(v,key[x])-cross(key[x],key[suc[x]])<-eps){296 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];297 }else{298 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];299 }300 }301 ch[y][t]=0;302 x=ch[p][0],y=p,t=0;303 while(x){304 if(pre[x]==0||cross(key[pre[x]],key[x])-cross(key[pre[x]],v)<-eps){305 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];306 }else{307 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];308 }309 }310 ch[y][t]=0;311 }else{312 p=_insert(v);x=ch[p][1],y=p,t=1;313 while(x){314 if(suc[x]==0||cross(v,key[x])-cross(key[x],key[suc[x]])<-eps){315 f[ch[y][t]=x]=y;y=x;t=0;x=ch[x][0];316 }else{317 pool[++top]=x;erase(ch[x][0]);x=ch[x][1];318 }319 }320 ch[y][t]=0;321 }322 else{323 p=_insert(v);x=ch[p][0],y=p,t=0;324 while(x){325 if(pre[x]==0||cross(key[pre[x]],key[x])-cross(key[pre[x]],v)<-eps){326 f[ch[y][t]=x]=y;y=x;t=1;x=ch[x][1];327 }else{328 pool[++top]=x;erase(ch[x][1]);x=ch[x][0];329 }330 }331 ch[y][t]=0;332 }333 maintain(p);334 }335 LL find_D(LL X){336 int x=root,ret=0;LD X1,X2;337 while(x){338 if(pre[x]+suc[x]==0)339 return key[x].a*X+key[x].b;340 else if(pre[x]==0){341 X2=cross(key[x],key[suc[x]]);342 if(X2-X>-eps) return key[x].a*X+key[x].b;343 else x=ch[x][1];344 }else if(suc[x]==0){345 X1=cross(key[pre[x]],key[x]);346 if(X1-X<eps) return key[x].a*X+key[x].b;347 else x=ch[x][0];348 }else{349 X1=cross(key[pre[x]],key[x]);350 X2=cross(key[x],key[suc[x]]);351 if(X1-X<eps&&X2-X>-eps) return key[x].a*X+key[x].b;352 if(X1-X>eps) x=ch[x][0]; else x=ch[x][1];353 }354 }355 }356 }L;357 358 void work(){359 int j;P.clear();L.clear();360 for(int i=1;i<=n;i++){361 P.maintain_U((point){i,s[i-1]});362 j=P.find_U(b[i]);363 f[i]=max(b[i]*(i-P.key[j].x+1)+P.key[j].y-s[i],f[i]);364 L.maintain_D((line){b[i],1ll*b[i]*(-(i-1))+s[i-1]});365 f[i]=max(L.find_D(i)-s[i],f[i]);366 }367 for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1]);368 }369 370 char buf[10000000],*pt = buf,*o = buf;371 int getint(){372 int f = 1,x = 0;373 while((*pt != ‘-‘) && (*pt < ‘0‘ || *pt > ‘9‘)) pt ++;374 if(*pt == ‘-‘) f = -1,pt ++; else x = *pt++ - 48;375 while(*pt >= ‘0‘ && *pt <= ‘9‘) x = x * 10 + *pt ++ - 48;376 return x * f;377 }378 379 int main(){380 //freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);381 fread(buf,1,10000000,stdin);382 n=getint();383 for(int i=1;i<=n;i++) a[i]=getint();384 for(int i=1;i<=n;i++) b[i]=getint();385 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];386 work();387 for(int i=1;i<=n;i++) g[i]=f[i];388 reverse(g+1,g+n+1);389 reverse(a+1,a+n+1);reverse(b+1,b+n+1);390 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];391 memset(f,0,sizeof(f));392 work();393 LL ans=0;394 for(int i=0;i<=n;i++) ans=max(f[i]+g[i+1],ans);395 printf("%lld\n",s[n]+ans);396 return 0;397 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。