BZOJ3165【HEOI2013】Segment <李超线段树>

Problem

【HEOI2013】Segment

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第$i$条被插入的线段的标号为$i$。
2. 给定一个数$k$，询问与直线$x=k$相交的线段中，交点最靠上的线段的编号。

Input

第一行一个整数$n$，表示共$n$个操作。
接下来$n$行，每行第一个数为$0$或$1$。
若该数为$0$，则后面跟着一个正整数$k$，表示询问与直线$x=((k+lastans–1)\%39989+1)$相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中$\%$表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段$y$坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为$1$，则后面跟着四个正整数$x_0,y_0,x_1,y_1$，表示插入一条两个端点为$((x_0+lastans-1)\%39989+1$,$(y_0+lastans-1)\%10^9+1)$和$((x_1+lastans-1)\%39989+1$,$(y_1+lastans-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\le n\le10^5$, $1\le k,x_0,x_1\le39989$, $1\le y_0\le y_1\le10^9$。

标签：李超线段树

Solution

李超线段树模板题。

用线段树维护线段。对于每个区间，维护这个区间的“优选线段”，即对于多数$x$值是最优的线段。
插入一条线段时，首先判断是否完全优于或完全劣于当前区间的优选线段。如果完全更优就覆盖后返回，如果完全更劣就直接返回。这样只剩下部分优于当前区间优先线段的情况。计算出两线段交点，令两线段中取最优值的部分较多的那条为$a$，较少的那条为$b$。如果交点在左区间，那么$b$一定不可能是右区间的最优线段，否则$b$取最优值的部分比$a$多，与定义矛盾。于是将$a$作为本区间的优选线段，然后递归试图将$b$插入左区间中。同样地，交点在右区间时，将$b$递归插入右区间即可。
查询一个$x$值时，将线段树从根到值为$x$的叶子结点的路径上的所有线段在$x$处的取值取最大值即可。
总复杂度$O(n\log_2^2{n})$。

Code

#include <bits/stdc++.h>
#define R 40000
#define P1 39989
#define P2 1000000000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct line {int id; dnt k, b;} tr[R<<2];
dnt calc(line l, int x) {return l.k*x+l.b;}
line max(line a, line b, int x) {
    dnt val1 = calc(a, x), val2 = calc(b, x);
    if (val1 == val2) return a.id < b.id ? a : b;
    return val1 > val2 ? a : b;
}
void insert(int v, int s, int t, line L) {
    if (!tr[v].id) {tr[v] = L; return;}
    line a = tr[v], b = L;
    dnt sa = calc(a, s), sb = calc(b, s);
    dnt ta = calc(a, t), tb = calc(b, t);
    if (sa >= sb && ta >= tb) {tr[v] = a; return;}
    if (sa <= sb && ta <= tb) {tr[v] = b; return;}
    dnt p = (a.b-b.b)/(b.k-a.k);
    if (sa > sb) {
        if (p <= (dnt)mid) insert(v<<1, s, mid, a), tr[v] = b;
        if (p > (dnt)mid) insert(v<<1|1, mid+1, t, b),tr[v] = a;
    } else {
        if (p <= (dnt)mid) insert(v<<1, s, mid, b), tr[v] = a;
        if (p > (dnt)mid) insert(v<<1|1, mid+1, t, a), tr[v] = b;
    }
}
void modify(int v, int s, int t, int l, int r, line L) {
    if (s >= l && t <= r) {insert(v, s, t, L); return;}
    if (l <= mid) modify(v<<1, s, mid, l, r, L);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, L);
}
line query(int v, int s, int t, int x) {
    if (s == t) return tr[v]; line ret;
    if (x <= mid) ret = query(v<<1, s, mid, x);
    if (x >= mid+1) ret = query(v<<1|1, mid+1, t, x);
    return max(tr[v], ret, x);
}
int main() {
    int T, n = 0; read(T), tr[0].b = (dnt)-INF;
    for (int lst = 0; T; T--) {
        int opt; read(opt);
        if (opt == 0) {
            int x; read(x), x = (x+lst-1)%P1+1;
            line res = query(1, 1, R, x);
            printf("%d\n", lst = res.id);
        }
        if (opt == 1) {
            int x0, y0, x1, y1; dnt k, b;
            read(x0), x0 = (x0+lst-1)%P1+1;
            read(y0), y0 = (y0+lst-1)%P2+1;
            read(x1), x1 = (x1+lst-1)%P1+1;
            read(y1), y1 = (y1+lst-1)%P2+1;
            if (x0 > x1) swap(x0, x1), swap(y0, y1);
            if (x0 == x1) k = 0, b = max(y0, y1);
            else k = 1.0*(y0-y1)/(x0-x1), b = y0-k*x0;
            modify(1, 1, R, x0, x1, (line){++n, k, b});
        }
    }
    return 0;
}