BZOJ_3165_[Heoi2013]Segment_线段树
Description
要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。
Input
第一行一个整数n，表示共n 个操作。
接下来n行，每行第一个数为0或1。
若该数为 0，则后面跟着一个正整数 k，表示询问与直线
x = ((k +lastans–1)%39989+1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为 1，则后面跟着四个正整数 x0, y0, x 1, y 1，表示插入一条两个端点为
((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。
其中lastans为上一次询问的答案。初始时lastans=0。
Output
对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。
Sample Input
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5
Sample Output
0 3
HINT
对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。
插入时找到线段树上对应log个完全包含的结点。
对于当前结点，如果完全更优或原来没有线段，就插入并返回，如果比当前完全更差也返回，否则向下递归。
查询时查一个点查到底即可。
插入复杂度：每次插入log个区间，递归过程相当于向下二分，于是复杂度O(lognlogn)
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 40050
#define M 39989
#define ls p<<1
#define rs p<<1|1
typedef double f2;
int n,ans,is[N<<2],xx[N<<2],yy[N<<2];
f2 Y,K[N<<2],lv[N<<2],rv[N<<2];
int id;
void insert(int l,int r,int a,int b,f2 k,int y,int p) {
int mid=(l+r)>>1;
if(a<=l&&b>=r) {
f2 lw=y+(l-a)*k,rw=y+(r-a)*k;
if(!is[p]||(lw>lv[p]&&rw>rv[p])) {
is[p]=id; lv[p]=lw; rv[p]=rw;
}else if(lw>lv[p]||rw>rv[p]) {
insert(l,mid,a,b,k,y,ls);
insert(mid+1,r,a,b,k,y,rs);
}
return ;
}else {
if(a<=mid) insert(l,mid,a,b,k,y,ls);
if(b>mid) insert(mid+1,r,a,b,k,y,rs);
}
}
void query(int l,int r,int k,int p) {
if(l==r) {
if(is[p]&&(lv[p]>Y||(lv[p]==Y&&ans>is[p]))) Y=lv[p],ans=is[p];
return ;
}
if(is[p]) {
f2 now=lv[p]+1.0*(rv[p]-lv[p])/(r-l)*(k-l);
if(now>Y||(now==Y&&ans>is[p])) Y=now,ans=is[p];
}
int mid=(l+r)>>1;
if(k<=mid) query(l,mid,k,ls);
else query(mid+1,r,k,rs);
}
int main() {
scanf("%d",&n);
int opt,x_1,y_1,x_2,y_2,i;
for(i=1;i<=n;i++) {
scanf("%d%d",&opt,&x_1);
x_1=(x_1+ans-1)%M+1;
if(opt==0) {
Y=-1e15; ans=0;
query(1,M,x_1,1);
printf("%d
",ans);
}else {
id++;
scanf("%d%d%d",&y_1,&x_2,&y_2);
y_1=(y_1+ans-1)%1000000000+1;
x_2=(x_2+ans-1)%M+1;
y_2=(y_2+ans-1)%1000000000+1;
if(x_1>x_2) swap(x_1,x_2),swap(y_1,y_2);
f2 k; int y;
if(x_1==x_2) k=0,y=max(y_1,y_2);
else k=1.0*(y_2-y_1)/(x_2-x_1),y=y_1;
insert(1,M,x_1,x_2,k,y,1);
// printf("%d %d %d %d
",x_1,y_1,x_2,y_2);
}
}
}