萌新求调李超树 & 灵异事件

rt.

过了 subtask0（hack 数据），但是 subtask1 只过了前 3 个点/kk

而将线段树的数组大小改成 x 的值域*4 后 subtask1 就会全 RE。

感觉很灵异求助/ll

#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
void file_IO() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
bool M1;
const ld eps=1e-9;
const int N=1e5+5,M=4e4+5,X=39989,Y=1e9;
struct LiChaoTree {
    struct line {
        ld k,b;
    }; line val[N];
    int p;
    int new_node(int ax,int ay,int bx,int by) {
        int k=++p;
        if(ax==bx) {
            val[k].k=0;
            val[k].b=max(ay,by);
        } else {
            val[k].k=1.0*(ay-by)/(ax-bx);
            val[k].b=1.0*ay-1.0*val[k].k*ax;
        }
        return k;
    }
    ld calc(int k,int x) {
        if(!k)
            return -INFLL;
        return val[k].k*x+val[k].b;
    }
    bool cmp(ld x,ld y,int u,int v) {
        return (x-y>eps||(y-x<eps&&u<v));
    }
    struct node {
        int l,r,x;
    }; node tree[N<<2]; //如果这里改成 M<<2 就会 RE，但是感觉开 M<<2 很对啊？
    #define ls(k) (k<<1)
    #define rs(k) (k<<1|1)
    void build(int k,int l,int r) {
        tree[k].l=l; tree[k].r=r;
        if(l==r)
            return;
        int mid=(l+r)>>1;
        build(ls(k),l,mid);
        build(rs(k),mid+1,r);
    }
    void upd(int k,int u) {
        int &v=tree[k].x;
        if(cmp(calc(u,tree[ls(k)].r),calc(v,tree[ls(k)].r),u,v))
            swap(u,v);
        if(tree[k].l==tree[k].r)
            return;
        if(cmp(calc(u,tree[k].l),calc(v,tree[k].l),u,v))
            upd(ls(k),u);
        if(cmp(calc(u,tree[k].r),calc(v,tree[k].r),u,v))
            upd(rs(k),u);
    }
    void update(int k,int ql,int qr,int u) {
        if(ql<=tree[k].l&&tree[k].r<=qr) {
            upd(k,u);
            return;
        }
        if(ql<=tree[ls(k)].r)
            update(ls(k),ql,qr,u);
        if(qr>=tree[rs(k)].l)
            update(rs(k),ql,qr,u);
    }
    int query(int k,int qx) {
        if(tree[k].l==tree[k].r)
            return tree[k].x;
        int u=tree[k].x,v=0;
        if(qx<=tree[ls(k)].r)
            v=query(ls(k),qx);
        else
            v=query(rs(k),qx);
        return cmp(calc(u,qx),calc(v,qx),u,v)? u:v;
    }
    void ins(int ax,int ay,int bx,int by) {
        if(ax>bx) {
            swap(ax,bx);
            swap(ay,by);
        }
        update(1,ax,bx,new_node(ax,ay,bx,by));
    }
    int query(int x) {
        return query(1,x);
    }
    #undef ls
    #undef rs
}; LiChaoTree T;
void solve() {
    int q;
    scanf("%d",&q);
    T.build(1,1,X);
    int ans=0;
    while(q--) {
        int op;
        scanf("%d",&op);
        if(op==0) {
            int x;
            scanf("%d",&x);
            x=(x+ans-1)%X+1;
            printf("%d\n",ans=T.query(x));
        } else {
            int ax,ay,bx,by;
            scanf("%d%d%d%d",&ax,&ay,&bx,&by);
            ax=(ax+ans-1)%X+1;
            ay=(ay+ans-1)%Y+1;
            bx=(bx+ans-1)%X+1;
            by=(by+ans-1)%Y+1;
            T.ins(ax,ay,bx,by);
        }
    }
}
bool M2;
signed main() {
    //file_IO();
    int testcase=1;
    //scanf("%d",&testcase);
    while(testcase--)
        solve();
    cerr<<"used time = "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
    cerr<<"used memory = "<<(&M1-&M2)/1024/1024<<"MB\n";
    return 0;
}