BZOJ3165: [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

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。

Source

这一道题非常巧妙，用一个线段树来维护了一段类似凸包的东西。这种线段树还有一个优美的名字——李超线段树(应该是一个叫李超dalao发明的QWQ?)

我们对于这一道题，用线段树的每一个节点存放一条线段：

我们这样操作：先把线段拆到log个完整的区间，对于每一个完整的区间，考虑向下递归插入当前线段：

1、如果当前线段比节点现有线段上方漏出的区间更多，那么用现有线段替换当前节点线段，将当前节点的线段递归插入到左/右儿子。

2、否则将现有线段递归插入。

对于上图来说区间AD内储存红色的线段，区间AB内储存绿色的线段，区间BC内储存蓝色的线段。类似标记永久化，那么对于一个查询，可能成为最优答案的线段一定在该节点到线段树根的路径上，我们查询的时候一边回溯一遍更新就行了。

code:

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e5 + 5;

namespace G2D {
    #define T double
    #define eps 1e-8
    struct P {T x, y;P(T _x, T _y):x(_x), y(_y){}P(){}};
    inline int sg(T a) {return (a > -eps) - (a < eps);}
    struct Line {
        P s, t;double k, b;Line(){k = b = 0;}
        Line(P _s, P _t):s(_s), t(_t){
        	if(s.x == t.x) k = 0, b = t.y > s.y ? t.y : s.y;
			else k = (t.y - s.y) / (t.x - s.x), b = s.y - s.x * k;
		}
		double GetY(double x) {return k * x + b;}
    };
}

G2D::Line lines[maxn];

namespace SGT {
	using namespace G2D;
	int t[maxn << 2], cnt;
	bool cmp_line(int a, int b, int pos) {
		double Ya = lines[a].GetY(pos), Yb = lines[b].GetY(pos);
		return sg(Ya - Yb) ? Ya > Yb : a < b;
	}
	void add(int x, int l, int r, int rt) {
		if(!t[rt]) t[rt] = x;
		else {
			double leftY = lines[x].GetY(l) - lines[t[rt]].GetY(l);
			double rightY = lines[x].GetY(r) - lines[t[rt]].GetY(r);
			int SL = sg(leftY), SR = sg(rightY);
			if(SL == 1 && SR == 1) t[rt] = x;
			else if(SL == 1 || SR == 1){
				int mid = (l + r) >> 1;
				if(SL > 0)
					if(cmp_line(x, t[rt], mid)) add(t[rt], mid + 1, r, rt << 1 | 1), t[rt] = x;
					else add(x, l, mid, rt << 1);
				else
					if(cmp_line(x, t[rt], mid)) add(t[rt], l, mid, rt << 1), t[rt] = x;
					else add(x, mid + 1, r, rt << 1 | 1);
			}
		}
	}
	void insert(int x, int l, int r, int tl, int tr, int rt) {
		if(l == tl && r == tr) {
			add(x, l, r, rt);
			return;
		}
		int mid = tl + tr >> 1;
		if(r <= mid) insert(x, l, r, tl, mid, rt << 1);
		else if(l > mid) insert(x, l, r, mid + 1, tr, rt << 1 | 1);
		else insert(x, l, mid, tl, mid, rt << 1), insert(x, mid + 1, r, mid + 1, tr, rt << 1 | 1);
	}
	int query(int pos, int tl, int tr, int rt) {
		if(tl == tr) 
			return t[rt];
		int mid = tl + tr >> 1, ret;
		if(pos <= mid) ret = query(pos, tl, mid, rt << 1);
		else ret = query(pos, mid + 1, tr, rt << 1 | 1);
		double Yret = lines[ret].GetY(pos), Yrt = lines[t[rt]].GetY(pos);
		if(!sg(Yret - Yrt)) return ret < t[rt] ? ret : t[rt];
		return sg(Yret - Yrt) == -1 ? t[rt] : ret;
	}
}

int n, out, t, opt, a, b, c, d, cnt, p2 = 1e9, lastans = 0;

int main() {
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &opt);
		if(opt == 1) {
			scanf("%d%d%d%d", &a, &b, &c, &d);
			a = ((a + lastans - 1) % 39989 + 1);
			b = ((b + lastans - 1) % p2 + 1);
			c = ((c + lastans - 1) % 39989 + 1);
			d = ((d + lastans - 1) % p2 + 1);
			if(a > c) swap(a, c), swap(b, d);
			lines[++cnt] = G2D::Line(G2D::P(a, b), G2D::P(c, d));
			SGT::insert(cnt, a, c, 1, 40000, 1);
		} else {
			scanf("%d", &a);
			a = ((a + lastans - 1) % 39989 + 1), ++out;
			printf("%d\n", lastans = SGT::query(a, 1, 40000, 1));
		}
	}
	return 0;
}

Rockdu's Blog