题解 P4097 【[HEOI2013]Segment 】

写一篇比较易于理解的题解 线段树的每个节点维护该线段的最优编号 用标记永久化 先锁定线段的位置 在将不优线段下放 （只是代表当前不优（即没有站到区间的1/2）） 其实本题的细节很多。。。 但是数据很水。。。。 并且以前有大佬的复杂度有问题都可以AC。。 double=（int/int） ... 这个double和int没有区别 （一定要乘上一个1.0！！！（调试1小时。。）） 最后放代码和数据生成器。。。 随手写的。。。。 ```cpp //AC code #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r inline int read(){ int x=0,f=1; char p=getchar(); while(!isdigit(p)){ if(p=='-') f=-1; p=getchar(); } while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar(); return x*f; } const int maxn=1e6+5; const int mod1=39989,mod2=1e9; int n,lastans,cnt; struct node{ int id; }tree[maxn<<2]; struct node1{ double k,b; }line[maxn]; inline void swap(int &x,int &y){ int t=x;x=y;y=t; } inline void insert(int k,int l,int r,int id){ if(l==r){ double xid=line[id].k*l+line[id].b; double yid=line[tree[k].id].k*l+line[tree[k].id].b; if(xid>yid) tree[k].id=id; return; } double xmid=line[id].k*mid+line[id].b; double ymid=line[tree[k].id].k*mid+line[tree[k].id].b; double xxl=line[id].k*l+line[id].b; double yyl=line[tree[k].id].k*l+line[tree[k].id].b; double xxr=line[id].k*r+line[id].b; double yyr=line[tree[k].id].k*r+line[tree[k].id].b; if(xxl>=yyl&&xxr>=yyr){ if(xxl!=yyl&&xxr!=yyr){ tree[k].id=id; return; } if(xxl==yyl&&xxr==yyr) return; if(xxl==yyl){ insert(lson,tree[k].id); tree[k].id=id; return; } if(xxr==yyr){ insert(rson,tree[k].id); tree[k].id=id; return; } } if(xxl<yyl&&xxr<yyr) return ; if(xmid>ymid){ int yid=tree[k].id; tree[k].id=id; if(xxl>yyl){ insert(rson,yid); return; } if(xxr>yyr){ insert(lson,yid); return; } } if(xmid<=ymid){ if(xxl>yyl){ insert(lson,id); return; } if(xxr>yyr){ insert(rson,id); return; } } } inline void update(int k,int l,int r,int L,int R,int id){ if(L<=l&&r<=R){ insert(k,l,r,id); // cout<<"debug "<<k<<" "<<l<<" "<<r<<endl; return; } if(L<=mid) update(lson,L,R,id); if(R>mid) update(rson,L,R,id); return ; } inline int query(int k,int l,int r,int pos){ if(l==r) return tree[k].id; double jisk=line[tree[k].id].k*pos+line[tree[k].id].b; double jisx; if(pos<=mid){ int x=query(lson,pos); jisx=line[x].k*pos+line[x].b; if(jisk==jisx) return min(x,tree[k].id); if(jisk>jisx) return tree[k].id; if(jisk<jisx) return x; } else{ int x=query(rson,pos); jisx=line[x].k*pos+line[x].b; if(jisk==jisx) return min(x,tree[k].id); if(jisk>jisx) return tree[k].id; if(jisk<jisx) return x; } } int main(){ // freopen("data.in","r",stdin); // freopen("man.txt","w",stdout); n=read(); while(n--){ int opt=read(); if(opt==1){ int xx0=read(),yy0=read(),xx1=read(),yy1=read(); xx0=(xx0+lastans-1)%mod1+1,yy0=(yy0+lastans-1)%mod2+1; xx1=(xx1+lastans-1)%mod1+1,yy1=(yy1+lastans-1)%mod2+1; if(xx0>xx1) swap(xx0,xx1),swap(yy0,yy1); if(xx0==xx1){ line[++cnt].k=0; line[cnt].b=max(yy1,yy0); } else{ line[++cnt].k=(1.0*(yy0-yy1))/(1.0*(xx0-xx1)); line[cnt].b=yy0-xx0*line[cnt].k; } // cout<<xx0<<" "<<yy0<<" "<<xx1<<" "<<yy1<<" "<<line[cnt].k<<" "<<line[cnt].b<<endl; update(1,1,mod1,xx0,xx1,cnt); continue; } if(opt==0){ int x=read(); x=(x+lastans-1)%mod1+1; printf("%d\n",lastans=query(1,1,mod1,x)); continue; } } return 0; } ``` 方便大家写锅对拍。。。。 ``` // maker #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <queue> #include<ctime> #include <vector> #include <set> #define ll long long const int N=100010; using namespace std; inline int rnd() { int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { res=res*10+ch-'0'; ch=getchar(); } return res*f; } inline void wr(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) wr(x/10); putchar(x%10+'0'); } int n,m,Q,mx,x; int tong[N]; inline int R(int x) { return (rand())%x+1; } int main() { freopen("data.in","w",stdout); srand((long long)time(0)); n=100000; cout<<n<<endl; for(int i=1; i<=n; i++) { x=R(2)-1; if(x==1){ cout<<1<<" "; int xx1=R(39989); int yy1=R(1000000000); int xx2=R(39989); int yy2=R(1000000000); cout<<xx1<<" "<<yy1<<" "<<xx2<<" "<<yy2<<endl; } if(x==0){ cout<<0<<" "; int x=R(39989); cout<<x<<endl; } } return 0; } ```