bzoj 1568 李超线段树

博客：http://www.cnblogs.com/mangoyang/p/9979465.html

李超线段树支持两种操作：1：插入一条直线。2：询问在x = c与这些直线的交点中最大的y坐标。

插入的时候，如果有交点，本层节点留下来的是优势直线,劣势的那条去递归比较。优势直线是指在这个区间中覆盖的面积最大的那条直线。

维护的时候用了标记永久化，所以递归询问回溯的时候比较所有的直线，取坐标最大的那一条。

复杂度O(n(lgn)^2),常数相对于平衡树比较小。

代码：

#include <bits/stdc++.h>

#define ls(x) (x << 1)

#define rs(x) ((x << 1) | 1)

using namespace std;

const int maxn = 100010;

struct line {

	double k, b;

};

line a[maxn];

int tot;

struct SegementTree {

	int id;

};

SegementTree tr[maxn * 4];

double get_pos(int x, int y) {

	return a[x].k * y + a[x].b;

}

double cross(int x, int y) {

	return (a[x].b - a[y].b) / (a[y].k - a[x].k);

}

void update(int o, int l, int r, int now) {

	if(!tr[o].id) {

		tr[o].id = now;

		return;

	}

	int x = tr[o].id;

	double l1 = get_pos(now, l), r1 = get_pos(now, r);

	double l2 = get_pos(x, l), r2 = get_pos(x, r);

	if(l1 <= l2 && r1 <= r2) {

		return;

	}

	else if(l1 > l2 && r1 > r2) {

		tr[o].id = now;

		return;

	}

	int mid = (l + r) >> 1;

	double y = cross(now, x);

	if(y <= mid) update(ls(o), l, mid, r1 > r2 ? x : now);

	else update(rs(o), mid + 1, r, l1 > l2 ? x : now);

	if((y <= mid && r1 > r2) || (y > mid && l1 > l2))

		tr[o].id = now;

}

int query(int o, int l, int r, int pos) {

	if(l == r) {

		return tr[o].id;

	}

	int mid = (l + r) >> 1, ans = 0;

	if(pos <= mid) ans = query(ls(o), l, mid, pos);

	else ans = query(rs(o), mid + 1, r, pos);

	if(!tr[o].id) return ans;

	int x = tr[o].id;

	if(get_pos(x, pos) > get_pos(ans, pos)) return x;

	else return ans;

}

char s[110];

int main() {

	int n;

	double x, y;

	int z;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%s",s + 1);

		if(s[1] == 'P') {

			scanf("%lf%lf", &x, &y);

			a[++tot] = (line){y, x};

			update(1, 0, 50000, tot);

		} else {

			scanf("%d", &z);

			int ans = query(1, 0, 50000, z - 1);

			printf("%d\n", (int)(get_pos(ans, z - 1) / 100));

		}

	}

}

巴特西

bzoj 1568 李超线段树

最新文章

热门文章