【悬2关求调】李超线段树模板Wa on #2#4~6

100pts Unaccepted

#include<bits/stdc++.h>
#define pdi pair<double,int> 
using namespace std;
const int MOD1 = 39989;
const int MOD2 = 1e9;
const int eps = 1e-9; 
const int N = 1e5+5;
int cnt = 0;
double k[N],b[N];
int s[N<<2];
void add(int x0,int y0,int x1,int y1){
    ++ cnt;
    if(x0 == x1){
        k[cnt] = 0;
        b[cnt] = max(y0,y1);
    }else{
        k[cnt] = (double)(y1-y0)/(x1-x0);
        b[cnt] = (double)y0-k[cnt]*x0;
    }
}
double solve(int cnt,int x){
    return k[cnt]*x+b[cnt];
}
int cmp(double x,double y){
    if(x - y >= eps){
        return 1;
    }else if(x - y <= -eps){
        return -1;
    }else{
        return 0;
    }
}
void change(int p,int l,int r,int u){
    int mid = (l+r)>>1;
    int &v = s[p];
    int cmid = cmp(solve(u,mid),solve(v,mid));
    if(cmid == 1 || (cmid == 0 && u < v)){// u > v;
        swap(u,v);
    }
    int cr = cmp(solve(u,r),solve(v,r));
    int cl = cmp(solve(u,l),solve(v,l));
    if(cr == 1 || (cr == 0 && u < v))change(p<<1|1,mid+1,r,u);
    if(cl == 1 || (cl == 0 && u < v))change(p<<1,l,mid,u);
}
void update(int p,int l,int r,int ll,int rr){
    if(ll == l && rr == r){
        change(p,ll,rr,cnt);
        return;
    }
    int mid = (l+r)>>1;
    if(rr <= mid){
        update(p<<1,l,mid,ll,rr); 
    }else if(ll > mid){
        update(p<<1|1,mid+1,r,ll,rr);
    }else{
        update(p<<1,l,mid,ll,mid);
        update(p<<1|1,mid+1,r,mid+1,rr);
    }
}
pdi pmax(pdi x,pdi y){
    if(cmp(x.first,y.first) == -1){
        return y;
    }else if(cmp(x.first,y.first) == 1){
        return x;
    }else if(x.second < y.second){
        return x;
    }else{
        return y;
    }
}
pdi query(int p,int l,int r,int d){
    if(d > r || d < l){
        return (pdi){0,0};
    }
    pdi ans;
    ans.first = solve(s[p],d);
    ans.second = s[p];
    int mid = (l+r)>>1;
    if(l == r){
        return ans;
    }else{
        pdi q1 = query(p<<1,l,mid,d);
        pdi q2 = query(p<<1|1,mid+1,r,d);
//      cout<<ans.first<<' '<<ans.second<<'|'<<q1.first<<' '<<q1.second<<'|'<<q2.first<<' '<<q2.second<<endl;
//      cout<<pmax(q1,q2).first<<'|'<<pmax(q1,q2).second<<endl;
        return pmax(ans,pmax(q1,q2));
    }
}
int main(){
    int n,opt,x0,y0,x1,y1,k,lastans = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&opt);
        if(opt){
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            x0 = (x0+lastans-1)%MOD1+1; x1 = (x1+lastans-1)%MOD1+1;
            y0 = (y0+lastans-1)%MOD2+1; y1 = (y1+lastans-1)%MOD2+1;
            add(x0,y0,x1,y1);
            update(1,1,MOD1,min(x0,x1),max(x0,x1));
        }else{
            scanf("%d",&k);
            k = (k+lastans-1)%MOD1+1;
            printf("%d\n",lastans = query(1,1,MOD1,k).second);
        }
    }
}

2.in:

3
1 2 1 1 1
1 1 2 2 1
0 2

2.ans:

1

2.out:

2