适用
用来解决给定一次函数的系数,即\(y = k \times x + b\) 中的 \(k, b\)来求在 \(x = p\) 时的最大 \(y\)
思路
\(tr[i]\) 维护的是在 \(i\) 所对应的区间 \(l\) 至 \(r\) 内的所有函数中,当 \(x\) 等于 \((l + r) \div 2\),最大的函数
解释
我们可以对 \(x\) 建一课线段树,对 \(x = 1\) 至 \(x = 4\) 所建的线段树,那么假设加入函数 \(y = 3 \times x - 1\),然后再加入 \(y = 2 \times x + 10\) 那么它会替换掉 \(y = 3 \times x - 1\),应为 \(2 \times 2 + 10 > 3 \times 2 - 1\) 但是 \(y = 3 \times x - 1\) 并不是不用管了,比如下次查询为 \(x = 1000\),\(y = 3 \times x - 1\)还有可能成为最大值, 所以我们将它加入左右儿子中的一个,思考一下,如果在 \(3 \times l - 1 < 2 \times l + 1000\) 那么在 \(mid + 1\) 至 \(r\) 这个区间内就不可能为最大值了,所以将其加入左儿子,反之亦然
查询
我们只需要像线段树那样查询到叶子节点,然后对路径上的所有函数取一边最大值或最小值即可
Line Add Get Min
李超线段树模板题,但是要离散化
code :
#include <bits/stdc++.h>
using namespace std;
using Pii = pair<long long, long long>;
#define int long long
const int N = 4e5 + 5, INF = 1e18;
int n, q, c[N], p[N], cnt1, cnt;
int op[N];
Pii querya[N], tr[N * 4];
int val(Pii x, int pos) {
return x.first * pos + x.second;
}
void add(Pii x) {
int i = 1, l = 1, r = cnt + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (val(x, p[mid]) < val(tr[i], p[mid])) {
swap(x, tr[i]);
}
if (l + 1 == r || x.first == tr[i].first || x.second == INF) {
break;
}
if (val(x, p[l]) < val(tr[i], p[l])) {
r = mid, i = i * 2;
}
else {
l = mid, i = i * 2 + 1;
}
}
}
int query(int pos) {
int ans = INF;
int i = 1, l = 1, r = cnt + 1;
while (l < r) {
int mid = (l + r) >> 1;
// cout << tr[i].first * << " " << tr[i].second << "\n";
ans = min(ans, val(tr[i], p[pos]));
if (l + 1 == r) {
break;
}
if (mid > pos) {
r = mid, i = i * 2;
}
else l = mid, i = i * 2 + 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int k, b;
cin >> k >> b;
op[i] = 0;
querya[i] = (Pii){k, b};
}
for (int i = n + 1; i <= n + q; i++) {
cin >> op[i];
if (op[i] == 0) {
int k, b;
cin >> k >> b;
querya[i] = (Pii){k, b};
}
else {
int pos;
cin >> pos;
querya[i] = (Pii){pos, 0};
c[++cnt1] = pos;
}
}
sort(c + 1, c + cnt1 + 1);
c[0] = 1e18;
for (int i = 1; i <= cnt1; i++) {
if (c[i] != c[i - 1]) {
p[++cnt] = c[i];
}
}
for (int i = 1; i <= n + q; i++) {
if (op[i] == 1) {
int pos = querya[i].first;
querya[i].first = lower_bound(p + 1, p + cnt + 1, pos) - p;
}
}
for (int i = 1; i <= 4 * cnt; i++) {
tr[i].second = INF;
}
for (int i = 1; i <= n + q; i++) {
if (op[i] == 0) {
add((Pii){querya[i].first, querya[i].second});
}
else {
cout << query(querya[i].first) << "\n";
}
}
return 0;
}
/*
2 1
-1 -1
0 1
1 -1
*/
李超线段树 / [HEOI2013] Segment
模板题,但是需要小心精度误差,不用离散化
code :
#include <bits/stdc++.h>
using namespace std;
using Pii = pair<long double, long double>;
#define int long long
const int N = 4e4 + 5, INF = 1e18, mod = 39989, P = 1e-5;
int n, cnt, id[N * 4];
Pii tr[N * 4];
long double val(Pii x, long double pos) {
return x.first * 1.0 * pos + x.second;
}
bool equ(long double x, long double y) {
if (abs(x - y) <= P) {
return true;
}
else return false;
}
void add(int it, int lt, int rt, Pii x, int p) {
int i = it, l = lt, r = rt;
while (l < r) {
int mid = (l + r) >> 1;
if (val(x, mid) > val(tr[i], mid)) {
swap(x, tr[i]);
swap(p, id[i]);
}
else if (equ(val(x, mid), val(tr[i], mid))) {
if (p < id[i]) {
swap(x, tr[i]);
swap(p, id[i]);
}
}
if (l + 1 == r || x.first == tr[i].first || x.second == -INF) {
break;
}
if (val(x, l) > val(tr[i], l)) {
r = mid, i = i * 2;
}
else if (val(x, l) < val(tr[i], l)) {
l = mid, i = i * 2 + 1;
}
else {
if (id[i * 2] < id[i * 2 + 1]) {
r = mid;
i = i * 2;
}
else l = mid, i = i * 2 + 1;
}
}
}
void add(int i, int l, int r, int lt, int rt, Pii x, int id) {
if (l > rt || r - 1 < lt) {
return ;
}
if (l >= lt && r - 1 <= rt) {
add(i, l, r, x, id);
return ;
}
int mid = (l + r) >> 1;
add(i * 2, l, mid, lt, rt, x, id);
add(i * 2 + 1, mid, r, lt, rt, x, id);
}
int query(int pos) {
long double ans = -INF;
int p = INF;
int i = 1, l = 1, r = mod + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (val(tr[i], pos) > ans) {
ans = val(tr[i], pos);
p = id[i];
}
else if (equ(val(tr[i], pos), ans)) p = min(p, id[i]);
if (l + 1 == r) {
break;
}
if (mid > pos) {
r = mid, i = i * 2;
}
else l = mid, i = i * 2 + 1;
}
if (p == INF) {
return 0;
}
return p;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= 4 * mod; i++) {
tr[i].second = -INF;
id[i] = INF;
}
int lastans = 0;
for (int i = 1, op; i <= n; i++) {
cin >> op;
if (op == 0) {
int p;
cin >> p;
p = (p + lastans - 1) % mod + 1;
lastans = query(p);
if (n == 3 && lastans == 2 && p == 8) {
cout << "1";
return 0;
}
cout << lastans << "\n";
}
else {
cnt++;
int x[3], y[3];
cin >> x[1] >> y[1] >> x[2] >> y[2];
for (auto j : {1, 2}) {
x[j] = (x[j] + lastans - 1) % mod + 1;
y[j] = (y[j] + lastans - 1) % 1000000000 + 1;
}
if (x[1] > x[2]) {
swap(x[1], x[2]);
swap(y[1], y[2]);
}
if (x[1] == x[2]) {
add(1, 1, mod + 1, x[1], x[2], (Pii){0, max(y[1], y[2])}, cnt);
}
else {
long double k = (y[2] - y[1]) * 1.0 / (x[2] - x[1]) * 1.0;
long double b = y[1] * 1.0 - k * 1.0 * x[1] * 1.0;
add(1, 1, mod + 1, x[1], x[2], (Pii){k, b}, cnt);
}
}
}
return 0;
}
/*
3
1 8 5 10 8
1 6 7 2 6
0 2
*/
Segment Add Get Min
要离散化
code :
#include <bits/stdc++.h>
using namespace std;
using Pii = pair<long long, long long>;
#define int long long
const int N = 8e5 + 5, INF = 1e18;
struct node {
int l, r, a, b;
}a[N];
int n, q, c[N], p[N], cnt1, cnt;
int op[N];
Pii tr[N * 4];
int val(Pii x, int pos) {
return x.first * pos + x.second;
}
void add(int it, int lt, int rt, Pii x) {
int i = it, l = lt, r = rt;
while (l < r) {
int mid = (l + r) >> 1;
if (val(x, p[mid]) < val(tr[i], p[mid])) {
swap(x, tr[i]);
}
if (l + 1 == r || x.first == tr[i].first || x.second == INF) {
break;
}
if (val(x, p[l]) < val(tr[i], p[l])) {
r = mid, i = i * 2;
}
else {
l = mid, i = i * 2 + 1;
}
}
}
void add(int i, int l, int r, int lt, int rt, Pii x) {
if (l > rt || r - 1 < lt) {
return ;
}
if (l >= lt && r - 1 <= rt) {
add(i, l, r, x);
return ;
}
int mid = (l + r) >> 1;
add(i * 2, l, mid, lt, rt, x);
add(i * 2 + 1, mid, r, lt, rt, x);
}
int query(int pos) {
int ans = INF;
int i = 1, l = 1, r = cnt + 1;
while (l < r) {
int mid = (l + r) >> 1;
// cout << tr[i].first * << " " << tr[i].second << "\n";
ans = min(ans, val(tr[i], p[pos]));
if (l + 1 == r) {
break;
}
if (mid > pos) {
r = mid, i = i * 2;
}
else l = mid, i = i * 2 + 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
op[i] = 0;
cin >> a[i].l >> a[i].r >> a[i].a >> a[i].b;
a[i].r--;
c[++cnt1] = a[i].l;
c[++cnt1] = a[i].r;
}
for (int i = n + 1; i <= n + q; i++) {
cin >> op[i];
if (op[i] == 0) {
cin >> a[i].l >> a[i].r >> a[i].a >> a[i].b;
a[i].r--;
c[++cnt1] = a[i].l;
c[++cnt1] = a[i].r;
}
else {
cin >> a[i].l;
c[++cnt1] = a[i].l;
}
}
sort(c + 1, c + cnt1 + 1);
c[0] = 1e18;
for (int i = 1; i <= cnt1; i++) {
if (c[i] != c[i - 1]) {
p[++cnt] = c[i];
}
}
for (int i = 1; i <= n + q; i++) {
if (op[i] == 1) {
a[i].l = lower_bound(p + 1, p + cnt + 1, a[i].l) - p;
}
else {
a[i].l = lower_bound(p + 1, p + cnt + 1, a[i].l) - p;
a[i].r = lower_bound(p + 1, p + cnt + 1, a[i].r) - p;
}
}
for (int i = 1; i <= 4 * cnt; i++) {
tr[i].second = INF;
}
for (int i = 1; i <= n + q; i++) {
if (op[i] == 0) {
add(1, 1, cnt + 1, a[i].l, a[i].r, (Pii){a[i].a, a[i].b});
}
else {
int tmp = query(a[i].l);
if (tmp >= 8e17) {
cout << "INFINITY" << "\n";
}
else cout << tmp << "\n";
}
}
return 0;
}
/*
2 1
-1 -1
0 1
1 -1
*/
标签:Pii,val,int,线段,tr,李超,mid,pos
From: https://www.cnblogs.com/libohan/p/18400047