题解：P14208 [ROI 2016 Day1] 人烟之山

yangzichen1203 · 2026-11-13 11:44:20 · 题解

可以做到在线 1log。

每次询问对两侧二分最远的均合法位置，一个顶点对一个前缀合法当且仅当只在其凸壳内部。

对这些半平面按 x 轴顺序建线段树，每个节点维护区间的凸壳，在一个区间的凸壳内部当且仅当在每个对应的线段树节点的凸壳内部。

不优化是在线 2log 的。建凸壳时归并排序，询问时分散层叠，即可在线做到 1log。

:::success[Code]

#include<bits/stdc++.h>
#define For(i,j,k) for(auto i=(j);i<=(k);i++)
#define dFor(i,j,k) for(auto i=(j);i>=(k);i--)
using namespace std;
#define MAXN 400005
int n,q,x[MAXN],y[MAXN];
struct Line{
    long long k,b;
    inline long long calc(int x){
        return 1ll*k*x+b;
    }
}a[MAXN];
inline bool cross(const Line &x,const Line &y,const Line &z){
    return (__int128)(y.b-x.b)*(y.k-z.k)<=(__int128)(z.b-y.b)*(x.k-y.k);
}
namespace SGT{
    struct Node{
        vector<Line> v;
    }tr[MAXN*4];
    void build(int c,int L,int R){
        vector<Line> now;
        For(i,L,R){
            now.push_back(a[i]);
        }
        sort(now.begin(),now.end(),[&](const Line &x,const Line &y){
            if(x.k!=y.k) return x.k>y.k;
            else return x.b>y.b;
        });
        for(auto l:now){
            while(tr[c].v.size()>=2&&cross(tr[c].v[tr[c].v.size()-2],tr[c].v.back(),l)){
                tr[c].v.pop_back();
            }
            tr[c].v.push_back(l);
        }
        if(L==R) return ;
        int mid=(L+R)>>1;
        build(c*2,L,mid);
        build(c*2+1,mid+1,R);
    }
    bool check(int c,int x,int y){
        int L=0,R=(int)tr[c].v.size()-2;
        while(L<=R){
            int mid=(L+R)>>1;
            if(tr[c].v[mid].calc(x)<=tr[c].v[mid+1].calc(x)){
                L=mid+1;
            }else{
                R=mid-1;
            }
        }
        return y>=tr[c].v[L].calc(x);
    }
    int find(int c,int L,int R,int l,int r,int x,int y,bool op){
        if(check(c,x,y)) return -1;
        if(L==R){
            if(op==0) return ::x[L];
            else return ::x[L-1];
        }
        int mid=(L+R)>>1;
        if(r<=mid) return find(c*2,L,mid,l,r,x,y,op);
        else if(l>mid) return find(c*2+1,mid+1,R,l,r,x,y,op);
        else{
            if(op==0){
                int ans=find(c*2+1,mid+1,R,l,r,x,y,op);
                if(ans!=-1) return ans;
                return find(c*2,L,mid,l,r,x,y,op);
            }else{
                int ans=find(c*2,L,mid,l,r,x,y,op);
                if(ans!=-1) return ans;
                return find(c*2+1,mid+1,R,l,r,x,y,op);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    x[0]=y[0]=0;
    For(i,1,n){
        int d,k;
        cin>>d>>k;
        x[i]=x[i-1]+d;
        y[i]=y[i-1]+d*k;
        a[i]={k,y[i]-1ll*x[i]*k};
    }
    SGT::build(1,1,n);
    while(q--){
        int u,v;
        cin>>u>>v;
        int pos=lower_bound(x+1,x+n+1,u)-x;
        int l=SGT::find(1,1,n,1,pos,u,v,0);
        int r=SGT::find(1,1,n,pos,n,u,v,1);
        if(l==-1) l=x[0];
        if(r==-1) r=x[n];
        cout<<l<<' '<<r<<'\n';
    }
    return 0;
}

:::