WA #2 #6

看过这个帖子了

https://www.luogu.com.cn/discuss/831250

但是问题好像不在这里，快调成和oiwiki上代码一样了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 100010;
const int mod1 = 39989, mod2 = 1e9;
const double eps = 1e-9;
const int MAXT = 40000;
typedef pair<double,int> PII;
int cmp(double x, double y) {
    if(x-y > eps) {
        return 1;
    }
    if(y-x > eps) {
        return -1;
    }
    return 0;
}
int tree[maxn];
int dian[maxn];
int s[maxn];
struct node{
    double k, b;
}xian[maxn];
int cnt;
int lastans;
double calc(int id, int d) {
    return xian[id].k * d + xian[id].b;
}
void add(int x0, int y0, int x1, int y1) {
    if(x0 == x1) {
        xian[++cnt].k = 0;
        xian[cnt].b = max(y0, y1);
    } else {
        xian[++cnt].k = 1.0 * (y1 - y0) / (x1 - x0);
        xian[cnt].b = y0 - xian[cnt].k * x0;
    }
}
void upd(int root, int cl, int cr, int u) {
    int &v = s[root], mid = cl + cr >> 1;
    int bmid = cmp(calc(u, mid), calc(v, mid));
    if (bmid == 1 || (!bmid and u < v)) swap(u, v);
    int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
    if (bl == 1 or (!bl and u < v)) upd(root*2, cl, mid, u);
    if (br == 1 or (!bl and u < v)) upd(root*2+1, mid+1, cr, u); 
}
void update(int root, int cl, int cr, int l, int r, int u) {

    if(l <= cl and cr <= r) {
        upd(root, cl, cr, u);
        return;
    }
    int mid = cl + cr >> 1;
    if(l <= mid) {
        update(root * 2, cl, mid, l, r, u);
    }
    if(r > mid) {
        update(root * 2 + 1, mid+1, cr, l, r, u);
    }
}
PII pmax(PII x, PII y) {  // pair max函数
  if (cmp(x.first, y.first) == -1)
    return y;
  else if (cmp(x.first, y.first) == 1)
    return x;
  else
    return x.second < y.second ? x : y;
}
PII query(int idx, int l, int r, int wh) {
    if(r < wh or l > wh) return {0, 0};
    int mid = l + r >> 1;
    double res = calc(s[idx], wh);
    if(l == r) {
        return {res, s[idx]};
    } 
    return pmax({res, s[idx]}, pmax(query(idx*2, l, mid, wh), query(idx*2+1, mid+1, r, wh)));
} 
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
        int opt; cin >> opt;
        if(opt == 1) {
            int x0, y0, x1, y1;
            cin >> x0 >> y0 >> x1 >> y1;
            x0 = (x0 + lastans - 1 + mod1) % mod1 + 1;
            x1 = (x1 + lastans - 1 + mod1) % mod1 + 1;
            y0 = (y0 + lastans - 1 + mod2) % mod2 + 1;
            y1 = (y1 + lastans - 1 + mod2) % mod2 + 1;
            if(x0 > x1) {
                swap(x0, x1); swap(y0, y1);
            }
            add(x0, y0, x1, y1);
            update(1, 1, mod1, x0, x1, cnt);
        } else {
            int k; cin >> k;
            k = (k + lastans - 1 + mod1) % mod1 + 1;
            cout << (lastans = query(1, 1, mod1, k).second) << endl;
        }
    }
    return 0;
}