线段树分治

线段树分治即对时间轴建立线段树(标记永久化)。

这样我们将所有操作离线后,对于每个修改的操作,它所能影响的就是一个时间段。可以直接在线段树上更新。

查询则变成了一个单点查询(某个时间点)。

它的一个好处是可以把删除操作去掉。如果删除操作不好做的话可以考虑用线段树分治来解决。

bzoj4311 为例。

你要维护一个向量集合,支持以下操作:

  1. 插入一个向量 $(x,y)$。
  2. 删除插入的第 $i$ 个向量。
  3. 查询当前集合与 $(x,y)$ 点积的最大值是多少。

将所有操作离线后,我们就可以知道每一个向量所存在的时间段。然后在线段树上相应的区间中插入这个向量。

因为答案一定在上凸壳上,所以线段树上每个节点维护一个上凸壳。

查询就是单点查询,在路径上的每一个节点都三分一下最大值。

#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define Lson l, m, lson
#define Rson m + 1, r, rson
const int maxn = 2e5 + 5;
typedef long long ll;
struct Point {
  ll x, y;
  Point(ll x = 0, ll y = 0) : x(x), y(y) {}
  bool operator<(const Point &a) const {
    if (x == a.x) return y < a.y;
    return x < a.x;
  }
};
Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
ll Cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
ll Cross(Point A, Point B, Point C) { return Cross(B - A, C - A); }
ll dot(Point A, Point B) { return A.x * B.x + A.y * B.y; }

vector<Point> seg[maxn << 2];
ll ans;

struct Vector {
  int x, y, id;
  int in, out;
  Vector(int x = 0, int y = 0, int id = 0, int in = 0, int out = 0)
      : x(x), y(y), id(id), in(in), out(out) {}
};
struct Query {
  int x, y, id;
  Query(int x = 0, int y = 0, int id = 0) : x(x), y(y), id(id) {}
};
vector<Vector> vec;
vector<Query> query;

void build(int l, int r, int rt) {
  int n = seg[rt].size(), k = 0;
  sort(seg[rt].begin(), seg[rt].end());
  vector<Point> tmp(2 * n);
  for (int i = 0; i < n; tmp[k++] = seg[rt][i++])
    while (k > 1 && Cross(tmp[k - 2], tmp[k - 1], seg[rt][i]) >= 0) --k;
  tmp.resize(k);
  seg[rt] = tmp;
  if (l == r) return;
  int m = l + r >> 1;
  build(Lson);
  build(Rson);
}
void update(int l, int r, int rt, int L, int R, int x, int y) {
  if (L <= l && R >= r) {
    seg[rt].push_back(Point(x, y));
    return;
  }
  int m = l + r >> 1;
  if (L <= m) update(Lson, L, R, x, y);
  if (m + 1 <= R) update(Rson, L, R, x, y);
}

void find(int rt, Point p) {
  int l = 0, r = seg[rt].size() - 1;
  int m1, m2;
  while (r - l >= 3) {
    m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if (dot(seg[rt][m1], p) > dot(seg[rt][m2], p))
      r = m2;
    else
      l = m1;
  }
  for (int i = l; i <= r; i++) ans = max(ans, dot(seg[rt][i], p));
}
void ask(int l, int r, int rt, int p, int x, int y) {
  if (seg[rt].size() > 0) find(rt, Point(x, y));
  if (l == r) return;
  int m = l + r >> 1;
  if (p <= m)
    ask(Lson, p, x, y);
  else
    ask(Rson, p, x, y);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0, op, x, y, id; i < n; i++) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &x, &y);
      int m = vec.size();
      vec.push_back(Vector(x, y, m + 1, i + 1, n));
    } else if (op == 2) {
      scanf("%d", &id);
      vec[id - 1].out = i + 1;
    } else {
      scanf("%d%d", &x, &y);
      query.push_back(Query(x, y, i + 1));
    }
  }
  for (int i = 0; i < vec.size(); i++) {
    Vector &v = vec[i];
    update(1, n, 1, v.in, v.out, v.x, v.y);
  }

  build(1, n, 1);
  for (int i = 0; i < query.size(); i++) {
    Query &q = query[i];
    ans = 0;
    ask(1, n, 1, q.id, q.x, q.y);
    printf("%lld\n", ans);
  }
}
最后修改:2020 年 07 月 30 日 10 : 19 PM