题意
在平面直角坐标系中维护两个操作:
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.询问与x=k的线段中,y 坐标最靠上的线段标号。
(强制在线)
分析
李超线段树模板题
代码
#include<iostream> using namespace std; const int mod1=39989,mod2=1e9,N=1e5+5; int m,cnt,v[N<<2],ans; struct data{ double k,b; data(){} data(int x1,int y1,int x2,int y2){//计算直线(线段)的 k,b if(x1==x2)k=0,b=max(y1,y2); else k=1.0*(y1-y2)/(x1-x2),b=-k*x1+y1; } double calc(int x){//计算y的值 return k*x+b; } }t[N]; void query(int id,int l,int r,int x){//查询 if(t[ans].calc(x)<t[v[id]].calc(x))ans=v[id];//取最大的y else if(t[ans].calc(x)==t[v[id]].calc(x)&&ans>v[id])ans=v[id];//取最小的标号 if(l==r)return; int mid=(l+r)>>1; if(x<=mid)query(id<<1,l,mid,x);//更新 else query(id<<1|1,mid+1,r,x); } void ins(int id,int l,int r,int x,int y,int now){//插入线段 if(x<=l&&r<=y){ if(t[now].calc(l)>t[v[id]].calc(l)&&t[now].calc(r)>t[v[id]].calc(r)){//完全覆盖当前优势线段,更改 v[id]=now; return; } if(t[now].calc(l)<=t[v[id]].calc(l)&&t[now].calc(r)<=t[v[id]].calc(r))return;//完全被覆盖,gg if(l==r)return; } int mid=(l+r)>>1; if(x<=mid)ins(id<<1,l,mid,x,y,now);//更改左边 if(y>mid)ins(id<<1|1,mid+1,r,x,y,now);//更改右边 } int main(){ scanf("%d",&m); t[0].b=-1; int op,x1,x2,y1,y2; while(m--){ scanf("%d",&op); if(!op){ scanf("%d",&x1); x1=(x1+ans-1)%mod1+1; ans=0; query(1,1,mod1,x1); printf("%d\n",ans); } else{ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1=(x1+ans-1)%mod1+1;x2=(x2+ans-1)%mod1+1;//强制在线 y1=(y1+ans-1)%mod2+1;y2=(y2+ans-1)%mod2+1; t[++cnt]=data(x1,y1,x2,y2); if(x1>x2)swap(x1,x2); ins(1,1,mod1,x1,x2,cnt); } } }View Code