李超树

· · 个人记录

李超树：

用处：

用来存储每一段区间最优势直线（优势最大即暴露在最高折线中横坐标跨度最大)。

Segment:

我们考虑如何加入一条新的线段。(bool g(i,p,q)表示横坐标为i时p直线取值是否大于q)

1.当前区间没有线段，直接赋值；

2.当前最大线段左右端点都大于加入线段，返回。

    if(g(l,s[k],t)&&g(r,s[k],t))return;

3.当前最大线段左右端点都小于加入线段，覆盖。

    if(g(l,s[k],t)&&g(r,s[k],t))return;

4.否则就是两条线段有交点。其实可以发现，谁在mid的点较优，就是这段的最大优势直线。但是另一个有可能是左右区间的最优势线段，所以要下传。

    if(g(m,t,s[k]))swap(t,s[k]);
    if(g(l,t,s[k]))add(k<<1,l,m,t);
    else add(k<<1|1,m+1,r,t);

Code:这是我自己的代码，上述代码是觉得panyf聚聚在货币兑换的题解代码风格，比我写的简洁许多，于是学习了一下。下面是提供另一种更朴素的强力分讨李超树写法

#include<bits/stdc++.h>
#define re register
#define ee 1e-7
using namespace std;
typedef long long ll;
const int N=1e5;
const int M=1e5+100;
int n,opt,tot;
int x1,ans;
int x2;
int yy;
int y2; 
double K[M],B[M];
inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return s*w;
}
struct node
{
    bool bj;
    int id;
    double k,b;
    void up(int _id,double _k,double _b)
    {
        id=_id;k=_k;b=_b;
    }
}t[M<<2];
void Cmax(int &a,int b,int x)
{
    double ya=K[a]*x+B[a];
    double yb=K[b]*x+B[b];
    if(ya<yb||(fabs(ya-yb)<1e-7&&a>b)) a=b;
}
inline int ask(int wz,int l,int r,int x)
{
    if(l==r) return t[wz].id;
    int mid=(l+r)>>1,an=t[wz].id;
    if(x<=mid) Cmax(an,ask(wz<<1,l,mid,x),x);
    else Cmax(an,ask(wz<<1|1,mid+1,r,x),x);
    return an;
}
void cl(int wz,int l,int r,int id,double k,double b)
{
    if(!t[wz].bj)
    {   t[wz].bj=1;
        t[wz].up(id,k,b);return ;
    }
    int mid=(l+r)>>1;
    double l1=l*t[wz].k+t[wz].b,r1=r*t[wz].k+t[wz].b;
    double l2=l*k+b,r2=r*k+b;
    if(l1>=l2&&r1>=r2) return ;
    if(l1<l2&&r1<r2) {
        t[wz].up(id,k,b);
        return ;
    }
    double x=1.0*(b-t[wz].b)/(t[wz].k-k);
    if(x<=mid)
    {
        if(l1>l2)
            cl(wz<<1,l,mid,t[wz].id,t[wz].k,t[wz].b),t[wz].up(id,k,b);
        else
            cl(wz<<1,l,mid,id,k,b);
    }
    else
    {
        if(l1>l2)
            cl(wz<<1|1,mid+1,r,id,k,b);
        else
            cl(wz<<1|1,mid+1,r,t[wz].id,t[wz].k,t[wz].b),t[wz].up(id,k,b);
    }
}
void modify(int wz,int l,int r,int ql,int qr,int id,double k,double b)
{
    if(ql<=l&&qr>=r)
    {
        cl(wz,l,r,id,k,b);
        return ;
    }
    int mid=(l+r)>>1;
    if(ql<=mid) modify(wz<<1,l,mid,ql,qr,id,k,b);
    if(qr>mid) modify(wz<<1|1,mid+1,r,ql,qr,id,k,b);
}
signed main(){
    n=read();
    while(n--)
    {
        opt=read();
        if(opt==0)
        {
            int k=read();
            k=(((k+ans-1)%39989)+1);
            ans=ask(1,1,N,k);
            printf("%d\n",ans);
        }
        else
        {
            x1=read();x1=(x1+ans-1)%39989+1;
            yy=read();yy=(yy+ans-1)%1000000000+1;
            x2=read();x2=(x2+ans-1)%39989+1;
            y2=read();y2=(y2+ans-1)%1000000000+1;
            if(x1>x2) swap(x1,x2),swap(yy,y2);
            tot++;
            K[tot]=1.0*(y2-yy)/(x2-x1);
            B[tot]=yy-K[tot]*x1;
            modify(1,1,N,x1,x2,tot,K[tot],B[tot]);
        }
    }
    return 0;
}