首页 > 其他分享 >李超线段树

李超线段树

时间：2024-09-06 18:16:00浏览次数：4  
标签：Pii val int 线段 tr 李超 mid pos

适用

用来解决给定一次函数的系数,即\(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

相关文章

  • 线段树
    查找区间最大最小值查看代码#include<bits/stdc++.h>//维护最大最小值#defineintlonglongusingnamespacestd;intn,q;inttree1[4000000],tree2[4000000],a[1000000];voidbuild(intp,intl,intr){if(l==r){tree1[p]=a[l];tree2[p]=......
  • 变种线段树 提高篇
    可持久化线段树注意，它的全称为可持久化权值线段树。例题\(1\)：可持久化线段树2首先我们考虑几个暴力：对于每次询问，找出区间中的所有数，直接排序求第\(k\)小。这样做的时间复杂度为\(O(nq\logn)\)的。对于每次询问，建出一棵权值线段树，然后权值线段树上二分查找即可。发现......
  • 线段树分治
    前置知识：可撤销化并查集注意：可撤销化并查集的作用和删边不一样，其只能撤销最近的一次操作。既然只需撤销，那么只需在合并并查集时用个vector记录下合并的哪两个点，撤销时就直接还原就行了。这里要强调一下，可撤销化并查集不能路径压缩，只能启发式合并。代码intf[MAXN],sz[MAXN......
  • codeforces做题记录（1924B）& 回顾线段树
    1924B.SpaceHarbour题意：n个点排成一行，其中某些点上面建有港湾，港湾有一个权值，对每个点我们定义点的权值为“左边（包括自己）第一个港湾上的权值\(\times\)到右边（包括自己）第一个港湾的距离”（保证在一开始1号和n号点上都有港湾）。有q次操作：操作1给定x和v，表示在x点上建立权值为v的......
  • 优化半群结构的线段树信息维护
    今天在做区间历史和。感觉给每个标记一个含义实在太抽象了，遂听从白神建议学习矩阵维护信息和优化半群结构。前置知识：大魔法师，用矩阵维护轮换信息。我们发现区间历史和事实上是对“历史和”变量被“和”变量轮换加法的结果，不知道为什么以前没反应过来和大魔法师有关。区间加和区......
  • 线段覆盖问题
    1.线段不覆盖问题给出\(n\)个线段，选择尽量多的线段使得线段无重叠，问最多可以选多少条线段。解析考虑贪心，将线段按右端点从小到大排序，如果这条线段的左端点大于上一条线段的右端点那就选择这条线段。为什么这么贪是对的呢，因为将右端点排序可以使右边剩余的空间尽量大，那么剩余......
  • Luogu P4425 转盘 题解 [ 黑 ] [ 线段树 ] [ 贪心 ] [ 递归 ]
    转盘：蒟蒻的第一道黑，这题是贪心和线段树递归合并的综合题。贪心破环成链的trick自然不用多说。首先观察题目，很容易发现一个性质：只走一圈的方案一定最优。这个很容易证，因为再绕一圈回来标记前面的和等前面的标记完之后继续走是等价的，并且再绕一圈甚至可能更劣。于是，我们只用走......
  • 线段树
    线段树区间加区间和区间乘法的懒标记优先级高于加法，且会对加法懒标记造成影响voidpush_up(node&u,node&l,node&r){ u.sum=l.sum+r.sum;//}voidpushup(vector<node>&tr,intu){push_up(tr[u],tr[u<<1],tr[u<<1|1]);}voidpush_down(vector<node......
  • 【数据结构】【模板】李超线段树
    李超线段树定义可以看看洛谷的模板题目：作用优化动态规划，如果可以将一个动态规划的转移式子转化为\(y=kx+b\)的形式，那么我们可以边转移边将\(y=kx+b\)这条线段放入李超线段树，然后在下次转移时，直接调用下次计算出来的\(x\)位置上的最大值或最小值。（结合题目理解......
  • Luogu P4588 数学运算 题解 [ 绿 ] [ 线段树 ]
    LuoguP4588数学运算。虽然是一个很典的题，但里面的思想还是比较值得记录的。假做法一开始看到此题还以为是乘法逆元的模板题，但看到\(m\)与\(M\)不互质，就知道这种做法是假的了。注意exgcd虽然能求模数为合数的逆元，但是要是两数不互质就什么算法都搞不了了。因此，本题不能......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99