liuziqin @ 2024-10-07 16:48:25
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod1=39989;
const int mod2=1e9;
const int N=40000;
const double eps=1e-9;
struct line{
double k,b;
};
double kth(double x0,double y0,double x1,double y1){
if(fabs(x0-x1)<=eps)return 0;
return (y0-y1)/(x0-x1);
}
double bth(double x0,double y0,double x1,double y1){
if(fabs(x0-x1)<=eps)return max(y0,y1);
return y0-x0*kth(x0,y0,x1,y1);
}
double get(double x,double k,double b){
return k*x+b;
}
struct segtree{
int sum[N<<2];
line lazy[N<<2];
bool used[N<<2];
int check(int p,int l,int r,double k1,double b1,double k2,double b2){
if(!used[p])return 1;
if(l==r){
if(get(l,k1,b1)-get(l,k2,b2)>eps)return 1;
else return -1;
}
int l1=get(l,k1,b1);
int r1=get(r,k1,b1);
int l2=get(l,k2,b2);
int r2=get(r,k2,b2);
if(fabs(l1-l2)<=eps&&fabs(r1-r2)<=eps)return -1;
if(l1-l2>eps&&r1-r2>eps)return 1;
else if((l1-l2<-eps&&r1-r2>eps)||(l1-l2>eps&&r1-r2<-eps))return 0;
else if((fabs(l1-l2)<=eps&&r1-r2>eps)||(l1-l2>eps&&fabs(r1-r2)<=eps))return 0;
else return -1;
}
void upd(int p,int l,int r,double k,double b,int id){
if(check(p,l,r,k,b,lazy[p].k,lazy[p].b)==1){
lazy[p].k=k;
lazy[p].b=b;
sum[p]=id;
used[p]=1;
return ;
}
if(l==r)return ;
int mid=(l+r)>>1;
if(check(p*2,l,mid,k,b,lazy[p].k,lazy[p].b)>=0)upd(p*2,l,mid,k,b,id);
if(check(p*2+1,mid+1,r,k,b,lazy[p].k,lazy[p].b)>=0)upd(p*2+1,mid+1,r,k,b,id);
}
void push_down(int p,int l,int r){
if(!used[p])return ;
int mid=(l+r)>>1;
upd(p*2,l,mid,lazy[p].k,lazy[p].b,sum[p]);
upd(p*2+1,mid+1,r,lazy[p].k,lazy[p].b,sum[p]);
lazy[p].k=lazy[p].b=sum[p]=0;
used[p]=0;
}
void add(int p,int l,int r,int x,int y,double k,double b,int id){
if(l>=x&&r<=y){
upd(p,l,r,k,b,id);
return ;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)add(p*2,l,mid,x,y,k,b,id);
if(mid<y)add(p*2+1,mid+1,r,x,y,k,b,id);
}
int query(int p,int l,int r,int x){
if(l==r)return sum[p];
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)return query(p*2,l,mid,x);
else return query(p*2+1,mid+1,r,x);
}
}st;
signed main(){
int q,lastans=0,n=mod1,cnt=0;
cin>>q;
while(q--){
int op,k,x0,y0,x1,y1;
cin>>op;
if(op==0){
cin>>k;
k=(k+lastans-1)%mod1+1;
lastans=st.query(1,1,n,k);
cout<<lastans<<"\n";
}
else {
cnt++;
cin>>x0>>y0>>x1>>y1;
x0=(x0+lastans-1)%mod1+1;
x1=(x1+lastans-1)%mod1+1;
y0=(y0+lastans-1)%mod2+1;
y1=(y1+lastans-1)%mod2+1;
if(x0>x1){
swap(x0,x1);
swap(y0,y1);
}
long double k=kth(x0,y0,x1,y1);
long double b=bth(x0,y0,x1,y1);
st.add(1,1,n,x0,x1,k,b,cnt);
}
}
}WA on #2 #5 #6 #14 #17
by YWHHDJSer @ 2024-10-07 17:00:36
不知道，但是还是建议检查一下精度问题，开long double试试。
by liuziqin @ 2024-10-07 17:12:17
开了，但结果一样。
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int mod1=39989;
const int mod2=1e9;
const int N=40000;
const double eps=1e-9;
struct line{
double k,b;
};
double kth(double x0,double y0,double x1,double y1){
if(fabs(x0-x1)<=eps)return 0;
return (y0-y1)/(x0-x1);
}
double bth(double x0,double y0,double x1,double y1){
if(fabs(x0-x1)<=eps)return max(y0,y1);
return y0-x0*kth(x0,y0,x1,y1);
}
double get(double x,double k,double b){
return k*x+b;
}
struct segtree{
int sum[N<<2];
line lazy[N<<2];
bool used[N<<2];
int check(int p,int l,int r,double k1,double b1,double k2,double b2){
if(!used[p])return 1;
if(l==r){
if(get(l,k1,b1)-get(l,k2,b2)>eps)return 1;
else return -1;
}
int l1=get(l,k1,b1);
int r1=get(r,k1,b1);
int l2=get(l,k2,b2);
int r2=get(r,k2,b2);
if(fabs(l1-l2)<=eps&&fabs(r1-r2)<=eps)return -1;
if(l1-l2>eps&&r1-r2>eps)return 1;
else if((l1-l2<-eps&&r1-r2>eps)||(l1-l2>eps&&r1-r2<-eps))return 0;
else if((fabs(l1-l2)<=eps&&r1-r2>eps)||(l1-l2>eps&&fabs(r1-r2)<=eps))return 0;
else return -1;
}
void upd(int p,int l,int r,double k,double b,int id){
if(check(p,l,r,k,b,lazy[p].k,lazy[p].b)==1){
lazy[p].k=k;
lazy[p].b=b;
sum[p]=id;
used[p]=1;
return ;
}
if(l==r)return ;
int mid=(l+r)>>1;
if(check(p*2,l,mid,k,b,lazy[p].k,lazy[p].b)>=0)upd(p*2,l,mid,k,b,id);
if(check(p*2+1,mid+1,r,k,b,lazy[p].k,lazy[p].b)>=0)upd(p*2+1,mid+1,r,k,b,id);
}
void push_down(int p,int l,int r){
if(!used[p])return ;
int mid=(l+r)>>1;
upd(p*2,l,mid,lazy[p].k,lazy[p].b,sum[p]);
upd(p*2+1,mid+1,r,lazy[p].k,lazy[p].b,sum[p]);
lazy[p].k=lazy[p].b=sum[p]=0;
used[p]=0;
}
void add(int p,int l,int r,int x,int y,double k,double b,int id){
if(l>=x&&r<=y){
upd(p,l,r,k,b,id);
return ;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)add(p*2,l,mid,x,y,k,b,id);
if(mid<y)add(p*2+1,mid+1,r,x,y,k,b,id);
}
int query(int p,int l,int r,int x){
if(l==r)return sum[p];
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)return query(p*2,l,mid,x);
else return query(p*2+1,mid+1,r,x);
}
}st;
signed main(){
int q,lastans=0,n=mod1,cnt=0;
cin>>q;
while(q--){
int op,k,x0,y0,x1,y1;
cin>>op;
if(op==0){
cin>>k;
k=(k+lastans-1)%mod1+1;
lastans=st.query(1,1,n,k);
cout<<lastans<<"\n";
}
else {
cnt++;
cin>>x0>>y0>>x1>>y1;
x0=(x0+lastans-1)%mod1+1;
x1=(x1+lastans-1)%mod1+1;
y0=(y0+lastans-1)%mod2+1;
y1=(y1+lastans-1)%mod2+1;
if(x0>x1){
swap(x0,x1);
swap(y0,y1);
}
double k=kth(x0,y0,x1,y1);
double b=bth(x0,y0,x1,y1);
st.add(1,1,n,x0,x1,k,b,cnt);
}
}
}by liuziqin @ 2024-10-07 17:12:38
@YWHHDJSer
by YWHHDJSer @ 2024-10-07 17:28:12
看一下是不是upd的锅，感觉是不是分讨的情况少了。一个区间保留的优势线段是在该区间占有一半及以上优势区的线段，所以有时保留有一定缺陷的线段（雾。
总之感觉是upd的问题。
by YWHHDJSer @ 2024-10-07 17:28:22
@liuziqin
by liuziqin @ 2024-10-07 20:17:09
此贴结。
死因：double敲成了int
by wjy2020 @ 2024-10-07 21:14:12
@liuziqin
补充：lazy传递时没有默认传编号最小的线段