@[vicky128](/user/177000)
~~码风再紧凑一点就和我一样了~~
你没有证错。它不需要笼统建树，但是点数最多也就 $2n-1$ 个。
实际上动态开点线段树开点个数是 $\min(q\log n,2n-1)$ 的。
另外，这是我的代码：
```cpp
#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 SMT0x400 @ 2023-09-20 22:31:02
蛙趣 你代码怎么比我还短
~~呜呜呜~~
by SMT0x400 @ 2023-09-20 22:33:05
@[SMT0x400](/user/121995)
阿里嘎多！
另：你的代码七十多行我的代码九十多行你是怎么学的比大小的啊？
by vicky128 @ 2023-09-21 16:05:42
@[vicky128](/user/177000)
重构了一下
可以做到三十五行了
```cpp
#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 SMT0x400 @ 2023-09-21 17:11:18
@[SMT0x400](/user/121995) 你这马蜂……
~~如读~~
by vicky128 @ 2023-09-21 17:21:21