woc 今天信息量好大。感觉过年之前不一定理解得完。
怎么 40 min 讲完李超线段树、wqs 二分、决策单调性的。
一种支持维护若干个一次函数的数据结构。
过程
考虑一个问题。
- 加入一个定义域为 \([l, r]\) 的一次函数。
- 查询与所有在 \(x = k\) 处有定义的一次函数中在 \(x = k\) 处取值最大的一个。
\(n \le 10^5\)，强制在线。（所以这个东西有什么很好的离线算法吗？好像也不能上单调队列维护凸壳来着？）
李超线段树的思想就是把定义域拆成 \(\log\) 段。
对于线段树上的每一个点我们打一个一次函数作为标记，表示我们要用这个一次函数来更新这个区间。我们修改的时候没有标记肯定把当前函数挂上作为标记，但是如果当前节点有标记，由于标记难以合并，我们只能下传。但是子节点也可能有标记，于是我们递归下传标记。
但是我们不需要真的每次都把标记下传到左右节点，如果真的这么干的话复杂度很容易就假了。于是我们对于一个区间 \([l,r]\)，将其对应的一次函数中 \(\operatorname{f}(\lfloor \frac{l+r}{2} \rfloor)\) 较大者留下来作为标记挂在节点上。容易发现，另一个函数大于留下的函数的区间要么全部属于左子，要么全部属于右子，于是我们只需要下传至其一，因为下传至另一显然不优。
由于把定义域分为了 \(\log n\) 个区间，每个区间递归下传标记又是 \(\log n\) 的，于是修改操作一次 \(\log^2 n\)。
查询的话直接套用线段树单点查，\(\log n\) 的。
#include <bits/stdc++.h>
#define llong long long
#define N 100005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}constexpr int n = 39989;
constexpr double eps = 1e-8;
int q, cnt;struct Seg{double k, b; int id;
} a[N];
inline double gety(Seg s, double x){return s.k*x+s.b;
}
inline int cmp(double a, double b){if(fabs(a-b) < eps) return 0;return a>b ? 1 : -1;
}
Seg val[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
inline void insert(int L, int R, Seg k, int x = 1, int l = 1, int r = n){if(L <= l && R >= r){if(val[x].id == 0){val[x] = k;return;}Seg s1 = val[x], s2 = k;if(cmp(gety(s1, mid), gety(s2, mid)) < 0 || (cmp(gety(s1, mid), gety(s2, mid))==0&&s1.id>s2.id)) swap(s1, s2);val[x] = s1;if(cmp(gety(s1, l), gety(s2, l)) < 0 || (cmp(gety(s1, l), gety(s2, l))==0&&s1.id>s2.id)) insert(L, R, s2, ls(x), l, mid );else if(cmp(gety(s1, r), gety(s2, r)) < 0 || (cmp(gety(s1, r), gety(s2, r))==0&&s1.id>s2.id)) insert(L, R, s2, rs(x), mid+1, r);return;}if(L <= mid) insert(L, R, k, ls(x), l, mid );if(R > mid) insert(L, R, k, rs(x), mid+1, r);return;
}
inline Seg query(int pos, int x = 1, int l = 1, int r = n){Seg res = val[x];if(l == r) return res;if(pos <= mid){Seg tmp = query(pos, ls(x), l, mid);if(!res.id || cmp(gety(tmp, pos),gety(res, pos))>0 || (!cmp(gety(tmp, pos),gety(res, pos))&&tmp.id<res.id)) res = tmp;}else{Seg tmp = query(pos, rs(x), mid+1, r);if(!res.id || cmp(gety(tmp, pos),gety(res, pos))>0 || (!cmp(gety(tmp, pos),gety(res, pos))&&tmp.id<res.id)) res = tmp;}return res;
}int lstans;int main(){read(q);while(q--){int op, x1, y1, x2, y2;read(op);if(op == 0){read(x1), x1 = (x1+lstans-1)%39989+1;printf("%d\n", lstans = query(x1).id);}if(op == 1){read(x1, y1, x2, y2);x1 = (x1+lstans-1)%39989+1, y1 = (y1+lstans-1)%1000000000+1;x2 = (x2+lstans-1)%39989+1, y2 = (y2+lstans-1)%1000000000+1;if(x1 > x2) swap(x1, x2), swap(y1, y2);double k = 1.0*(y2-y1)/(x2-x1);double b = y1-x1*k;++cnt, a[cnt] = (Seg){k, b, cnt};insert(x1, x2, a[cnt]);}}return 0;
}