更新日志

2025/01/21：开工。

用处

\(O(n\log n)\) 解决这个问题

实现

首先，我们肯定需要一棵线段树，区间为横轴。

我们考虑每一段都储存最优的线段，但考虑到线段必然有交点，所以会有较为复杂的情况，下面详细考虑：

首先考虑单纯的储存线段，我们把线段横轴影射区间区间修改即可。

下面考虑同一区间多条线段的情况。

首先，如果一个线段完全优于另一个，那么就可以把劣的那个删掉了。

接下来考虑交点情况，如何解决呢？我们令中点上最优的线段为当前最优线段，并把另一条线段下放到可能的最优位置。如果交点在左侧，说明其在左侧有可能的最优区间，在左子节点加入这个劣线段；右侧同理。

下面考虑查询，我们直接把走到这个节点上经过的所有答案取最优值即可，这样就解决了上面把线段下方产生的问题。

模板

struct line{
    db k,b;
    db y(db x){return k*x+b;}
}ls[N];
struct lsegment{
    int dat[M*4+5];
    void insert(int lq,int rq,int id,int x=1,int l=1,int r=M){
        if(l==lq&&r==rq){
            if(!dat[x]){
                dat[x]=id;
                return;
            }
            int m=l+r>>1;
            if(ls[dat[x]].y(m)<ls[id].y(m))swap(dat[x],id);
            if(ls[id].y(l)>ls[dat[x]].y(l))insert(l,m,id,x<<1,l,m);
            if(ls[id].y(r)>ls[dat[x]].y(r))insert(m+1,r,id,x<<1|1,m+1,r);
            return;
        }
        int m=l+r>>1;
        if(rq<=m)insert(lq,rq,id,x<<1,l,m);
        else if(m<lq)insert(lq,rq,id,x<<1|1,m+1,r);
        else insert(lq,m,id,x<<1,l,m),insert(m+1,rq,id,x<<1|1,m+1,r);
    }
    int query(int k,int x=1,int l=1,int r=M){
        if(l==r)return dat[x];
        int m=l+r>>1,res;
        if(k<=m)res=query(k,x<<1,l,m);
        else res=query(k,x<<1|1,m+1,r);
        if(!res||ls[dat[x]].y(k)>ls[res].y(k))res=dat[x];
        return res;
    }
}lseg;

细节

对于这道例题，上面的代码是无法通过的。

你需要开 long double，特判相等情况，以及当心精度问题。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;

const int N=1e5+5,M=39989;

struct line{
    db k,b;
    db y(db x){return k*x+b;}
}ls[N];
struct lsegment{
    int dat[M*4+5];
    void insert(int lq,int rq,int id,int x=1,int l=1,int r=M){
        if(l==lq&&r==rq){
            if(!dat[x]){
                dat[x]=id;
                return;
            }
            int m=l+r>>1;
            if(ls[dat[x]].y(m)<ls[id].y(m)||fabs(ls[dat[x]].y(m)-ls[id].y(m))<1e-10&&id<dat[x])swap(dat[x],id);
            if(ls[id].y(l)>ls[dat[x]].y(l)||fabs(ls[dat[x]].y(l)-ls[id].y(l))<1e-10&&id<dat[x])insert(l,m,id,x<<1,l,m);
            if(ls[id].y(r)>ls[dat[x]].y(r)||fabs(ls[dat[x]].y(r)-ls[id].y(r))<1e-10&&id<dat[x])insert(m+1,r,id,x<<1|1,m+1,r);
            return;
        }
        int m=l+r>>1;
        if(rq<=m)insert(lq,rq,id,x<<1,l,m);
        else if(m<lq)insert(lq,rq,id,x<<1|1,m+1,r);
        else insert(lq,m,id,x<<1,l,m),insert(m+1,rq,id,x<<1|1,m+1,r);
    }
    int query(int k,int x=1,int l=1,int r=M){
        if(l==r)return dat[x];
        int m=l+r>>1,res;
        if(k<=m)res=query(k,x<<1,l,m);
        else res=query(k,x<<1|1,m+1,r);
        if(!res||ls[dat[x]].y(k)>ls[res].y(k))res=dat[x];
        else if(res&&dat[x]&&fabs(ls[dat[x]].y(k)-ls[res].y(k))<1e-10&&dat[x]<res)res=dat[x];
        return res;
    }
}lseg;

int n,m,ans;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
    int op,x0,y0,x1,y1;
    rep(i,1,n){
        cin>>op;
        if(op){
            ++m;
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+ans-1)%39989+1,x1=(x1+ans-1)%39989+1;
            y0=(y0+ans-1)%(int)1e9+1,y1=(y1+ans-1)%(int)1e9+1;
            if(x0>x1)swap(x0,x1),swap(y0,y1);
            if(x0!=x1)ls[m].k=db(y1-y0)/(x1-x0),ls[m].b=y0-ls[m].k*x0;
            else ls[m].k=0,ls[m].b=max(y0,y1);
            lseg.insert(x0,x1,m);
        }else{
            cin>>x0;
            x0=(x0+ans-1)%39989+1;
            ans=lseg.query(x0);
            cout<<ans<<"\n";
        }
    }
    return 0;
}

应用

可以用来斜率优化。