【bzoj4172】弹珠

本文主要是介绍【bzoj4172】弹珠，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

时间限制 : 2000 MS 空间限制 : 262144KB

问题描述

样例输入

5 10
Insert 0 10
Change 0 2
Insert 0 2
Change 0 10
Insert 2 4
Insert 1 8
Change 1 2
Change 0 5
Insert 1 2
Change 1 4
1 5
2 10
3 14
4 17
5 19

样例输出

1
6
8
2

提示

第1次操作后，序列为{10}
第2次操作后，序列为{2}
第3次操作后，序列为{2,2}
第4次操作后，序列为{10,2}
第5次操作后，序列为{10,2,4}
第6次操作后，序列为{10,8,2,4}
第7次操作后，序列为{10,2,2,4}
第8次操作后，序列为{5,2,2,4}
第9次操作后，序列为{5,2,2,2,4}
第10次操作后，序列为{5,4,2,2,4}
对于第2颗弹珠，B_{1,2}=1， 最大值为 1
对于第3颗弹珠，B_{1,3}=3，B_{2,3}=6，最大值为6
对于第4颗弹珠，B_{1,4}=3，B_{2,4}=6，B_{3,4}=8，最大值为8
对于第5颗弹珠，B_{1,5}=1，B_{2,5}=2，B_{3,5}=2，B_{4,5}=1，最大值为2

对于前 30% 的数据， n <= 1000， m <= 3000
对于前 50% 的数据， n <= 10000，m <= 20000
对于 100% 的数据， n <= 400000，m <= 500000，0

题解

出题人硬生生地把两道题合在了一起……
弹珠最大响度的公式有明显的斜率优化的形式，关键在于如何求出$a$数列……其实用Splay搞一搞就好了……斜率优化维护上凸包，但$a$数列不单调，要用二分法查找切线位置……

代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
const ll inf=1e18;
const ll eps=1e-9;
ll n,m,t,u,tl,tr,ans,cnt,mid,top,b[maxn],p[maxn],q[maxn],s[maxn];
ll rt,tot,a[maxn],l[maxn],r[maxn],fa[maxn],siz[maxn];
char op[10];
void Zig(ll x)
{ll y=fa[x],z=fa[y];if(z){if(l[z]==y) l[z]=x;else r[z]=x;}fa[x]=z,l[y]=r[x],fa[r[x]]=y,r[x]=y,fa[y]=x;siz[x]=siz[y],siz[y]=siz[l[y]]+siz[r[y]]+1;
}
void Zag(ll x)
{ll y=fa[x],z=fa[y];if(z){if(l[z]==y) l[z]=x;else r[z]=x;}fa[x]=z,r[y]=l[x],fa[l[x]]=y,l[x]=y,fa[y]=x;siz[x]=siz[y],siz[y]=siz[l[y]]+siz[r[y]]+1;
}
void Splay(ll x)
{while(fa[x]){ll y=fa[x],z=fa[y];if(z){if(l[z]==y){if(l[y]==x) Zig(y),Zig(x);else Zag(x),Zig(x);}if(r[z]==y){if(r[y]==x) Zag(y),Zag(x);else Zig(x),Zag(x);}}else{if(l[y]==x) Zig(x);else Zag(x);}}rt=x;
}
ll Getkth(ll k)
{ll p=rt;while(p){if(siz[l[p]]+1==k) break;if(siz[l[p]]+1<k) k-=siz[l[p]]+1,p=r[p];else p=l[p];}return p;
}
void DFS(ll p)
{if(l[p]) DFS(l[p]);b[cnt++]=a[p];if(r[p]) DFS(r[p]);
}
double Slope(ll x,ll y)
{if(x==0||y==0) return inf;if(x==inf||y==inf) return -inf;return (double)1.0*(q[y]-q[x])/(double)(p[y]-p[x]);
}
int main()
{scanf("%lld%lld",&n,&m),siz[++tot]=1,rt=tot;while(m--){scanf("%s%lld%lld",op+1,&t,&u);if(op[1]=='I'){ll temp=Getkth(t+1);Splay(temp),a[++tot]=u,siz[tot]=1,siz[temp]++;if(!r[temp]) fa[tot]=temp,r[temp]=tot;else{r[tot]=r[temp],fa[r[temp]]=tot,siz[tot]+=siz[r[temp]];fa[tot]=temp,r[temp]=tot;}}else{ll temp=Getkth(t+2);if(temp) a[temp]=u;}}DFS(rt),s[top=1]=1;for(ll i=1;i<=n;i++) scanf("%lld%lld",&p[i],&q[i]);for(ll i=2;i<=n;i++){tl=1,tr=top,s[top+1]=inf;while(1){mid=(tl+tr)>>1;if(Slope(s[mid-1],s[mid])+eps>=1.0*b[i]&&Slope(s[mid],s[mid+1])<=eps+1.0*b[i]) break;if(Slope(s[mid],s[mid+1])>eps+1.0*b[i]) tl=mid+1;else tr=mid-1;}ans=max(0ll,-b[i]*p[s[mid]]+q[s[mid]]),printf("%lld\n",ans);while(top>1&&Slope(s[top-1],s[top])<Slope(s[top],i)) top--;s[++top]=i;}return 0;
}

这篇关于【bzoj4172】弹珠的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---