C119 李超线段树 P4097 [HEOI2013] Segment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5, D=4e4, p1=39989, p2=1e9;
const double eps=1e-9;
int tree[N<<2];
struct line{
    int x0, x1;
    double k, b;
}a[N];
double f(int x, int id){
    return a[id].k*(double)x + a[id].b;
}
bool cmp(int u, int v, int x){//1：u更优，0：v更优
    double a = f(x, u), b = f(x, v);
    if(b - a > eps) return 0;
    if(a - b > eps) return 1;
    return u < v;
}
void upd(int p, int pl, int pr, int u){ 
    int &v = tree[p], mid=(pl+pr)>>1;
    if(cmp(u, v, mid)) swap(u, v);
    if(pl == pr) return;
    if(cmp(u, v, pl)) upd(p<<1, pl, mid, u);
    if(cmp(u, v, pr)) upd(p<<1|1, mid+1, pr, u);
}
void update(int p, int pl, int pr, int L, int R, int id){
    if(L <= pl && R >= pr)
        return upd(p, pl, pr, id), void();
    int mid=(pl+pr)>>1;
    if(L <= mid)
        update(p<<1, pl, mid, L, R, id);
    if(R > mid)
        update(p<<1|1, mid+1, pr, L, R, id);
}
int query(int p, int pl, int pr, int x){
    if(pl == pr){
        return tree[p];
    }
    int mid=(pl+pr)>>1, t=0;
    if(x <= mid)
        t = query(p<<1, pl, mid, x);
    else t = query(p<<1|1, mid+1, pr, x);
    return (cmp(t, tree[p], x) ? t : tree[p]);
}
int n, lastans;
int conv(int x, int mod){
    return (x + lastans - 1) % mod + 1;
}
line addl(double x0, double x1, double y0, double y1){
    if(fabs(x0 - x1) > eps){
        double k = (y0 - y1)/(x0 - x1);
        return {x0, x1, k, -x0*k + y0};
    }
    else return {x0, x1, 0, max(y0, y1)};
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);;
    int cnt=0;
    cin >> n;
    for(int i=1; i<=n; ++i){
        int x0, y0, x1, y1, k, op;
        cin >> op;
        if(!op){
            cin >> k;
            k = conv(k, p1);
            cout << (lastans = query(1, 1, D, k)) << '\n';
        }
        else{
            cin >> x0 >> y0 >> x1 >> y1;
            x0 = conv(x0, p1), x1 = conv(x1, p1);
            y0 = conv(y0, p2), y1 = conv(y1, p2);
            a[++cnt] = addl(x0, x1, y0, y1);
            if(x0 > x1) swap(x0, x1);
            update(1, 1, D, x0, x1, cnt);
        }
    }
    return 0;
}

C119 李超线段树 P4097 [HEOI2013] Segment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,D=4e4,p1=39989,p2=1e9;
const double eps=1e-9;
int tree[N<<2];
struct line{
    int x0,x1;
    double k,b;
}a[N];
double f(int x,int id){
    return a[id].k*(double)x+a[id].b;
}
bool cmp(int u,int v,int x){//1：u更优,0：v更优
    double a=f(x,u),b=f(x,v);
    if(b-a>eps) return 0;
    if(a-b>eps) return 1;
    return u<v;
}
void upd(int p,int pl,int pr,int u){ 
    int &v=tree[p],mid=(pl+pr)>>1;
    if(cmp(u,v,mid)) swap(u,v);
    if(pl==pr) return;
    if(cmp(u,v,pl)) upd(p<<1,pl,mid,u);
    if(cmp(u,v,pr)) upd(p<<1|1,mid+1,pr,u);
}
void update(int p,int pl,int pr,int L,int R,int id){
    if(L<=pl && R>=pr)
        return upd(p,pl,pr,id),void();
    int mid=(pl+pr)>>1;
    if(L<=mid)
        update(p<<1,pl,mid,L,R,id);
    if(R>mid)
        update(p<<1|1,mid+1,pr,L,R,id);
}
int query(int p,int pl,int pr,int x){
    if(pl==pr){
        return tree[p];
    }
    int mid=(pl+pr)>>1,t=0;
    if(x<=mid)
        t=query(p<<1,pl,mid,x);
    else t=query(p<<1|1,mid+1,pr,x);
    return (cmp(t,tree[p],x) ? t:tree[p]);
}
int n,lastans;
int conv(int x,int mod){
    return (x+lastans-1)%mod+1;
}
line addl(double x0,double x1,double y0,double y1){
    if(fabs(x0-x1)>eps){
        double k=(y0-y1)/(x0-x1);
        return {x0,x1,k,-x0*k+y0};
    }
    else return {x0,x1,0,max(y0,y1)};
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int cnt=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        int x0,y0,x1,y1,k,op;
        cin>>op;
        if(!op){
            cin>>k;
            k=conv(k,p1);
            cout<<(lastans=query(1,1,D,k))<<'\n';
        }
        else{
            cin>>x0>>y0>>x1>>y1;
            x0=conv(x0,p1),x1=conv(x1,p1);
            y0=conv(y0,p2),y1=conv(y1,p2);
            a[++cnt]=addl(x0,x1,y0,y1);
            if(x0>x1) swap(x0,x1);
            update(1,1,D,x0,x1,cnt);
        }
    }
    return 0;
}