传说中的“李超树”。
大意：给你若干线段，试求横坐标x上的最上方一条线段的编号。无则输出零。
解:用线段树维护。
插入的时候保存自己这个区间上可能成为最大值的线段，被抛弃的则看情况下放。
查询时从最底层向上查一路，沿途取得答案。
函数我用的是斜截式来存，脑残的把b写错了.....getY还传错参了。
调掉之后就一发AC！哈哈哈
#include <cstdio>
#include <algorithm>
#include <cmath>
const int N = , M = , INF = 0x3f3f3f3f;
const double eps = 1e-; struct SG {
double k, b;
int l, r;
}sg[M]; inline double getY(int a, int x) {
SG t = sg[a];
if(x < t.l || t.r < x || !a) {
return (double)(-INF);
}
if(fabs(t.k - INF) < eps) {
return t.b;
}
return t.k * x + t.b;
} struct SegmentTree {
int ans[N << ]; void add(int L, int R, int v, int l, int r, int o) {
//printf("add : %d %d %d %d %d \n", L, R, v, l, r);
int mid = (l + r) >> ;
if(L <= l && r <= R) {
if(!ans[o]) { /// no segment
ans[o] = v;
//printf("ans[] = %d \n", ans[o]);
return;
}
if(l == r) { /// only one
if(getY(v, r) > getY(ans[o], r)) {
ans[o] = v;
//printf("ans[] = %d \n", ans[o]);
}
return;
}
double A = getY(v, l), B = getY(v, mid), C = getY(v, r);
double D = getY(ans[o], l), E = getY(ans[o], mid), F = getY(ans[o], r);
if(A > D && C > F) {
ans[o] = v;
//printf("ans[] = %d \n", ans[o]);
return;
}
/*if(v == 3 && l == 4 && r == 5) {
printf("B = %lf E = %lf\n", B, D);
}*/
if(!(A > D) && !(C > F)) {
return;
}
if(B > E) {
if(sg[v].k > sg[ans[o]].k) {
add(l, mid, ans[o], l, mid, o << );
ans[o] = v;
//printf("ans[] = %d \n", ans[o]);
}
else {
add(mid + , r, ans[o], mid + , r, o << | );
ans[o] = v;
//printf("ans[] = %d \n", ans[o]);
}
}
else {
if(sg[v].k > sg[ans[o]].k) {
add(mid + , r, v, mid + , r, o << | );
}
else {
add(l, mid, v, l, mid, o << );
}
}
return;
}
if(L <= mid) {
add(L, R, v, l, mid, o << );
}
if(mid < R) {
add(L, R, v, mid + , r, o << | );
}
return;
}
int ask(int p, int l, int r, int o) {
if(l == r) {
//printf("ask: %d %d %d return %d \n", p, l, r, ans[o]);
return ans[o];
}
int mid = (l + r) >> ;
int A;
if(p <= mid) {
A = ask(p, l, mid, o << );
}
else {
A = ask(p, mid + , r, o << | );
}
int t = ans[o];
if(getY(A, p) - eps > getY(t, p)) {
t = A;
}
else if(fabs(getY(A, p) - getY(t, p)) < eps) {
t = std::min(t, A);
}
//printf("ask: %d %d %d return %d \n", p, l, r, t);
return t;
}
}SgT; int main() {
int n, MO = , lastans = , num = ;
scanf("%d", &n);
for(int i = , f, x, xx, y, yy; i <= n; i++) {
scanf("%d", &f);
if(f) {
scanf("%d%d%d%d", &x, &y, &xx, &yy);
x = (x + lastans - ) % MO + ;
xx = (xx + lastans - ) % MO + ;
y = (y + lastans - ) % + ;
yy = (yy + lastans - ) % + ;
if(x > xx) {
std::swap(x, xx);
std::swap(y, yy);
}
sg[++num].l = x;
sg[num].r = xx;
if(x == xx) {
sg[num].k = 1.0 * INF;
sg[num].b = 1.0 * std::max(y, yy);
}
else {
sg[num].k = 1.0 * (y - yy) / (x - xx);
sg[num].b = y - sg[num].k * x;
}
SgT.add(x, xx, num, , MO, );
/*for(int i = 1; i <= 11; i++) {
SgT.ask(i, 1, MO, 1);
}
puts("");*/
}
else {
scanf("%d", &x);
x = (x + lastans - ) % MO + ;
lastans = SgT.ask(x, , MO, );
printf("%d\n", lastans);
}
} /*puts("");
for(int i = 1; i <= num; i++) {
printf("%lf %lf %d %d \n", sg[i].k, sg[i].b, sg[i].l, sg[i].r);
}*/ return ;
}
AC代码
调起来真难...很不理解为什么有人的李超树代码只有我的 1 / 3 长