李超线段树模板求调

rt，sub2WA11~15 RE16~17

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define y1 Y1
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define P pair<double,double>
#define x first
#define y second
#define modd(x) (((x)%mod+mod)%mod) 
#define rd read()
#define lowbit(x) ((x)&(-x))
#define abs(x) ((x)<0?-(x):(x))
mt19937 rnd(time(0));
inline int read(int u=0, char c=getchar(), bool f=false){
    for (;!isdigit(c);c=getchar()) f|=c=='-';
    for (;isdigit(c);c=getchar()) u=(u<<1)+(u<<3)+c-'0';
    return f?-u:u;
}
inline void wt(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) wt(x/10);
    putchar(x%10+48);
}
inline void wt(int x,char k){wt(x),putchar(k);}
const int inf=~0U>>1,linf=~0ULL>>1; 
const int mod=998244353,g=3,gi=332748118;
const int N=1e5+10;
struct node{
    int lc,rc,id;
}tr[N<<2];
int n,root,cnt,cntedge;
struct edge{
    double k,b;
}p[N];
const double eps=1e-9;
int cmp(double x,double y){
    if(x>y+eps) return 1;
    if(y>x+eps) return -1;
    return 0;
}
double calc(int id,int x){return p[id].k*x+p[id].b;}
void add_edge(int x0,int y0,int x1,int y1){
    if(x0==x1) p[++cntedge].k=0,p[cntedge].b=max(y0,y1);
    else p[++cntedge].k=(y0-y1)*1.0/(x0-x1),p[cntedge].b=y0-p[cntedge].k*x0;
}
void pushdown(int &now,int l,int r,int v){
    if(!now) now=++cnt;
    if(!tr[now].id){
        tr[now].id=v;
        return ;
    }
    int mid=l+r>>1,u=tr[now].id;
    int bmid=cmp(calc(u,mid),calc(v,mid));
    if(bmid==1||(!bmid&&(u<v))) swap(u,v);tr[now].id=v;
    int bl=cmp(calc(u,l),calc(v,l)),br=cmp(calc(u,r),calc(v,r));
    if(bl==1||(!bl&&u<v)) pushdown(tr[now].lc,l,mid,u);
    if(br==1||(!br&&u<v)) pushdown(tr[now].rc,mid+1,r,u);
}
void modify(int &now,int l,int r,int ql,int qr,int x){
    if(!now) now=++cnt;
    if(ql<=l&&r<=qr){
        pushdown(now,l,r,x);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid) modify(tr[now].lc,l,mid,ql,qr,x);
    if(qr>mid) modify(tr[now].rc,mid+1,r,ql,qr,x);
}
P pmax(P u,P v){
    if(cmp(u.x,v.x)==1) return u;
    if(cmp(u.x,v.x)==-1) return v;
    return u.y<v.y?u:v;
}
P query(int now,int l,int r,int pos){
    if(!now) return {0,0};
    if(l==r) return {calc(tr[now].id,pos),tr[now].id};
    int mid=l+r>>1;
    if(pos<=mid) return pmax({calc(tr[now].id,pos),tr[now].id},query(tr[now].lc,l,mid,pos));
    else return pmax({calc(tr[now].id,pos),tr[now].id},query(tr[now].rc,mid+1,r,pos));
}
main(){
    n=rd;
    int lastans=0;
    while(n--){
        bool op=rd;
        if(!op){
            int k=rd;k=(k+lastans-1)%39989+1;
            wt(lastans=query(root,1,39940,k).y,'\n');
        }
        else{
            int x0=rd,y0=rd,x1=rd,y1=rd;
            x0=(x0+lastans-1)%39989+1,x1=(x1+lastans-1)%39989+1;
            y0=(y0+lastans-1)%(int)(1e9)+1,y1=(y1+lastans-1)%(int)(1e9)+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            add_edge(x0,y0,x1,y1);
            modify(root,1,39940,x0,x1,cntedge);
        }
    }
    return 0;
}