【BZOJ4172】弹珠

2015.08.10 13:35 Mon | 38次阅读 | 旧日oi | 固定链接 | 源码

题目大意

涉及版权,我就不贴了

题解

先用treap把a搞出来,然后维护上凸壳每次二分查找就行了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 400005
#define ll long long
int n,m,x,y,root,cnt;
char s[10];
int rnd[N],val[N],siz[N],l[N],r[N];
#define ls l[rt]
#define rs r[rt]
void update(int rt)
{
    siz[rt]=siz[ls]+siz[rs]+1;
}
void lturn(int &k)
{
    int t=r[k];r[k]=l[t];l[t]=k;
    siz[t]=siz[k];update(k);k=t;
}
void rturn(int &k)
{
    int t=l[k];l[k]=r[t];r[t]=k;
    siz[t]=siz[k];update(k);k=t;
}
void insert(int &rt,int x,int y)
{
    if(!rt)
    {
        rt=++cnt;
        siz[rt]=1;
        rnd[rt]=rand();
        val[rt]=y;
        return;
    }
    siz[rt]++;
    if(siz[ls]>=x) 
    {
        insert(ls,x,y);
        if(rnd[ls]<rnd[rt]) rturn(rt); 
    }
    else
    {
        insert(rs,x-siz[ls]-1,y);
        if(rnd[rs]<rnd[rt]) lturn(rt);
    }
}
void change(int rt,int x,int y)
{
    if(siz[ls]==x)
    {
        val[rt]=y;
        return;
    }
    else if(siz[ls]>x) change(ls,x,y);
    else change(rs,x-siz[ls]-1,y);
}
int a[N],num;
void dfs(int rt)
{
    if(ls) dfs(ls);
    a[++num]=val[rt];
    if(rs) dfs(rs);
}
struct node
{
    ll x,y;
    double lk,rk;
}p[N],st[N];
int top;
#define inf 233333333.0
int find(int x)
{
    int l=1,r=top,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(st[mid].lk<x) r=mid-1;
        else if(st[mid].rk>x) l=mid+1;
        else return mid;
    }
}
double calc_k(node a,node b)
{
    return double(a.y-b.y)/(a.x-b.x);
}
double calc(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)>=(b.y-a.y)*(c.x-a.x);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d%d",s,&x,&y);
        if(s[0]=='I') insert(root,x,y);
        else change(root,x,y);
    }
    dfs(root);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
    st[top=1]=p[1];st[1].lk=inf;st[1].rk=-inf;
    for(int i=2;i<=n;i++)
    {
        int k=find(a[i]);
        printf("%lld\n",max(0ll,-a[i]*st[k].x+st[k].y));
        while(top>1&&calc(st[top-1],st[top],p[i])) top--;
        st[++top]=p[i];st[top].rk=-inf;
        if(top==1) st[top].lk=inf;
        else st[top].lk=st[top-1].rk=calc_k(st[top],st[top-1]);
    }
}```