自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:37:49，当前版本为作者最后更新于2022-07-06 22:08:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题其实想通了很简单。

就相当于是给你几个函数 $b = kx+y$，将当前时间 $T$ 代入到区间 $[A, B]$ 所有函数当中，求所得的最大值。还要求支持修改。

这个东西貌似很难维护。如果用线段树等数据结构，比较难维护区间凸包的合并。所以我们选择分块，每次修改暴力重构凸包，查询则可以在凸包上二分，边角暴力。

那我们先推一下式子。

当 $x_1 < x_2$ 时，

$kx_1 + y_1 \le kx_2 +y_2 \Leftrightarrow k(x_1-x_2)\le y_2-y_1 \Leftrightarrow -k \le\dfrac{y_2-y_1}{x_2-x_1}$。

故 $\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）

#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));
}