1 条题解

  • 0
    @ 2026-8-11 15:00:03

    #include<map>
    #include<queue>
    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 50005
    #define MAXM 100005
    #define LL long long
    #define DB double
    #define ENDL putchar('\n')
    #define lowbit(x) ((-x)&(x))
    //#define int LL
    //#pragma GCC optimize(2)
    LL read() {
        LL f = 1,x = 0;char s = getchar();
        while(s < '0' || s > '9') {if(s=='-')f=-f;s = getchar();}
        while(s >= '0' && s <= '9') {x=x*10+(s-'0');s=getchar();}
        return f*x;
    }
    const int MOD = 998244353;
    int n,m,i,j,s,o,k;
    struct it{
    	DB x,y;
    	it(){x = y = 0;}
    	it(DB X,DB Y){x=X;y=Y;}
    };
    it cg(it a,it b) {
    	DB k = (a.y - b.y) / (a.x - b.x);
    	DB B = a.y - a.x * k;
    	return it(k,B);
    }
    it jd(it a,it b) {
    	DB xx = (b.y - a.y) / (a.x - b.x);
    	return it(xx,a.x*xx+a.y);
    }
    bool abov(it a,it st) {
    	DB y2 = a.x * st.x + st.y;
    	return a.y >= y2;
    }
    bool operator < (it a,it b) {return a.y < b.y;}
    bool operator > (it a,it b) {return b < a;}
    bool operator <= (it a,it b) {return a.y <= b.y;}
    bool operator >= (it a,it b) {return b <= a;}
    struct tr{
    	int l,r;
    	it st;
    	tr(){l=r=0;st=it(0,-1e9);}
    }tre[MAXM<<4];
    void maketree(int a,int l,int r) {
    	tre[a].l = l;tre[a].r = r;
    	if(l < r) {
    		int mid = (l+r)>>1;
    		maketree(a<<1,l,mid);
    		maketree(a<<1|1,mid+1,r);
    	}
    	return ;
    }
    void addtree(int a,int l,int r,it st) {
    	if(tre[a].l > r || tre[a].r < l) return ;
    	if(tre[a].l >= l && tre[a].r <= r) {
    		DB ll = (DB)tre[a].l,rr = (DB)tre[a].r;
    		it l1 = it(ll,ll*tre[a].st.x+tre[a].st.y);
    		it r1 = it(rr,rr*tre[a].st.x+tre[a].st.y);
    		it l2 = it(ll,ll*st.x+st.y),r2 = it(rr,rr*st.x+st.y);
    		if(l1 >= l2 && r1 >= r2) return ;
    		if(l2 >= l1 && r2 >= r1) {
    			tre[a].st = st; return ;
    		}
    		it md = jd(st,tre[a].st); int mid = (tre[a].l+tre[a].r)>>1;
    		it ls = (l1 >= l2 ? tre[a].st:st),rs = (r1 >= r2 ? tre[a].st:st);
    		if(md.x <= (DB)mid) tre[a].st = rs,addtree(a<<1,l,r,ls);
    		else tre[a].st = ls,addtree(a<<1|1,l,r,rs);
    		return ;
    	}
    	addtree(a<<1,l,r,st);addtree(a<<1|1,l,r,st);
    	return ;
    }
    DB query(int a,int ad) {
    	if(tre[a].l > ad || tre[a].r < ad) return -1e9;
    	if(tre[a].l == tre[a].r) {
    		return ad*tre[a].st.x + tre[a].st.y;
    	}
    	return max(ad*tre[a].st.x+tre[a].st.y,max(query(a<<1,ad),query(a<<1|1,ad)));
    }
    int main() {
    	n = read();m = read();
    	maketree(1,1,100000);
    	for(int i = 1;i <= n;i ++) {
    		it a,b;
    		a.x = (DB)read();
    		a.y = (DB)read();
    		b.x = (DB)read();
    		b.y = (DB)read();
    		if(a.x > b.x) swap(a,b);
    		it st;
    		if(a.x == b.x) st = it(0,max(a.y,b.y));
    		else st = cg(a,b);
    		int ll = (int)a.x,rr = (int)b.x;
    		addtree(1,ll,rr,st);
    	}
    	for(int i = 1;i <= m;i ++) {
    		k = read();
    		if(!k) {
    			it a,b;
    			a.x = (DB)read();
    			a.y = (DB)read();
    			b.x = (DB)read();
    			b.y = (DB)read();
    			if(a.x > b.x) swap(a,b);
    			it st;
    			if(a.x == b.x) st = it(0,max(a.y,b.y));
    			else st = cg(a,b);
    			int ll = (int)a.x,rr = (int)b.x;
    			addtree(1,ll,rr,st);
    		}
    		else {
    			int x0 = read();
    			DB ans = query(1,x0);
    			printf("%.4f\n",ans < -1e8 ? 0.0:ans);
    		}
    	}
        return 0;
    }
    
    • 1

    「雅礼集训 2017 Day2」线段游戏

    信息

    ID
    10092
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    14
    已通过
    3
    上传者