萌新求助李超树

Cocoly1990 @ 2022-06-14 10:10:12

by Cocoly1990 @ 2022-06-14 10:10:37

#include<bits/stdc++.h>
using namespace std;
#define Maxn 1000007
#define int long long
struct Node{
    double k; double b;int id;
}T[Maxn << 2];
double lv(int x0,int x_1,double y0,double y_1)
{
    return (double)(y_1 - y0) / (1.0 * x_1 - 1.0 * x0);
}
int ls(int x){return x << 1;}
int rs(int x){return x << 1 | 1;}
double f(double kkk, double bbb, int xx){
    return 1.0 * xx * kkk + bbb;
}
void insert(int p, int l, int r, double K, double B, int Id){
    //cout << l << " " << r << " " << K << " " << B << " " << Id << endl;
    int mid = (l + r) >> 1;
    double fl = f(T[p].k, T[p].b, l); double fr = f(T[p].k, T[p].b, r);
    double gl = f(K, B, l); double gr = f(K, B, r);
    double fm = f(T[p].k, T[p].b, mid);
    double gm = f(K, B, mid);   
    if(gl <= fl && gr <= fr) return;
    if(gl >= fl && gr >= fr){
        T[p].k = K, T[p].b = B, T[p].id = Id; return;
    }
    if(gm > fm) swap(T[p].k, K), swap(T[p].b, B), swap(T[p].id, Id);
    if(K < T[p].k) insert(ls(p), l, mid, K, B, Id);
    else insert(rs(p), mid + 1, r, K, B, Id);
}
void update(int ql, int qr, int l, int r, int p, double K, double B, int Id){
    //cout << l << " " << r << "\n";
    if(ql <= l && r <= qr){insert(p, l, r, K, B, Id); return;}
    int mid = (l + r) >> 1;
    if(ql <= mid) update(ql, qr, l, mid, ls(p), K, B, Id);
    if(qr > mid) update(ql, qr, mid + 1, r, rs(p), K, B, Id);
    return;
}
pair<double, int> ask(int l, int r, int p, int x){
    //cout << p << "\n";
    double res = 1.0 * T[p].k * x + T[p].b;
    int pos = T[p].id;
    int mid = (l + r) >> 1;
    //cout << l << " " << r << " " << res << " " << pos << endl;
    if(l == r) return make_pair(res, pos);
    if(x <= mid){
        pair<double, int> qwq = ask(l, mid, ls(p), x);
        if(qwq.first > res || (qwq.first == res && qwq.second < pos)){
            res = qwq.first, pos = qwq.second;
        }
    }
    if(x > mid){
        pair<double, int> qwq = ask(mid + 1, r, rs(p), x);
        if(qwq.first > res || (qwq.first == res && qwq.second < pos)){
            res = qwq.first, pos = qwq.second;
        }
    }
    return make_pair(res, pos); 
}
int n, last;
int opt, tot;
signed main(){
    cin >> n;
    //cout << lv(1.0, 2.0, 5.0 ,10.0) << endl;
    for(int i = 1; i <= n; i ++){
        cin >> opt;
        //cout << opt << "\n";
        if(opt == 0){
            int xx;
            cin >> xx;
            //cout << opt << "\n";
            xx = ((xx + last - 1) % 39989) + 1;
            //cout << xx << "\n";
            pair<double, int> kel;
            kel = ask(1, Maxn, 1, xx);
            last = kel.second;
            cout << last << endl;
        }else{
            int x0, y0, x_1, y_1;
            cin >> x0 >> y0 >> x_1 >> y_1;
            x0 = ((x0 + last - 1) % 39989) + 1;
            y0 = ((y0 + last - 1) % 39989) + 1;
            x_1 = ((x_1 + last - 1) % 1000000000) + 1;
            y_1 = ((y_1 + last - 1) % 1000000000) + 1;
            double kk = lv(x0, x_1, 1.0 * y0, 1.0 * y_1);
            double bb = y0 - 1.0 * kk * x0;
            update(min(x0, x_1), max(x0, x_1), 1, Maxn, 1, kk, bb, ++ tot);
        }
    }
}

by Renshey @ 2022-06-14 11:21:57

提示

不保证 x_0\ne x_1。