小兔叽

\(\texttt{Link}\)

简单题意

有 \(n\) 个小木桩排成一行，第 \(i\) 个小木桩的高度为 \(h_i\)，分数为 \(c_i\)。

如果一只小兔叽在第 \(i\) 个小木桩上，她会获得 \(c_i\) 的分数；同时，如果 \((|i - j| \neq 1) \wedge (h_j < h_i) \wedge (\forall \min\{i, j\} < k < \max\{i, j\}, h_k < h_i)\)，那么她可以从第 \(i\) 个小木桩跳跃到第 \(j\) 个小木桩上；当然，她也可以停止跳跃。

记 \(f_i\) 表示小兔叽从第 \(i\) 个小木桩开始跳跃获得的总分数的最大值。

请你求出 \(\sum\limits_{i = 1}^{n} f_i\) 和 \(\mathrm{xor} _ {i = 1} ^ {n} |f_i|\)。

数据范围

对于 \(100\%\) 的数据：满足 \(1 \leq n \leq {3 \times 10^6}\)，\(\forall 1 \leq i \leq n, \ 1 \leq h_i \leq {10}^{18} \wedge |c_i| \leq {10}^{10}\)。

\(\texttt{Solution}\)

由于小兔叽只能往低处跳，考虑建一棵笛卡尔树，满足大根堆性质，即 \(h_{f_u} \geq h_u\)。

\(\texttt{lson[u]}\) 表示 \(u\) 的左儿子。
\(\texttt{rson[u]}\) 表示 \(u\) 的右儿子。

\(\texttt{code}\)：

void build(int u)

{

	while (top && h[u] > h[S[top]]) lson[u] = S[top--];

	rson[S[top]] = u; S[++top] = u;

}

其中 \(\texttt{h[u] > h[S[top]]}\) 可以使得 \(h_{f_u} = h_u\) 的取等条件为 \(\texttt{rson[f[u]] = u}\)；当然如也写成 \(\texttt{h[u] >= h[S[top]]}\)，这样取等条件就为 \(\texttt{lson[f[u]] = u}\)。

考虑 \(\texttt{dp}\)：

定义 \(L_u\) 表示以 \(u\) 为根的子树对应的区间的左端点。
定义 \(R_u\) 表示以 \(u\) 为根的子树对应的区间的右端点。
定义 \(f_u\) 表示小兔叽从第 \(u\) 个小木桩开始跳跃获得的总分数的最大值。
定义 \(g_u\) 表示 \(\max\{f_i \ | \ L_u < i < R_u \}\)，严格小于，即不包含两个端点。

考虑一个结点 \(u\) 的状态转移：

\(g_u\) 和初始值为 \(0\)，\(f_u\) 初始值为 \(c_u\)。
考虑左儿子：
- \(g_u = \max\{ g_u, g_{\texttt{lson[u]}} \}\)
- \(g_u = \max\{ g_u, g_{u - 1}\}, {u - 1} > L_u\)
- \(f_u = \max\{ f_u, c_u + g_{\texttt{lson[u]}} \}, {u - 1} > L_u\)
- \(f_u = \max\{ f_u, c_u + f_{L_u} \}, {u - 1} > L_u\)
考虑右儿子：
- \(g_u = \max\{ g_u, g_{\texttt{rson[u]}} \}\)
- \(g_u = \max\{ g_u, g_{u + 1} \}, {u + 1} > R_u\)
- 条件 \({h_{\texttt{rson[u]}} = u} \wedge {\texttt{rson[u]} > {u + 1}}\)：
  - \(f_u = \max\{ f_u, c_u + g_{\texttt{lson[rson[u]]}} \}\)
  - \(f_u = \max\{ f_u, c_u + f_{\texttt{rson[u]} - 1}\}, {\texttt{rson[u]} - 1} > {u + 1}\)
- 条件 \({h_{\texttt{rson[u]}} \neq u} \wedge {{u + 1} < R_u}\)
  - \(f_u = \max\{ f_u, c_u + g_{\texttt{rson[u]}} \}\)
  - \(f_u = \max\{ f_u, c_u + g_{R_u} \}\)
- 条件 \({{u + 1} < R_u}\)
考虑 \(u\) 自己：
- \(g_u = \max\{ g_u, f_u \}, L_u < u < R_u\)

上面与 \(L_u\) 和 \(R_u\) 有关的判断，就是在 \(\texttt{check}\) 与 \(u\) 相邻的结点可不可以对 \(g_u\) 或 \(f_u\) 做贡献。

因为建笛卡尔树的代码中写的是 \(\texttt{h[u] > h[S[top]]}\)，所以只可能出现 \(h_{\texttt{rson[u]} = h_u}\)，不会出现 \(h_{\texttt{lson[u]} = h_u}\)。

注意事项：

\(f_u\) 是在 \(\texttt{long long}\) 范围内的，而 \(\sum\limits_{u = 1}^{n} f_u\) 可能会超出范围。
因为 \(\sum\limits_{u = 1}^{n} f_u\) 超出的范围不会很多，所以令 \(\texttt{mod} = {10}^{18}\) 压 \(2\) 位就可以了。
压位的时候记住要补 \(0\)，同时不要出现前导 \(0\)。
使用题目给出的输入方式，不使用可能会 \(\texttt{TLE}\)。

\(\texttt{code}\)

#include <cstdio>

#include <cassert>

#define int long long

#define uint unsigned int

namespace Read

{

	static const int buf_size = 1 << 12;

	static unsigned char buf[buf_size];

	static int buf_len = 0, buf_pos = 0;

	inline bool isEOF()

	{

		if (buf_pos == buf_len)

		{

			buf_pos = 0; buf_len = fread(buf, 1, buf_size, stdin);

			if (buf_pos == buf_len) return true;

		}

		return false;

	}

	inline char readChar()

	{

		return isEOF() ? EOF : buf[buf_pos++];

	}

	inline int rint()

	{

		int x = 0, fx = 1; char c = readChar();

		while (c < '0' || c > '9') { fx ^= (c == '-'); c = readChar(); }

		while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = readChar(); }

		if (!fx) return -x;

		return x;

	}

	inline void read(int &x)

	{

		x = rint();

	}

	template<typename... Ts>

	inline void read(int &x, Ts &...rest)

	{

		x = rint();

		read(rest...);

	}

} using namespace Read;

namespace Write

{

	static const int buf_size = 1 << 12;

	static char buf[buf_size];

	static int buf_pos = 0;

	inline void flush()

	{

		if (buf_pos)

		{

			fwrite(buf, 1, buf_pos, stdout);

			buf_pos = 0; fflush(stdout);

		}

	}

	inline void writeChar(char x)

	{

		if (buf_pos == buf_size)

		{

			fwrite(buf, 1, buf_size, stdout);

			buf_pos = 0;

		}

		buf[buf_pos++] = x;

	}

	inline void write(int x, char end = 0)

	{

		if (x < 0) { writeChar('-'); x = -x; }

		char str[24]; int n = 0;

		do { str[n++] = ((x % 10) ^ 48); x /= 10; } while (x);

		while (n--) writeChar(str[n]);

		if (end) writeChar(end);

		flush();

	}

} using namespace Write;

namespace Math

{

	int Max(int u, int v) { return (u > v) ? u : v; }

	int Min(int u, int v) { return (u < v) ? u : v; }

} using namespace Math;

const int inf = 1e18;

const int mod = 1e18;

const int MAX_n = 3e6;

int n, top;

int h[MAX_n + 5];

int c[MAX_n + 5];

int S[MAX_n + 5];

int L[MAX_n + 5];

int R[MAX_n + 5];

int lson[MAX_n + 5];

int rson[MAX_n + 5];

int dp[MAX_n + 5];

int dpp[MAX_n + 5];

bool vis[MAX_n + 5];

void build(int u)

{

	while (top && h[u] > h[S[top]]) lson[u] = S[top--];

	rson[S[top]] = u; S[++top] = u;

}

void tree_dp(int u)

{

	L[u] = R[u] = u;

	if (lson[u])

	{

		tree_dp(lson[u]);

		L[u] = L[lson[u]];

		if (u - 1 > L[u])

		{

			dp[u] = Max(dp[u], dpp[lson[u]]);

			dp[u] = Max(dp[u], dp[L[u]]);

			dpp[u] = Max(dpp[u], dp[u - 1]);

		}

		dpp[u] = Max(dpp[u], dpp[lson[u]]);

	}

	if (rson[u])

	{

		tree_dp(rson[u]);

		R[u] = R[rson[u]];

		if (h[rson[u]] == h[u])

		{

			int v = rson[u];

			if (v > u + 1)

			{

				dp[u] = Max(dp[u], dpp[lson[v]]);

				if (v - 1 > u + 1) dp[u] = Max(dp[u], dp[v - 1]);

			}

		}

		else if (u + 1 < R[u]);

		{

			dp[u] = Max(dp[u], dpp[rson[u]]);

			dp[u] = Max(dp[u], dp[R[u]]);

		}

		dpp[u] = Max(dpp[u], dpp[rson[u]]);

		if (u + 1 < R[u]) dpp[u] = Max(dpp[u], dp[u + 1]);

	}

	dp[u] += c[u];

	if (L[u] < u && u < R[u])

		dpp[u] = Max(dpp[u], dp[u]);

}

signed main()

{

	freopen("jump.in", "r", stdin);

	freopen("jump.out", "w", stdout);

	n = rint();

	assert(1 <= n && n <= MAX_n);

	for (int i = 1; i <= n; build(i++))

	{

		read(h[i], c[i]);

		assert(1 <= h[i] && h[i] <= 1e18);

		assert(-1e10 <= c[i] && c[i] <= 1e10);

	}

	tree_dp(rson[0]);

	int res_first = 0, res_second = 0, res_xor = 0;

	for (int i = 1; i <= n; i++)

	{

		int now = dp[i];

		res_first += (res_second + now) / mod;

		res_second = (res_second + now) % mod;

		res_xor ^= ((now > 0) ? now : -now);

	}

	if (!res_first) printf("%lld %lld\n", res_second, res_xor);

	else printf("%lld%018lld %lld\n", res_first, res_second, res_xor);

	return 0;

}

巴特西

题解 - 「MLOI」小兔叽

小兔叽

\(\texttt{Link}\)

简单题意

数据范围

\(\texttt{Solution}\)

\(\texttt{code}\)

最新文章

热门文章