弹珠
时间限制 : 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
题解
出题人硬生生地把两道题合在了一起……
弹珠最大响度的公式有明显的斜率优化的形式，关键在于如何求出
代码
#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;
}
文章最后发布于: 2018-02-27 23:40:02