P8300 [COCI2012-2013#2] INSPEKTOR 题解
伟大的王夫子
·
·
题解
这题其实想通了很简单。
就相当于是给你几个函数 b = kx+y，将当前时间 T 代入到区间 [A, B] 所有函数当中，求所得的最大值。还要求支持修改。
这个东西貌似很难维护。如果用线段树等数据结构，比较难维护区间凸包的合并。所以我们选择分块，每次修改暴力重构凸包，查询则可以在凸包上二分，边角暴力。
那我们先推一下式子。
当 x_1 < x_2 时，
故 $\forall x_1 < x_2 < x_3$，如果 $x_2$ 成为最优解，那么 $\dfrac{y_3-y_2}{x_3-x_2} \le -k \le \dfrac{y_2-y_1}{x_2-x_1}$。
即我们应该维护一个斜率递减的上凸包。
注意这里 $x$ 要保证有序，所以我们用一个可重集维护凸包中的点，否则每次排序常数太大。并且 $x$ 相等时，保留 $y$ 大的。
查询我们可以二分第一个满足其与下一个点的斜率 $\le -k$ 的点，并更新答案。
而修改就当于如果本来这个位置有公司了就删除，然后加入一个新的公司。用 multiset 维护点集，并且每次暴力重构凸包。
设分块一块长度为 $len$，那么时间复杂度为 $O(\dfrac{nm\log len}{len}+mlen)$。经实际测验，$len$ 取 100 最快。注意卡常，不要用 vector，可以加上快读、快输。~~如果实在卡不过去就开 O2 吧，反正我是卡过去了。~~
关于取等问题：这个我也没有细心研究过，一个很好的方法时要么全部加等号，要么全部不加。应该不会有大问题。
参考代码 （未加 O2，20.58s）
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using LL = long long;
const int B = 100;//长度
template <class T>
inline void Rd(T &x) {
x = 0;
bool f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
if (f)
x = -x;
}
template <class T>
inline void writeInt(T x) {
if (x < 0) putchar('-'), x = -x;
char c[50];
int cnt = 0;
do {
c[++cnt] = x % 10 + '0';
x /= 10;
} while (x);
for (int i = cnt; i; --i) putchar(c[i]);
}
struct Poi {
LL x, y;
Poi() {
}
Poi(LL _x, LL _y) {
x = _x, y = _y;
} //kx + y
bool operator < (const Poi &a) const {
return x < a.x || (x == a.x && y > a.y);
}
} a[N];
bool v[N];
double slope(const Poi &a, const Poi &b) {
return 1.0 * (a.y - b.y) / (a.x - b.x);
}
struct DS {
int l = 1, r = 0;
Poi q[B + 10], a[B + 10];
multiset<Poi> s;
void Del(Poi x) {
s.erase(s.find(x));
}
void Ins(Poi x) {
s.insert(x);
}
bool empty() {
return s.empty();
}
void rebuild() {
l = 1, r = 0;
int n = 0;
for (auto v : s) a[++n] = v;
n = unique(a + 1, a + n + 1, [](const Poi &a, const Poi &b) {return a.x == b.x;}) - a - 1;
for (int i = 1; i <= n; ++i) {
while (l < r && slope(q[r - 1], q[r]) < slope(q[r], a[i])) --r;
q[++r] = a[i];
}
}
LL query(int v) {
int L = l, R = r;
while (L < R) {
int mid(L + R >> 1);
if (slope(q[mid], q[mid + 1]) < -v) R = mid;
else L = mid + 1;
}
return 1ll * v * q[L].x + q[L].y;
}
} b[N / B + 10];
int n, m;
int main() {
Rd(n), Rd(m);
for (int i = 1, op, T; i <= m; ++i) {
Rd(op), Rd(T);
if (op == 1) {
int K, Z, S;
Rd(K), Rd(Z), Rd(S);
int bK = (K - 1) / B + 1;
if (v[K]) b[bK].Del(a[K]);
v[K] = 1;
b[bK].Ins(a[K] = Poi(Z, S - 1ll * Z * T));
b[bK].rebuild();
} else {
int l, r;
bool flag = 0;
LL ans = -1e18;
Rd(l), Rd(r);
if (l > r) swap(l, r);
int bl = (l - 1) / B + 1, br = (r - 1) / B + 1;
if (br - bl <= 1)
for (int i = l; i <= r; ++i) {
flag |= v[i];
if (v[i]) ans = max(ans, a[i].x * T + a[i].y);
}
else {
for (int i = l; i <= min(n, bl * B); ++i) {
flag |= v[i];
if (v[i]) ans = max(ans, a[i].x * T + a[i].y);
}
for (int i = (br - 1) * B + 1; i <= r; ++i) {
flag |= v[i];
if (v[i]) ans = max(ans, a[i].x * T + a[i].y);
}
for (int i = bl + 1; i < br; ++i) {
flag |= !b[i].empty();
if (!b[i].empty()) ans = max(ans, b[i].query(T));
}
}
if (!flag) puts("nema");
else writeInt(ans), putchar('\n');
}
}
// O(m * len + m * (n / len * log(n) + len))
// len = sqrt(n * log2(n));
}
```