[洛谷P4097] [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\), \(x1\), \(y1\)，表示插入一条两个端点为 \(((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

对于 \(30\%\) 的数据，\(n \leq 1000\)
对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5, 1 \leq k, x0, x1 \leq 39989, 1 \leq y0 , y1 \leq 10^9\)

题解

李超线段树模板题。
推荐一篇好的 \(blog\) : https://blog.csdn.net/flere825/article/details/76283734

很巧妙的思想。
关键点就是引入区间“最优势线段” & 动态维护它，保证对每一个位置，答案一定在包含这个位置的区间的“最优势线段”中。

代码

注意坑点！！！！！
\(y\) 的模数为 \(10^9\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>

#define eps 1e-9 
#define P 39989

using namespace std;

int read(){
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}

const int N = 100005;
typedef double db;

int tot;
db K[N],B[N];
struct node{
    node *ch[2];
    int id;
}pool[P*2],*root;
int cnt;
void build(node *p,int l,int r){
    p->id=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p->ch[0]=&pool[++cnt],l,mid);
    build(p->ch[1]=&pool[++cnt],mid+1,r);
}
inline db cal(int x,int c) { return K[x]*c+B[x]; }
bool better(int x,int y,int c){
    if(x==0) return false;
    if(y==0) return true;
    db cx=cal(x,c),cy=cal(y,c);
    if(fabs(cx-cy)<eps) return x<y;
    return cx>cy;
}
void insert(node *p,int l,int r,int L,int R,int c){
    if(l==L && r==R){ 
        int mid=(l+r)>>1;
        if(better(c,p->id,mid)) swap(p->id,c);
        int tl=better(p->id,c,l),tr=better(p->id,c,r);
        if(!c || l==r || (tl && tr)) return;
        if(tl) insert(p->ch[1],mid+1,r,mid+1,r,c);
        else insert(p->ch[0],l,mid,l,mid,c);
        return;
    }
    int mid=(l+r)>>1;
    if(R<=mid) insert(p->ch[0],l,mid,L,R,c);
    else if(L>mid) insert(p->ch[1],mid+1,r,L,R,c);
    else {
        insert(p->ch[0],l,mid,L,mid,c);
        insert(p->ch[1],mid+1,r,mid+1,R,c);
    }
} 
int ans;
void query(node *p,int l,int r,int c){
    ans = better(p->id,ans,c) ? p->id : ans ;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(c<=mid) query(p->ch[0],l,mid,c);
    else query(p->ch[1],mid+1,r,c);
}

int main()
{
    int n,opt,lastans=0,k,x0,y0,x1,y1;
    n=read();
    
    root=&pool[++cnt];
    build(root,1,P);
    
    while(n--){
        opt=read();
        if(opt==0){
            k=(read()+lastans-1)%P+1;
            ans=0;
            query(root,1,P,k);
            lastans=ans;
            printf("%d\n",lastans);
        }
        else{
            x0=(read()+lastans-1)%P+1; y0=(read()+lastans-1)%1000000000+1;
            x1=(read()+lastans-1)%P+1; y1=(read()+lastans-1)%1000000000+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            tot++;
            K[tot]=1.0*(y1-y0)/(x1-x0);
            B[tot]=y0-K[tot]*x0;
            insert(root,1,P,x0,x1,tot);
        }
    }
    
    return 0;
} 

[洛谷P4097] [HEOI2013] Segment

原文：https://www.cnblogs.com/lindalee/p/11342709.html