题解 P4097 [HEOI2013]Segment

· · 题解

题目传送门

李超线段树模板题。

什么是李超线段树？

李超线段树是支持区间加入一条平面上的线段，单点询问函数最值的一种线段树。

什么是线段树？

呃，线段树可以在 O(logn) 的时间复杂度内完成单点修改、区间修改、单点查询、区间查询，是一种常用数据结构，主要用于维护区间信息。

李超线段树思想简介

每个线段树节点存储当前区间内最大优势线段，即在这个区间内所有线段中处于最高位置时所占横坐标跨度最大的线段。

存储方式：一次函数（存储 k，b）。

修改：

分类讨论。

若当前区间内新线段完全高于老线段，直接替换；

若当前区间内新线段完全低于老线段，跳过；

若一部分高一部分低（就是中间有交点），再分类讨论：

新线段在左子树区间内完全高于老的，替换左边，把老的递归到右边；

新线段在左子树区间内完全低于老的，把新的递归到右边；

新线段在右子树区间内完全高于老的，替换右边，把老的递归到左边；

新线段在右子树区间内完全低于老的，把新的递归到左边。

查询：

因为是单点查询，依次缩小点所在的区间，用 y=kx+b 计算出所有经过的区间中纵坐标最大值，然后输出对应编号即可。

本题注意事项：

输入信息解密；

开 double；

纵坐标相同取小编号；

如果 x0=x1 交点默认为大的纵坐标；

x0 可能大于 x1。

AC代码（含注释）：

#include<cstdio>
#include<iostream>
#include<cstring>

#define maxn 39989
#define maxm 100005
#define mod 39989
#define INF 0x3f3f3f3f

using namespace std;

const int mod0=1e9;

int n;

struct Tree{
    int l,r,id;//id记录最大优势线段编号
    double k,b;
    #define l(p) tree[p].l
    #define r(p) tree[p].r
    #define id(p) tree[p].id
    #define k(p) tree[p].k
    #define b(p) tree[p].b
    #define ls p<<1
    #define rs p<<1|1//位运算优化常数
}tree[maxn<<2];//别忘了开四倍

inline void build(int p,int l,int r)
{
    l(p)=l,r(p)=r;
    if(l==r){
        id(p)=k(p)=b(p)=0;
        return ;
    }
    int mid=l(p)+r(p)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}

inline void up(int p,double k,double b,int id)
{
    k(p)=k,b(p)=b,id(p)=id;
}

inline void change(int p,int l,int r,double k,double b,int id)
{
    int mid=l(p)+r(p)>>1;
    if(l<=l(p)&&r>=r(p)){
        double x0=l(p),x1=r(p);
        double y0p=k(p)*x0+b(p),y1p=k(p)*x1+b(p);
        double y0=k*x0+b,y1=k*x1+b;
        if(y0>=y0p&&y1>=y1p) up(p,k,b,id);//新线段完全高于老线段
        else if(y0<=y0p&&y1<=y1p) return ;//新线段完全低于老线段
        else{//有交
            double mid=(x0+x1)/2.0,jiao=(b-b(p))/(k(p)-k);
            if(y0>y0p){
                if(jiao<=mid) change(ls,l,r,k,b,id);//在右子树区间内完全低于老的
                else change(rs,l,r,k(p),b(p),id(p)),up(p,k,b,id);//在左子树区间内完全高于老的
            }
            else{
                if(jiao<=mid) change(ls,l,r,k(p),b(p),id(p)),up(p,k,b,id);//在右子树区间内完全高于老的
                else change(rs,l,r,k,b,id);//在左子树区间内完全低于老的
            }
        }
        return ;
    }
    if(l<=mid) change(ls,l,r,k,b,id);
    if(r>mid) change(rs,l,r,k,b,id);
}

inline int ask(int p,int x,int ans,double mx)
{
    if((1.0*x)*k(p)+b(p)>mx){
        mx=(1.0*x)*k(p)+b(p);
        ans=id(p);
    }
    else if((1.0*x)*k(p)+b(p)==mx){
        ans=min(id(p),ans);//如果相等取小编号
    }
    if(l(p)==r(p)) return ans;
    int mid=l(p)+r(p)>>1;
    if(x<=mid) return ask(ls,x,ans,mx);
    else return ask(rs,x,ans,mx);
}

int main()
{
    cin>>n;
    build(1,1,maxn);
    int cnt=0,lastans=0;
    for(int i=1;i<=n;i++){
        int opt;
        cin>>opt;
        if(!opt){
            int k;
            cin>>k;
            k=(k+lastans-1)%mod+1;//别忘了解密
            lastans=ask(1,k,0,0);
            cout<<lastans<<endl;
        }
        else{
            cnt++;
            int x0,y0,x1,y1;
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+lastans-1)%mod+1,y0=(y0+lastans-1)%mod0+1;
            x1=(x1+lastans-1)%mod+1,y1=(y1+lastans-1)%mod0+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            double k,b;
            if(x0==x1) k=0,b=max(y0,y1);//特殊情况特判
            else k=(double)(y1-y0)/(double)(x1-x0),b=(double)y0-(1.0*x0)*k;
            change(1,x0,x1,k,b,cnt);
        }
    }
    return 0;
}