xjb写了写……我评测时候心脏跳得贼快（逃

考虑如果知道了那一段区间的凸包那么怎么做。首先如果向量是往上指的话，一定在上凸壳上找点比较好，反之则在下凸壳上找点比较好（放到坐标系里脑补一下？）。然后我们观察一点，在上凸壳上的最优解往两边的点会越来越劣，所以这玩意是个上凸函数，可以三分答案（我才学的整数三分啊）。

但区间凸包求起来复杂度很爆炸啊……考虑用线段树搞？观察到一点，我们区间查询所使用的线段树节点一定是只包含了已经加进来的点。所以说，一个线段树节点的凸包需要被求的情况只有一种，那就是这个节点完全已加入点被覆盖了。那每次修改之后看是否一个节点完全被已加入点覆盖，如果被完全覆盖的话才去求它的凸包。

这样一来，线段树上每个节点之多会被求一次凸包。线段树有\(\log n\)层，每一层所有节点的大小加起来是\(n\)，所以求凸包耗费的总复杂度是\(n\log^2 n\)级别的。

其实这就是用线段树模拟二进制分组？

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <climits>
#include <cassert>
using ll = long long;
using T = ll;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
  if((a.x - b.x) == 0LL) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
  std::sort(P + 1, P + 1 + L, cmp);
  for(int i = 1; i <= L; i ++) {
    if(i != 1 && (P[i].x - P[i - 1].x) == 0LL) continue;
    while(bot.size() > 1 && (times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0LL) {
      bot.pop_back();
    }
    bot.push_back(P[i]);
  }
  for(int i = L; i >= 1; i --) {
    if(i != L && (P[i].x - P[i + 1].x) == 0LL) continue;
    while(top.size() > 1 && (times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0LL) {
      top.pop_back();
    }
    top.push_back(P[i]);
  }
  std::reverse(top.begin(), top.end());
}

const int maxn = 400005;
const int maxno = maxn << 2;
const int N = 400000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
  static Point tmp[maxn];
  const int lc = o << 1, rc = o << 1 | 1;
  const bool used = zen[o];
  zen[o] = (zen[lc] && zen[rc]);
  if(zen[o] != used) {
    std::copy(P + L, P + R + 1, tmp + 1);
    int len = R - L + 1;
    andrew(tmp, len, bot[o], top[o]);
  }
}
void modify(int o, int L, int R, const int &p, const Point &v) {
  if(L == R) {
    zen[o] = true;
    P[L] = v;
    bot[o].push_back(v); top[o].push_back(v);
  } else {
    const int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o, L, R);
  }
}
inline T search(const std::vector<Point> &vec, const Point &p) {
  int l = 0, r = vec.size() - 1;
  while(r - l > 2) {
    int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
    if(dot(p, vec[lm]) > dot(p, vec[rm])) {
      r = rm;
    } else {
      l = lm;
    }
  }
  T ans = LLONG_MIN;
  for(int i = l; i <= r; i ++) {
    ans = std::max(ans, dot(p, vec[i]));
  }
  return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const Point &p) {
  if(ql <= L && R <= qr) {
    if(p.y > 0LL) {
      return search(top[o], p);
    } else {
      return search(bot[o], p);
    }
  } else {
    int M = (L + R) / 2;
    T ans = LLONG_MIN;
    if(ql <= M) {
      ans = std::max(ans, query(o << 1, L, M, ql, qr, p));
    }
    if(qr > M) {
      ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, p));
    }
    return ans;
  }
}

inline int decode(int x, long long lastans) {
  return x ^ (lastans & 0x7fffffff);
}
int main() {
  int q; char buf[4]; scanf("%d%s", &q, buf);
  bool typ_E = (buf[0] == 'E' && buf[1] == char(0));
  T las = 0LL;
  int tot = 0;
  while(q --) {
    char op[4]; scanf("%s", op);
    if(op[0] == 'A') {
      T x, y; scanf("%lld%lld", &x, &y);
      if(!typ_E) {
        x = decode(x, las); y = decode(y, las);
      }
      tot ++;
      modify(1, 1, N, tot, Point(x, y));
    } else {
      T x, y, l, r; scanf("%lld%lld%lld%lld", &x, &y, &l, &r);
      if(!typ_E) {
        x = decode(x, las); y = decode(y, las);
        l = decode(l, las); r = decode(r, las);
      }
      las = query(1, 1, N, l, r, Point(x, y));
      printf("%lld\n", las);
    }
  }
  return 0;
}

• 相关文章
• 全局相关文章