\(\text{Solution}\)

记 \(k\) 这个办公室相关属性有 \(t,z,s\)

对于以后的某一天 \(T\)，其账户余额为 \((T-t)z+s\)

要最大化这东西，不妨另 \(b=(T-t)z+s\)

则等价于 \(tz-s=Tz-b\)，要最大化 \(-b\) 即最小化 \(b\)

把 \((z,tz-s)\) 视为坐标系一点，用斜率为 \(T\) 的直线过点，最小化截距

且 \(T\) 递增

那么就是很简单的维护凸包的题了

但发现能用的办公室为一个区间，且需要支持加点和删点

考虑分块，每个块内维护一个凸包

修改只涉及一个点所在的块，直接暴力重构凸包

为支持操作需要辅助数组记录一些信息，这些都是小细节了

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <cmath>

#define RE register

#define IN inline

#define LL long long

using namespace std;

const int N = 1e5 + 5, M = 325;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m, st[M], ed[M], id[N], L[M], R[M], bz[N], bb[N], aa[M][M], ct[M];

struct Point{LL x, y;}a[N], b[M][M], c[M][M];

IN void Prework()

{

	int num = sqrt(n);

	for(RE int i = 1; i <= num; i++)

	{

		st[i] = ed[i - 1] + 1, ed[i] = (i == num ? n : ed[i - 1] + n / num);

		for(RE int j = st[i]; j <= ed[i]; j++) id[j] = i;

	}

}

IN double slope(Point a, Point b)

{

	if (a.x == b.x) return INF;

	return 1.0 * (a.y - b.y) / (a.x - b.x);

}

IN void Rebuild(int l)

{

	int x = id[l];

	if (bb[l])

	{

		for(RE int i = bb[l]; i < ct[x]; i++) b[x][i] = b[x][i + 1], bb[aa[x][i] = aa[x][i + 1]] = i;

		--ct[x], bb[l] = 0;

	}

	for(RE int i = 1; i <= ct[x]; i++)

	if (b[x][i].x > a[l].x || (b[x][i].x == a[l].x && b[x][i].y > a[l].y))

	{

		for(RE int j = ct[x] + 1; j > i; j--) b[x][j] = b[x][j - 1], bb[aa[x][j] = aa[x][j - 1]] = j;

		b[x][i] = a[l], aa[x][i] = l, bb[l] = i, ++ct[x];

		break;

	}

	if (!bb[l]) b[x][++ct[x]] = a[l], aa[x][ct[x]] = l, bb[l] = ct[x];

	L[x] = R[x] = 0;

	for(RE int i = 1; i <= ct[x]; i++)

	{

		while (R[x] && slope(c[x][R[x]], c[x][R[x] - 1]) > slope(b[x][i], c[x][R[x]])) --R[x];

		c[x][++R[x]] = b[x][i];

	}

	if (R[x]) L[x] = 1;

}

IN LL query(int x, int T)

{

	while (L[x] < R[x] && slope(c[x][L[x]], c[x][L[x] + 1]) < T) ++L[x];

	if (L[x]) return c[x][L[x]].x * T - c[x][L[x]].y;

	return -INF;

}

IN LL Query(int T, int l, int r)

{

	if (l > r) swap(l, r);

	int x = id[l], y = id[r]; LL ans = -INF;

	if (x == y)

	{

		for(RE int i = l; i <= r; i++) if (bz[i]) ans = max(ans, a[i].x * T - a[i].y);

		return ans;

	}

	for(RE int i = l; i <= ed[x]; i++) if (bz[i]) ans = max(ans, a[i].x * T - a[i].y);

	for(RE int i = st[y]; i <= r; i++) if (bz[i]) ans = max(ans, a[i].x * T - a[i].y);

	for(RE int i = x + 1; i < y; i++) ans = max(ans, query(i, T));

	return ans;

}

IN void read(int &x)

{

	x = 0; char ch = getchar(); int f = 1;

	for(; !isdigit(ch); f = (ch == '-' ? -1 : f), ch = getchar());

	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

	if (f - 1) x = ~x + 1;

}

int main()

{

	read(n), read(m), Prework();

	for(RE int op, t, k, z, s; m; --m)

	{

		read(op), read(t), read(k), read(z);

		if (op == 1) read(s), bz[k] = 1, a[k] = (Point){z, (LL)z * t - s}, Rebuild(k);

		else{

			LL ans = Query(t, k, z);

			if (ans == -INF) printf("nema\n");

			else printf("%lld\n", ans);

		}

	}

}

巴特西

JZOJ 3167.查税

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章