P4254 [JSOI2008]Blue Mary开公司

P4254 [JSOI2008]Blue Mary开公司

李超树裸题，注意一开始截距是\(S-P\)。

code:

#include<bits/stdc++.h>
using namespace std;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const int maxn=500010;
const int maxm=100010;
const double eps=1e-8;
int n,cnt;
int maxid[maxn<<2];
double k[maxm],b[maxm];
inline double f(int x,int id){return k[id]*x+b[id];}
inline bool check(int a,int b,int x){return fabs(f(x,a)-f(x,b))>eps?f(x,a)<f(x,b):a>b;}
void insert(int p,int l,int r,int ql,int qr,int id)
{
    int mid=(l+r)>>1;
    if(l>=ql&&r<=qr)
    {
        if(check(id,maxid[p],l)&&check(id,maxid[p],r))return;
        if(!check(id,maxid[p],l)&&!check(id,maxid[p],r)){maxid[p]=id;return;}
        if(!check(id,maxid[p],mid))swap(id,maxid[p]);
        if(!check(id,maxid[p],l))insert(ls(p),l,mid,ql,qr,id);
        else insert(rs(p),mid+1,r,ql,qr,id);
        return;
    }
    if(ql<=mid)insert(ls(p),l,mid,ql,qr,id);
    if(qr>mid)insert(rs(p),mid+1,r,ql,qr,id);
}
int query(int p,int l,int r,int pos)
{
    if(l==r)return maxid[p];
    int mid=(l+r)>>1,res;
    res=pos<=mid?query(ls(p),l,mid,pos):query(rs(p),mid+1,r,pos);
    res=check(res,maxid[p],pos)?maxid[p]:res;
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char op[10];scanf("%s",op);
        if(op[0]=='Q')
        {
            int x;scanf("%d",&x);
            printf("%d\n",(int)(f(x,query(1,1,50000,x))/100));
        }
        else 
        {
            double P,S;
            scanf("%lf%lf",&S,&P);
            cnt++;k[cnt]=P,b[cnt]=S-P;
            insert(1,1,50000,1,50000,cnt);          
        }
    }
    return 0;
}

P4254 [JSOI2008]Blue Mary开公司

原文：https://www.cnblogs.com/nofind/p/11986884.html