rt

我怎么证都是应该开 $x$ 的取值范围（$[1,40000]$）的两倍就够了，而且线段树数组开两倍交上去也AC了

但还是有点怀疑自己是不是证错了

代码：（这一份是我的复习版代码，所以可能多少带点注释……QAQ）

#include<bits/stdc++.h>
#define int long long
#define N 100005
#define X 40005
#define esp 1e-8
#define modx 39989
#define mody 1000000000
using namespace std;
int n,bh,cnt,ans,no;
double cal(int,int);
struct tree{
    int l,r,id;
}tr[X<<1];//只需要开x的取值范围的倍即可
struct E{
    double st,k;
    E(double a=0,double b=0){ st=a,k=b;}
}e[N];
int ask(int,int,int,int);
void insert(int&,int,int,int,int,int);
bool com(int,int,int);
signed main(){
    scanf("%lld",&n);
    while(n--){
        int op,k,x0,x1,y0,y1;
        scanf("%lld",&op);
        if(!op)
            scanf("%lld",&k),
            ans=ask(1,1,X,(k+ans-1)%modx+1),
            printf("%lld\n",ans);
        else{
            scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
            x0=(x0+ans-1)%modx+1,x1=(x1+ans-1)%modx+1;
            y0=(y0+ans-1)%mody+1,y1=(y1+ans-1)%mody+1;
            if(x0>x1)
                swap(x0,x1),swap(y0,y1);
            if(x0==x1)
                e[++cnt]=E(max(y1,y0),0);//这里记得取max
            else{
                double k=1.0*(y1-y0)/(x1-x0);//记得转double
                e[++cnt]=E(1.0*y0-1.0*x0*k/*这里记得减去x0*k，不然后面计算时会算两遍x0*k！！！*/,k);
            }
            insert(no,1,X,x0,x1,cnt);
        }
    }
    return 0;
}
bool com(int a,int b,int x){//若线段a比线段b更优，则返回true
    double num1=cal(a,x),num2=cal(b,x);
    if(abs(num1-num2)<esp)//减小被卡精度的可能
        return a<b;
    return num1>num2;
}
double cal(int id,int x){
    return 1.0*e[id].k*x+e[id].st;//老生常谈转double
}
int ask(int no,int l,int r,int x){
    if(!no) return 0;//若该区间不存在线段，则直接返回
    if(l==r) return tr[no].id;
    int ans=0,mi=l+r>>1;
    if(x<=mi)//不断地取点x经过的区间中的最优线段
        ans=ask(tr[no].l,l,mi,x);
    else
        ans=ask(tr[no].r,mi+1,r,x);
    if(com(tr[no].id,ans,x))//之前经过的小区间的最优线段与当前区间的最优线段进行比较
        ans=tr[no].id;
    return ans;
}
void insert(int &no,int l,int r,int x1,int x2,int id){
    if(!no)
        no=++bh;//若当前区间没有编号，则给当前区间进行编号，记得打函数参数中的“&”，不然改了之后返回之前的区间就等于啥也没改了！！！
    int mi=l+r>>1;
    if(x1<=l&&x2>=r){
        if(com(tr[no].id,id,l)&&com(tr[no].id,id,r))
            return ;//左右两边都不优，直接舍
        if(com(id,tr[no].id,l)&&com(id,tr[no].id,r)){//左右两边都为当前最优，则用线段id直接覆盖该区间
            tr[no].id=id;
            return ;
        }
        if(com(id,tr[no].id,mi)) swap(tr[no].id,id);//若线段id在mid处更优，则更新no的线段，并判断线段id在左右两子区间是否可能更优
        if(com(id,tr[no].id,l)) insert(tr[no].l,l,mi,x1,x2,id);
        //左端点更大，可能取到更优；
        //注意！这里不能判断左区间的mid值，因为即使左区间的mid处值更劣，线段id也可能在左区间的子区间的mid处更优
        else insert(tr[no].r,mi+1,r,x1,x2,id);
    }
    else{
        if(x1<=mi)
            insert(tr[no].l,l,mi,x1,x2,id);
        if(x2>mi)
            insert(tr[no].r,mi+1,r,x1,x2,id);
    }
}