题解 - 「 MLOI 」小兔叽
小兔叽
\(\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}\)
- \(\texttt{dp[u]}\) 表示 \(f_u\)。
- \(\texttt{dpp[u]}\) 表示 \(g_u\)。
#include
#include
#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
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;
}