P4097 HEOI2013 Segment
今天我们来学习李超线段树。
他就是一个维护线段的线段树。
学习完毕
李超线段树是线段树的一个变种,支持在平面直角坐标系中动态插入线段,查询一条竖线与所有线段的交点纵坐标的最大值或最小值。
区间记录 (mid) 点在上面的线段。(也就是区间最优秀线段)
(caution: 大区间最优不一定是小区间最优)
举个例子:
显然 (S_1) 是 (L, R) 区间最优,但是不是 (L, mid) 区间最优。
(S_2) 不是 (L, R) 区间最优,但是是 (L, mid) 区间最优。
所以我们在一个区间有最优线段的时候,更新用的是交换而不是直接替代,然后再考虑原线段的当前线段的交点位置,然后在交点位置的那个区间再讨论。(没有的时候直接替代就行了)
(insert)代码:
void ins(ll node, ll l, ll r, line seg) {
if (l <= t[node].l && t[node].r <= r) {
dd lp = t[node].L.calcy(t[node].l), rp = t[node].L.calcy(t[node].r);
dd lq = seg.calcy(t[node].l), rq = seg.calcy(t[node].r);
if (!t[node].flag) t[node].flag = 1, t[node].L = seg;
else if (lq - lp > ep && rq - rp > ep) t[node].L = seg;
else if (lq - lp > ep || rq - rp > ep) {
ll mid = (t[node].l + t[node].r) >> 1;
if (seg.calcy(mid) - t[node].L.calcy(mid) > ep) swap(t[node].L, seg); // 这里可以保证找交点所在的区间进行再讨论一定是对的,同时更新区间最优线段。
if (mid - met(seg, t[node].L) > ep) ins(node << 1, l, r, seg);
else ins(node << 1 | 1, l, r, seg);
}
return;
}
ll mid = (t[node].l + t[node].r) >> 1;
if (l <= mid) ins(node << 1, l, r, seg);
if (mid < r) ins(node << 1 | 1, l, r, seg);
return;
}
下面是全部代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef double dd;
typedef long long ll;
typedef pair<double, ll> pdl;
const ll MAXN = 1e5+10;
const dd ep = 1e-6;
struct line {
dd k, b;
ll id;
line(dd k=0, dd b=0, ll id=0):k(k),b(b),id(id){}
dd calcy(ll pos) {
return k * pos + b;
}
};
struct nod {
ll l, r;
line L;
bool flag;
nod(ll l,ll r,line L,bool flag):l(l),r(r),L(L),flag(flag){}
nod(){}
} t[MAXN << 2];
ll N, M, lstans = 0, B = 39989, cnt;
pdl ask(ll, ll);
void build(ll, ll, ll);
void ins(ll, ll, ll, line);
dd met(line, line);
int main() {
#ifdef ZZCAKIOI
freopen("P4097_1.in", "r", stdin);
//freopen("P4097.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin >> N;
build(1, 0, B);
for (ll i = 1, op; i <= N; i++) {
cin >> op;
if (op == 1) {
ll x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 = (x1 + lstans - 1) % B + 1;
x2 = (x2 + lstans - 1) % B + 1;
y1 = (y1 + lstans - 1) % 1000000000 + 1;
y2 = (y2 + lstans - 1) % 1000000000 + 1;
if (x1 > x2) {
swap(x1, x2);
swap(y1, y2);
}
cnt++;
if (x1 != x2) {
dd kk = (y2 - y1 + 0.0) / (x2 - x1 + 0.0);
ins(1, x1, x2, {kk, (dd)y1 - (dd)x1 * kk, cnt});
} else ins(1, x1, x2, {0, (dd)max(y1, y2), cnt});
} else {
ll k, x;
cin >> k;
x = (k + lstans - 1) % B + 1;
lstans = ask(1, x).second;
cout << lstans << '
';
}
}
return 0;
}
void build(ll node, ll l, ll r) {
t[node] = {l, r, line(), false};
if (l == r) return;
ll mid = (l + r) >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid+1, r);
}
void ins(ll node, ll l, ll r, line seg) {
if (l <= t[node].l && t[node].r <= r) {
dd lp = t[node].L.calcy(t[node].l), rp = t[node].L.calcy(t[node].r);
dd lq = seg.calcy(t[node].l), rq = seg.calcy(t[node].r);
if (!t[node].flag) t[node].flag = 1, t[node].L = seg;
else if (lq - lp > ep && rq - rp > ep) t[node].L = seg;
else if (lq - lp > ep || rq - rp > ep) {
ll mid = (t[node].l + t[node].r) >> 1;
if (seg.calcy(mid) - t[node].L.calcy(mid) > ep) swap(t[node].L, seg);
if (mid - met(seg, t[node].L) > ep) ins(node << 1, l, r, seg);
else ins(node << 1 | 1, l, r, seg);
}
return;
}
ll mid = (t[node].l + t[node].r) >> 1;
if (l <= mid) ins(node << 1, l, r, seg);
if (mid < r) ins(node << 1 | 1, l, r, seg);
return;
}
pdl ask(ll node, ll pos) {
double an = t[node].L.calcy(pos);
ll id = t[node].L.id;
if (t[node].l == t[node].r) return make_pair(an, id);
ll mid = (t[node].l + t[node].r) >> 1;
if (pos <= mid) {
pdl tem = ask(node << 1, pos);
if (tem.first > an || (abs(tem.first - an) < ep && tem.second < id)) an = tem.first, id = tem.second;
} else {
pdl tem = ask(node << 1 | 1, pos);
if (tem.first > an || (abs(tem.first - an) < ep && tem.second < id)) an = tem.first, id = tem.second;
}
return make_pair(an, id);
}
dd met(line a, line b) {
return (a.b - b.b) / (b.k - a.k);
}