满屏re,求调
查看原帖
满屏re,求调
1147688
Ming3398楼主2025/7/3 15:08
#include<bits/stdc++.h>
#define double long double
#define eps 1e-8
using namespace std;
typedef pair<double,int> Pair;
const int mod1=39989,mod2=1e9,N=1e5+10,S=1e4+10;
int ans=0;
void cl(int &x,int m){
	x=(x+ans-1)%m+1;
}

int idx=0;
struct node{
	int l,r;
	int maxn;
	#define l(q) tree[q].l
	#define r(q) tree[q].r
	#define maxn(q) tree[q].maxn
}tree[S<<2];
struct line{
	double k,b;
}p[N];
void add(int x0,int y0,int x1,int y1){
	idx++;
	if(x0==x1){
		p[idx].k=0;
		p[idx].b=max(y0,y1);
	}
	else{
		p[idx].k=(y1-y0)*1.0/(x1-x0);
		p[idx].b=y0*1.0-x0*1.0*p[idx].k;	
	}
}
double calc(int tp,int x){
	return p[tp].k*x+p[tp].b;
} 
void build(int q,int l,int r){
	maxn(q)=0; 
	l(q)=l;r(q)=r;
	if(l==r) return ;
	int mid=l+r>>1;
	build(q<<1,l,mid);
	build(q<<1|1,mid+1,r);
} 
int cmp(double a,double b){
	if(a-b>eps) return 1;
	else if(b-a>eps) return -1;
	return 0;
}
void upd(int q,int u){
	int &v=maxn(q),l=l(q),r=r(q);
	int mid=l+r>>1;
	
	int m1=cmp(calc(u,mid),calc(v,mid));
	int l1=cmp(calc(u,l),calc(v,l));
	int r1=cmp(calc(u,r),calc(v,r));
	
	if(m1==1||(m1==0&&u<v)) swap(u,v);//////////////important
	if(l1==1||(l1==0&&u<v)) upd(q<<1,u);
	if(r1==1||(r1==0&&u<v)) upd(q<<1|1,u);
}
void update(int q,int L,int R,int tp){
	int l=l(q),r=r(q);
	
	if(L<=l&&r<=R){
		upd(q,tp);
		return ;
	}
	int mid=l+r>>1;
	if(L<=mid) update(q<<1,L,R,tp);
	if(mid<R) update(q<<1|1,L,R,tp);
} 
Pair pmax(Pair a,Pair b){
	if(cmp(a.first,b.first)==1) return a;
	else if(cmp(a.first,b.first)==-1) return b;
	else return a.second<b.second? a:b;
}
Pair query(int q,int x){
	int l=l(q),r=r(q);
	if(l>x||r<x) return {0,0};
	int mid=l+r>>1;
	double res=calc(maxn(q),x);
	Pair now={res,maxn(q)};
	if(l==r) return now;
	return pmax(now,pmax(query(q<<1,x),query(q<<1|1,x)));
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;cin>>n;
	build(1,1,mod1);
	for(int i=1;i<=n;i++){
		int op;cin>>op;
		if(op==1){
			int x0,y0,x1,y1;cin>>x0>>y0>>x1>>y1;
			cl(x0,mod1);cl(y0,mod2);cl(x1,mod1);cl(y1,mod2);
			if(x0>x1){
				swap(x0,x1);swap(y0,y1);
			}
			add(x0,y0,x1,y1);
			update(1,x0,x1,idx);
		}
		else{
			int x;cin>>x;cl(x,mod1);
			ans=query(1,x).second;
			cout<<ans<<"\n";
		}
	}
	return 0;
}
2025/7/3 15:08
加载中...