vicky2048_2 @ 2023-09-20 22:20:27
rt
我怎么证都是应该开
但还是有点怀疑自己是不是证错了
代码：（这一份是我的复习版代码，所以可能多少带点注释……QAQ）
#include<bits/stdc++.h>
#define int long long
#define N 100005
#define X 40005
#define esp 1e-8
#define modx 39989
#define mody 1000000000
using namespace std;
int n,bh,cnt,ans,no;
double cal(int,int);
struct tree{
int l,r,id;
}tr[X<<1];//只需要开x的取值范围的倍即可
struct E{
double st,k;
E(double a=0,double b=0){ st=a,k=b;}
}e[N];
int ask(int,int,int,int);
void insert(int&,int,int,int,int,int);
bool com(int,int,int);
signed main(){
scanf("%lld",&n);
while(n--){
int op,k,x0,x1,y0,y1;
scanf("%lld",&op);
if(!op)
scanf("%lld",&k),
ans=ask(1,1,X,(k+ans-1)%modx+1),
printf("%lld\n",ans);
else{
scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
x0=(x0+ans-1)%modx+1,x1=(x1+ans-1)%modx+1;
y0=(y0+ans-1)%mody+1,y1=(y1+ans-1)%mody+1;
if(x0>x1)
swap(x0,x1),swap(y0,y1);
if(x0==x1)
e[++cnt]=E(max(y1,y0),0);//这里记得取max
else{
double k=1.0*(y1-y0)/(x1-x0);//记得转double
e[++cnt]=E(1.0*y0-1.0*x0*k/*这里记得减去x0*k，不然后面计算时会算两遍x0*k！！！*/,k);
}
insert(no,1,X,x0,x1,cnt);
}
}
return 0;
}
bool com(int a,int b,int x){//若线段a比线段b更优，则返回true
double num1=cal(a,x),num2=cal(b,x);
if(abs(num1-num2)<esp)//减小被卡精度的可能
return a<b;
return num1>num2;
}
double cal(int id,int x){
return 1.0*e[id].k*x+e[id].st;//老生常谈转double
}
int ask(int no,int l,int r,int x){
if(!no) return 0;//若该区间不存在线段，则直接返回
if(l==r) return tr[no].id;
int ans=0,mi=l+r>>1;
if(x<=mi)//不断地取点x经过的区间中的最优线段
ans=ask(tr[no].l,l,mi,x);
else
ans=ask(tr[no].r,mi+1,r,x);
if(com(tr[no].id,ans,x))//之前经过的小区间的最优线段与当前区间的最优线段进行比较
ans=tr[no].id;
return ans;
}
void insert(int &no,int l,int r,int x1,int x2,int id){
if(!no)
no=++bh;//若当前区间没有编号，则给当前区间进行编号，记得打函数参数中的“&”，不然改了之后返回之前的区间就等于啥也没改了！！！
int mi=l+r>>1;
if(x1<=l&&x2>=r){
if(com(tr[no].id,id,l)&&com(tr[no].id,id,r))
return ;//左右两边都不优，直接舍
if(com(id,tr[no].id,l)&&com(id,tr[no].id,r)){//左右两边都为当前最优，则用线段id直接覆盖该区间
tr[no].id=id;
return ;
}
if(com(id,tr[no].id,mi)) swap(tr[no].id,id);//若线段id在mid处更优，则更新no的线段，并判断线段id在左右两子区间是否可能更优
if(com(id,tr[no].id,l)) insert(tr[no].l,l,mi,x1,x2,id);
//左端点更大，可能取到更优；
//注意！这里不能判断左区间的mid值，因为即使左区间的mid处值更劣，线段id也可能在左区间的子区间的mid处更优
else insert(tr[no].r,mi+1,r,x1,x2,id);
}
else{
if(x1<=mi)
insert(tr[no].l,l,mi,x1,x2,id);
if(x2>mi)
insert(tr[no].r,mi+1,r,x1,x2,id);
}
}by CrTsIr400 @ 2023-09-20 22:31:02
@vicky128
码风再紧凑一点就和我一样了
你没有证错。它不需要笼统建树，但是点数最多也就
实际上动态开点线段树开点个数是
另外，这是我的代码：
#include<bits/stdc++.h>
#define fo(i,a,b) for(I i=a;i<=b;++i)
#define fd(i,a,b) for(I i=a;i>=b;--i)
using namespace std;typedef int I;typedef long long LL;const I inf=0x3f3f3f3f;I FL,CH;template<typename T>void in(T&a){for(FL=1;!isdigit(CH)&&CH!=EOF;CH=getchar())FL=(CH=='-')?-1:1;for(a=0;isdigit(CH);CH=getchar())a=a*10+CH-'0';a*=FL;}template<typename T,typename...Args>void in(T&a,Args&...args){in(a);in(args...);}
typedef double DB;
const I N=1e5+10,M=N<<1,W=4e4+10;
struct line{
DB k,b;
line(){k=0;b=-inf;}
void init(I ax,I ay,I bx,I by){
if(ax==bx)b=max(ay,by),k=0;
else k=1.0*(ay-by)/(ax-bx),b=ay-ax*k;
}
}S[N];
const double eps=1e-9;
DB g(I&id,I x){
return S[id].k*x+S[id].b;}
I ls[M],rs[M],cnt,rt,sge[M];
I eq(DB x,DB y){
if(x-y>eps)return 1;
if(y-x>eps)return -1;
return 0;
}void upd(I&p,I a,I l,I r){
if(!p)p=++cnt;
I&b=sge[p],mid=l+r>>1;
I rs1=eq(g(a,l),g(b,l)),rs2=eq(g(a,r),g(b,r));
if(rs1>0&&rs2>0){b=a;return;}
if(rs1<=0&&rs2<=0){return;}
if(l==r)return;
upd(ls[p],a,l,mid);
upd(rs[p],a,mid+1,r);
}void chg(I&p,I cl,I cr,I a,I l,I r){
if(!p)p=++cnt;
if(r<cl||l>cr)return;
if(cl<=l&&r<=cr){
upd(p,a,l,r);
return;
}I mid=l+r>>1;
chg(ls[p],cl,cr,a,l,mid);
chg(rs[p],cl,cr,a,mid+1,r);
}void qry(I&p,I qx,I&qans,I l,I r){
if(qx<l||qx>r)return;
if(eq(g(qans,qx),g(sge[p],qx))<0)qans=sge[p];
if(eq(g(qans,qx),g(sge[p],qx))==0)qans=min(qans,sge[p]);
if(l==r)return;
I mid=l+r>>1;
qry(ls[p],qx,qans,l,mid);
qry(rs[p],qx,qans,mid+1,r);
}
I lans,n,m;
const I E9=1000000000;
void fix(I&p){
p=(p+lans-1)%39989+1;
}void fixy(I&y){
y=(y+lans-1)%E9+1;
}
I main(){
in(n);
fo(i,1,n){I op,a,b,c,d,k;
in(op);
if(!op){
in(k);
fix(k);
lans=0;
qry(rt,k,lans,1,W);
printf("%d\n",lans);
}else{
in(a,b,c,d);
fix(a);fixy(b);fix(c);fixy(d);
if(a>c)swap(a,c),swap(b,d);
S[++m].init(a,b,c,d);
chg(rt,a,c,m,1,W);
}
}
return 0;
}by CrTsIr400 @ 2023-09-20 22:33:05
蛙趣 你代码怎么比我还短
呜呜呜
by vicky2048_2 @ 2023-09-21 16:05:42
@SMT0x400
阿里嘎多！
另：你的代码七十多行我的代码九十多行你是怎么学的比大小的啊？
by CrTsIr400 @ 2023-09-21 17:11:18
@vicky128
重构了一下
可以做到三十五行了
#include<cstdio>
using I=int;using LL=long long;using V=void;using DB=double;
const I W=40000,N=1e5+10;
const DB eps=1e-8,inf=1e18;
#define ci const int
I jian(DB a,DB b){return a-=b,a<-eps?-1:(a>eps?1:0);}
struct line{DB k,b;
line(){k=-inf;b=-inf;}
line(ci&sx,ci&sy,ci&ex,ci&ey){
if(jian(ex,sx)==0)k=0,b=ey>sy?ey:sy;
else k=1.0*(ey-sy)/(ex-sx),b=sy-k*sx;}
}li[N];I lin;
DB gt(ci&id,ci&x){return li[id].k*x+li[id].b;}
I ls[W<<1],rs[W<<1],dm[W<<1],cnt,rt;
V upd(I&p,ci&b,I l=1,I r=W){
I&a=dm[(!p&&(p=++cnt)),p],cmpl=jian(gt(a,l),gt(b,l)),cmpr=jian(gt(a,r),gt(b,r)),mid=(l+r)>>1;
if(cmpl<0&&cmpr<0)return(V)(a=b);
return (V)((!((cmpl>=0&&cmpr>=0)||l==r))&&(upd(ls[p],b,l,mid),upd(rs[p],b,mid+1,r),1));}
V chg(I&p,ci&b,ci&cl,ci&cr,I l=1,I r=W){I mid=(l+r)>>1;
if((!p&&(p=++cnt)),l>cr||r<cl)return;
return (cl<=l&&r<=cr)?upd(p,b,l,r):(chg(ls[p],b,cl,cr,l,mid),chg(rs[p],b,cl,cr,mid+1,r));}
I qry(I&p,ci&x,I l=1,I r=W){
if(r<x||l>x||!p)return 0;
I ans=dm[p],mid=(l+r)>>1,la=qry(ls[p],x,l,mid),ra=qry(rs[p],x,mid+1,r),lgt,rgt;
if((lgt=jian(gt(ans,x),gt(la,x)))<0||(lgt==0&&la<ans))ans=la;
if((rgt=jian(gt(ans,x),gt(ra,x)))<0||(rgt==0&&ra<ans))ans=ra;
return ans;}
I n,lans;
V fx(I&x){x=(x+lans-1)%39989+1;}
V fy(I&y){y=(y+lans-1)%(I(1e9))+1;}
I main(){scanf("%d",&n);lans=0;
for(;n--;){I op,x0,y0,x1,y1,k;scanf("%d",&op);
if(op==1)scanf("%d%d%d%d",&x0,&y0,&x1,&y1),fx(x0),fx(x1),fy(y0),fy(y1),li[++lin]=line(x0,y0,x1,y1),(x0>x1&&(x0^=x1^=x0^=x1)),chg(rt,lin,x0,x1);
else scanf("%d",&k),fx(k),printf("%d\n",lans=qry(rt,k));}
return 0;}by vicky2048_2 @ 2023-09-21 17:21:21
@SMT0x400 你这马蜂……
如读