[题解] [HEOI2013] Segment

题面

题解

李超线段树
为了与机房大佬 HYJ 同步伐
学习笔记请移步 yyb的博客
Code

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

const int N = 100005;

const int mod = 39989;

#define val(id, x) (k[id] * x + b[id])

using namespace std;

int Q, cnt, ans;

struct node

{

	int id;

	double k, b;

} t[N << 2];

double k[N], b[N]; 

template < typename T >

inline T read()

{

	T x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * w;

}

void pushtag(int p, int l, int r, int id)

{

	if(!t[p].id) { t[p] = (node) { id, k[id], b[id] }; return; }

	int now = t[p].id;

	double l1 = val(now, l), r1 = val(now, r), l2 = val(id, l), r2 = val(id, r);

	if(l2 <= l1 && r2 <= r1) return;

	if(l1 < l2 && r1 < r2) { t[p] = (node) { id, k[id], b[id] }; return; }

	int mid = (l + r) >> 1; double x = (b[id] - b[now]) / (k[now] - k[id]);

	if(x <= mid)

	{

		if(l1 <= l2) pushtag(p << 1, l, mid, id);

		else pushtag(p << 1, l, mid, now), t[p] = (node) { id, k[id], b[id] };

	}

	else

	{

		if(l1 <= l2) pushtag(p << 1 | 1, mid + 1, r, now), t[p] = (node) { id, k[id], b[id] };

		else pushtag(p << 1 | 1, mid + 1, r, id);

	}

}

void modify(int p, int l, int r, int ql, int qr, int id)

{

	if(ql <= l && r <= qr) { pushtag(p, l, r, id); return; }

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

	if(ql <= mid) modify(p << 1, l, mid, ql, qr, id);

	if(mid < qr) modify(p << 1 | 1, mid + 1, r, ql, qr, id);

}

void check(int &a, int c, int x)

{

	double y0 = val(a, x), y1 = val(c, x);

	if(y1 > y0 || (fabs(y1 - y0) < 1e-7 && a > c)) a = c;

}

int query(int p, int l, int r, int x)

{

	if(l == r) return t[p].id;

	int mid = (l + r) >> 1, res = t[p].id;

	if(x <= mid) check(res, query(p << 1, l, mid, x), x);

	else check(res, query(p << 1 | 1, mid + 1, r, x), x);

	return res;

}

int main()

{

/*	freopen("cpp.in", "r", stdin);

	freopen("cpp.out", "w", stdout);

*/	Q = read <int> ();

	int opt, x0, x1, y0, y1;

	while(Q--)

	{

		opt = read <int> ();

		if(!opt)

		{

//			printf("%d\n", x0);

			x0 = read <int> (), x0 = ((x0 + ans - 1) % mod + 1);

			printf("%d\n", ans = query(1, 1, mod, x0));

		}

		else

		{

			x0 = read <int> (), y0 = read <int> (), x1 = read <int> (), y1 = read <int> ();

			x0 = ((x0 + ans - 1) % mod + 1), y0 = ((y0 + ans - 1) % 1000000000 + 1);

			x1 = ((x1 + ans - 1) % mod + 1), y1 = ((y1 + ans - 1) % 1000000000 + 1);

			if(x0 > x1) swap(x0, x1), swap(y0, y1);

//			printf("%d %d\n", x0, x1);

			k[++cnt] = 1.0 * (y1 - y0) / (x1 - x0), b[cnt] = 1.0 * y0 - k[cnt] * x0;

			modify(1, 1, mod, x0, x1, cnt);

		}

	}

	return 0;

}

/*

  3

  1 3 5 7 7

  1 3 9 7 3

  0 5

 */
巴特西

[题解] [HEOI2013] Segment

题面

题解

Code

最新文章

热门文章
