MnZn 我超线段树在线求条

ragwort @ 2024-08-12 08:00:47

#include <bits/stdc++.h>
// #define int long long
#define double long double
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define endl '\n' 
using namespace std;
typedef long long ll;
const int eps = 1e-9;
const int N = 1e5+5;
const int P1 = 39989;
const int P2 = 1e9;

struct line{
    double k,b;
}a[N];
int cnt;

struct node{
    int k;
    double y;
};

int s[P1<<2];

inline int cmp(double x,double y){  
    if(x == y) return -1;
    return x - y > eps;
}

inline double cal(int k,int x){
    return a[k].b + a[k].k * x;
}

inline node maxNode(node x,node y){
    int res = cmp(x.y,y.y);
    if(res == -1) return x.k<y.k ? x : y;
    return res ? x : y;
}

inline void add(int lx,int ly,int rx,int ry){
    a[++cnt] = (line){0,0};
    if(lx == rx) a[cnt].b = max(ly,ry);
    else{
        a[cnt].k = 1.0*(ry-ly)/(rx-lx);
        a[cnt].b = ly - a[cnt].k * lx;
    }
}

inline void doUpdate(int k,int l,int r,int u){
    int &v = s[k],mid = l + r >> 1;
    int res = cmp(cal(u,mid),cal(v,mid));
    if(res == 1 || res == -1 && u < v) swap(u,v);
    int resL = cmp(cal(u,l),cal(v,l)),resR = cmp(cal(u,r),cal(v,r));
    if(resL == 1 || resL == -1 && u < v) doUpdate(k<<1,l,mid,u);
    if(resR == 1 || resR == -1 && u < v) doUpdate(k<<1|1,mid+1,r,u);
}

inline void update(int k,int l,int r,int tl,int tr,int u){
    if(tl <= l && r <= tr){
        doUpdate(k,l,r,u);
        return ;
    }

    int mid = l + r >> 1;
    if(tl <= mid) update(k<<1,l,mid,tl,tr,u);
    if(tr > mid) update(k<<1|1,mid+1,r,tl,tr,u);
}

inline node query(int k,int l,int r,int t){
    if (r < t || t < l) return {0,0};

    double res = cal(s[k],t);
    if(l == r) return {s[k],res};

    int mid = l + r >> 1;
    return maxNode({s[k],res},maxNode(query(k<<1,l,mid,t),query(k<<1|1,mid+1,r,t)));
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int T;
    cin >> T;

    int lastans = 0;
    int op,x,lx,ly,rx,ry;
    while(T--){
        cin >> op;
        if(op){
            cin >> lx >> ly >> rx >> ry;

            lx = (lx+lastans-1) % P1 + 1;
            rx = (rx+lastans-1) % P1 + 1;
            ly = (ly+lastans-1) % P2 + 1;
            ry = (ry+lastans-1) % P2 + 1;

            if(lx > rx) swap(lx,rx),swap(ly,ry);
            if(lx == rx && ly > ry) swap(ly,ry);

            add(lx,ly,rx,ry);
            update(1,1,P1,lx,rx,cnt);
        }else{
            cin >> x;
            x = (x+lastans-1) % P1 + 1;
            lastans = query(1,1,P1,x).k;
            cout << lastans << endl;
        }
    }
    return 0; 
} 

by ragwort @ 2024-08-12 08:42:33

先别急

#include <bits/stdc++.h>
// #define int long long
#define double long double
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define endl '\n' 
using namespace std;
typedef long long ll;
const int eps = 1e-9;
const int N = 1e5+5;
const int P1 = 39989;
const int P2 = 1e9;

struct line{
    double k,b;
}a[N];
int cnt;

struct node{
    int k;
    double y;
};

int s[P1<<2];

inline int cmp(double x,double y){  
    if(x - y == eps) return -1;
    return x - y > eps;
}

inline double cal(int k,int x){
    return a[k].b + a[k].k * x;
}

inline node maxNode(node x,node y){
    int res = cmp(x.y,y.y);
    if(res == -1) return x.k<y.k ? x : y;
    return res ? x : y;
}

inline void add(int lx,int ly,int rx,int ry){
    a[++cnt] = (line){0,0};
    if(lx == rx) a[cnt].b = max(ly,ry);
    else{
        a[cnt].k = 1.0*(ry-ly)/(rx-lx);
        a[cnt].b = ly - a[cnt].k * lx;
    }
}

inline void doUpdate(int k,int l,int r,int u){
    int &v = s[k],mid = l + r >> 1;
    int res = cmp(cal(u,mid),cal(v,mid));
    if(res == 1 || res == -1 && u < v) swap(u,v);
    int resL = cmp(cal(u,l),cal(v,l)),resR = cmp(cal(u,r),cal(v,r));
    if(resL == 1 || resL == -1 && u < v) doUpdate(k<<1,l,mid,u);
    if(resR == 1 || resR == -1 && u < v) doUpdate(k<<1|1,mid+1,r,u);
}

inline void update(int k,int l,int r,int tl,int tr,int u){
    if(tl <= l && r <= tr){
        doUpdate(k,l,r,u);
        return ;
    }

    int mid = l + r >> 1;
    if(tl <= mid) update(k<<1,l,mid,tl,tr,u);
    if(tr > mid) update(k<<1|1,mid+1,r,tl,tr,u);
}

inline node query(int k,int l,int r,int t){
    if (r < t || t < l) return {0,0};

    double res = cal(s[k],t);
    if(l == r) return {s[k],res};

    int mid = l + r >> 1;
    return maxNode({s[k],res},maxNode(query(k<<1,l,mid,t),query(k<<1|1,mid+1,r,t)));
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int T;
    cin >> T;

    int lastans = 0;
    int op,x,lx,ly,rx,ry;
    while(T--){
        cin >> op;
        if(op){
            cin >> lx >> ly >> rx >> ry;

            lx = (lx+lastans-1) % P1 + 1;
            rx = (rx+lastans-1) % P1 + 1;
            ly = (ly+lastans-1) % P2 + 1;
            ry = (ry+lastans-1) % P2 + 1;

            if(lx > rx) swap(lx,rx),swap(ly,ry);
            if(lx == rx && ly > ry) swap(ly,ry);

            add(lx,ly,rx,ry);
            update(1,1,P1,lx,rx,cnt);
        }else{
            cin >> x;
            x = (x+lastans-1) % P1 + 1;
            lastans = query(1,1,P1,x).k;
            cout << lastans << endl;
        }
    }
    return 0; 
} 

by Kavin_0409 @ 2024-08-12 10:16:00

本题输入强制在线。

by ragwort @ 2024-08-12 10:30:36

@Kavin_0409 ？不懂

by Cyrene @ 2024-08-12 10:41:07

@ragwort 不要 define double long double，只需将k，b设为long double即可。

by Cyrene @ 2024-08-12 10:42:29

@Kavin_0409 怎么就没强制在线了

by ragwort @ 2024-08-12 10:49:58

@BernLeta 过了，谢谢您 /bx