所謂李超線段樹就是解決此題一類的問題（線段覆蓋查詢點最大（小）），把原本計算幾何的題目變成了簡單的線段樹，巧妙地結合了線段樹的標記永久化與標記下傳，在不考慮精度誤差的影響下，打法應該是這樣的。

#include <cstdio> #include <cstring> #include <algorithm> #define mid(a,b) ((a+b)>>1) typedef long double ld; const int Inf_x=39989; const int Inf_y=1000000000; int cnt,sz; struct Line{ld k,b;int id;inline ld f(int x){return k*x+b;}inline ld point(Line a){return (b-a.b)/(a.k-k);} }; struct lcSegment_Tree{lcSegment_Tree *ch[2];Line line; }seg[Inf_x<<4],*root; void pushdown(lcSegment_Tree *p,int l,int r,Line line){ld a1=p->line.f(l),a2=line.f(l),b1=p->line.f(r),b2=line.f(r);if(a1<=a2&&b1<=b2){p->line=line;return;}if(a1>a2&&b1>b2)return;ld x=line.point(p->line);if(x<=mid(l,r)){if(a1>a2)pushdown(p->ch[0],l,mid(l,r),p->line),p->line=line;else pushdown(p->ch[0],l,mid(l,r),line);}else{if(a1>a2)pushdown(p->ch[1],mid(l,r)+1,r,line);else pushdown(p->ch[1],mid(l,r)+1,r,p->line),p->line=line;} } void build(lcSegment_Tree *&p,int l,int r){p=seg+sz,++sz;if(l==r)return;build(p->ch[0],l,mid(l,r));build(p->ch[1],mid(l,r)+1,r); } void insert(lcSegment_Tree *p,int l,int r,int z,int y,Line line){if(z<=l&&r<=y){pushdown(p,l,r,line);return;}if(z<=mid(l,r))insert(p->ch[0],l,mid(l,r),z,y,line);if(mid(l,r)<y)insert(p->ch[1],mid(l,r)+1,r,z,y,line); } void query(lcSegment_Tree *p,int l,int r,int pos,ld last,int &ans){if(p->line.f(pos)>last||(p->line.f(pos)==last&&p->line.id<ans))ans=p->line.id,last=p->line.f(pos);if(l==r)return;if(pos<=mid(l,r))query(p->ch[0],l,mid(l,r),pos,last,ans);else query(p->ch[1],mid(l,r)+1,r,pos,last,ans); } int main(){int T,opt,zzh1,zzh2,wq1,wq2,lastans=0,x;Line temp;scanf("%d",&T),build(root,1,Inf_x);while(T--){scanf("%d",&opt);if(opt){scanf("%d%d%d%d",&zzh1,&zzh2,&wq1,&wq2);zzh1=(zzh1+lastans-1)%Inf_x+1,zzh2=(zzh2+lastans-1)%Inf_y+1,wq1=(wq1+lastans-1)%Inf_x+1,wq2=(wq2+lastans-1)%Inf_y+1;if(wq1>zzh1)wq1^=zzh1^=wq1^=zzh1,wq2^=zzh2^=wq2^=zzh2;if(wq1==zzh1)temp.k=0.,temp.b=std::max(wq2,zzh2);else temp.k=(ld)(zzh2-wq2)/(zzh1-wq1),temp.b=zzh2-temp.k*zzh1;temp.id=++cnt,insert(root,1,Inf_x,wq1,zzh1,temp);}else{scanf("%d",&x),x=(x+lastans-1)%Inf_x+1,lastans=0;query(root,1,Inf_x,x,0.,lastans);printf("%d\n",lastans);}}return 0; }

?

轉載于:https://www.cnblogs.com/TSHugh/p/7601879.html

總結

以上是生活随笔為你收集整理的【BZOJ 3165】 [Heoi2013]Segment 李超线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。