注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3165][Heoi2013]Segment  

2015-05-18 10:49:24|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3165: [Heoi2013]Segment

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 237  Solved: 104
[Submit][Status][Discuss]

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)和((x1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。 
其中lastans为上一次询问的答案。初始时lastans=0。 

Output

对于每个 0操作,输出一行,包含一个正整数,表示交点最靠上的线段的编号。若不存在与直线相交的线段,答案为0。 

Sample Input

6 1 8 5 10 8 1 6 7 2 6 0 2 0 9 1 4 7 6 7 0 5

Sample Output

2 0 3

HINT

对于100%的数据,1 ≤ n ≤ 10^5 , 1 ≤  k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

Solution

线段树维护线段。关键在于怎么维护标记。
因为只有插入,所以每个线段树上的节点只维护一条线段,表示当前节点所控制的区间内所有线段有可能含有这条线段。
插入的时候,先把线段拆成log条分别插入,然后与原来的线段比较,如果完全在上面或者在下面则直接替换,否则至多只有一个交点,只可能在一个子区间内,另一个子区间必然是一条线段完全大于另一条线段。
于是把大的留下来,小的递归子树做一样的事。所以插入log^2,询问log

Code

/**************************************************************
    Problem: 3165
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:644 ms
    Memory:2912 kb
****************************************************************/
 
#include<cstdio>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define swap(a,b) (st=a,a=b,b=st)
typedef double ld;
int _,n,d=65536,t[1<<17],x,x0,x1,y0,y1,ans,o,st;ld max,tmp;
struct L{ld k,b;}a[100010];
#define calc(x,i) (a[i].k*x+a[i].b)
#define its(x,y) (a[x].b-a[y].b)/(a[y].k-a[x].k)
void work(int o,int l,int r,int i){
    if(!t[o]){t[o]=i;return;}
    if(calc(l,i)>calc(l,t[o])||calc(l,i)==calc(l,t[o])&&calc(r,i)>calc(r,t[o]))swap(t[o],i);
    if(l==r||a[i].k==a[t[o]].k||calc(r,i)<=calc(r,t[o]))return;
    ld x=its(i,t[o]);if(x<l||x>r)return;int mid=l+r>>1;
    if(x<=mid)work(o<<1,l,mid,t[o]),t[o]=i;
    else work(o<<1|1,mid+1,r,i);
}
void upd(int o,int l,int r,int i){
    if(x0<=l&&r<=x1)work(o,l,r,i);
    else{
        int mid=l+r>>1;
        if(x0<=mid)upd(o<<1,l,mid,i);
        if(mid<x1)upd(o<<1|1,mid+1,r,i);
    }
}
int main(){
    for(_=F();_--;)
    if(!F()){
        for(x=(F()+ans-1)%39989+1,max=ans=0,o=x+d-1;o;o>>=1)
        if(tmp=calc(x,t[o]),tmp>max||tmp==max&&ans>t[o])max=tmp,ans=t[o];
        printf("%d\n",ans);
    }
    else{
        x0=(F()+ans-1)%39989+1,y0=(F()+ans-1)%1000000000+1,
        x1=(F()+ans-1)%39989+1,y1=(F()+ans-1)%1000000000+1;
        if(x0>x1)swap(x0,x1),swap(y0,y1);
        if(x0==x1)a[++n]=(L){0,y0>y1?y0:y1};
        else a[++n].k=1.0*(y0-y1)/(x0-x1),a[n].b=y0-a[n].k*x0;
        upd(1,1,d,n);
    }
}
  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018