以下按照考场过题顺序和赛后补题顺序

B.Recall

有一个初始为空的栈 \(S\)，现在需要执行一系列操作

+ x：将元素 \(x\) 入栈。

? x：查询元素 \(x\) 是否存在于栈中。

T x：表示元素 \(x\) 存在于栈中。

F x：表示元素 \(x\) 不存在于栈中。

- ：将栈顶元素出栈，保证执行出栈操作时栈非空。

小 G 记录了整个操作过程中所有的 + x、T x 和 F x 操作，但是没有记录任何 - 操作。

现在给出记录下来的 \(n\) 个操作，需要在这些操作之间插入若干个 - 操作，使得构造出的操作序列满足：

  1. 在任意时刻，栈中的所有元素互不相同。
  2. 所有查询操作的结果都与构造出的操作序列一致。
  3. 保证至少存在一种合法的构造方案。
    如果存在多种合法方案，输出任意一种即可。

非常好构造题。

接下来考虑怎么做，首先记录每个元素的入栈位置，考虑如何确定一个元素什么时候应该出栈。开个哈希表 l 维护每个元素最近一次入栈的位置。当遇到 + x 时，说明元素 \(x\) 入栈，记录 l[x]=i 其中 \(i\) 表示当前操作的位置。同时， d 记录每次入栈操作对应的出栈时间。对于第 \(i\) 次操作，如果它是入栈操作，先令 d[i]=-1， \(-1\) 表示暂时没有确定出栈时间。d[i] = i 的作用是：如果这次入栈操作后面没有遇到对应的 T x，那么就在入栈操作结束后立即出栈。

根据查询结果确定出栈时间， 接下来考虑两种查询结果。

  • 情况一：查询结果为 T x

这表示元素 \(x\) 当前必须存在于栈中。可以找到元素 \(x\) 最近一次入栈的位置 l[x]。因此，我们可以将这次入栈操作的出栈时间设置为当前查询位置 d[l[x]]=i 也就是说，元素 \(x\) 至少需要保留到这次查询结束。查询结束之后，就可以考虑将其出栈。

  • 情况二：查询结果为 F x

这表示元素 \(x\) 当前不能存在于栈中。因此，直接从哈希表中删除元素 \(x\) 的记录 l.erase(x[i])

这里需要注意我们不需要显式修改 d。如果某次入栈操作始终没有遇到对应的 T x，那么它的 d 就一直为 \(-1\)，在后面的模拟过程中会被立即出栈。如果它之前遇到过 T x，那么它已经在对应的查询之后出栈了。因此，F x 不需要再额外指定出栈时间。

完成上述处理后，我们就知道了每次入栈操作对应的出栈时间。接下来使用一个栈模拟整个过程。

从前往后枚举所有操作：

  • 如果当前操作是 +，将当前位置压入栈中，并在答案中添加 +。
  • 如果当前操作是 T 或 F，在答案中添加 ?。
    每处理完一个原始操作，就检查当前栈顶元素对应的出栈时间。

如果满足 \(d[stk[top]]\le i\)，说明栈顶元素已经到达允许出栈的时间，将其弹出，并在答案中添加一个 -。不断重复，直到栈为空或者栈顶元素尚未到达出栈时间。

最终得到的字符串就是一种合法的操作序列。

#include #define rint register int
#define int long long
#define endl '\n'using namespace std;const int N = 1e6 + 5;int n;
int d[N], stk[N], top;
char op[N];
unordered_map l;
string ans;signed main() 
{ios::sync_with_stdio(false);cin.tie(0);int T;cin >> T;while (T--) {cin >> n;l.clear();for (rint i = 1; i <= n; i++) {int x;cin >> op[i] >> x;d[i] = -1;if (op[i] == '+') d[i] = i, l[x] = i;else if (op[i] == 'T')  d[l[x]] = i;else  l.erase(x);}top = 0;ans.clear();for (rint i = 1; i <= n; i++) {if (op[i] == '+')  ans += '+', stk[++top] = i;else ans += '?';while (top && d[stk[top]] <= i) top--, ans += '-';}cout << ans << endl;	}return 0;
}

C.Check In

先写的 B 没注意到 C 是签子

开个 map 记录次数就好，没什么好说的

D.Palindrome Shuffle

给定一个只包含小写拉丁字母的字符串。可以对字符串进行如下操作：选择一个连续的子串（可能为空），并对其进行洗牌（重新排列该子串中的字符）。任务是，找出使给定字符串转换为回文所需进行操作的最小子串长度。

已经回文显然答案是零，那么接下来考虑字符串本身不是回文的情况，从两边开始对比，找到不同字符的位置，直到所有字符都能够匹配为止。

既然要从两边开始，不难想到直接拿双指针扫一下，从左边和右边同时开始扫描，直到两边字符相等。如果遇到不等的字符，记录下来该部分的长度，并进行调整，具体实现代码注释

#include #define rint register int
#define int long long
#define endl '\n'using namespace std;int n, res;
int v[30], cnt[30];
string s;signed main()
{//freopen("test1.in", "r", stdin);ios::sync_with_stdio(0);cin.tie(0);int T;cin >> T;while (T--) {cin >> s;n = s.size();res = n;memset(v, 0, sizeof v);for (rint i = 0; i < n; i++) v[s[i] - 'a']++;memset(cnt, 0, sizeof cnt);int j = n - 1;for (rint i = 0; i < n; i++){//s has x 'a', left part has x / 2 'a'//if in the right part, find the same end pointcnt[s[i] - 'a']++;if ((i < n / 2 && 2 * cnt[s[i] - 'a'] > v[s[i] - 'a']) || (i >= n / 2 && s[i] != s[n - i - 1])) break;while (j >= n - i - 1 && j > i && s[j] == s[n - j - 1]) j--;j = max(j, i);res = min(res, j - i);}reverse(s.begin(), s.end());memset(cnt, 0, sizeof cnt);j = n - 1;for (rint i = 0; i < n; i++){cnt[s[i] - 'a']++;if ((i < n / 2 && 2 * cnt[s[i] - 'a'] > v[s[i] - 'a']) || (i >= n / 2 && s[i] != s[n - i - 1])) break;while (j >= n - i - 1 && j > i && s[j] == s[n - j - 1]) j--;j = max(j, i);res = min(res, j - i);}//if (res == 0) res = 2;cout << res << endl;	}return 0;
}

H.Sequence

给定一个长度为 \(n\) 的 \(01\) 串 \(s_1s_2\ldots s_n\)，定义：

\[p_i=\#\{j\le i:s_j\ne s_i\} \]

也就是前 \(i\) 个字符中，与当前位置字符不同的字符数量。

现在不给出原来的 \(01\) 串，而是给出 \(p_1,p_2,\ldots,p_n\) 的一个乱序多重集，要求计算有多少个不同的 \(01\) 串能够产生这个多重集。

非常巧转化题使我大脑飞速旋转，可以把原来的 \(01\) 串转化成一个二维格路问题。考虑从 \((0,0)\) 出发，每次只能向右走一步或者向上走一步。

  • 向右走一步代表当前位置是 0。
  • 向上走一步代表当前位置是 1。

假设当前已经走到了 \((a,b)\)，那么说明前面已经出现了 \(a\) 个 0 和 \(b\) 个 1。此时如果下一步向右走，也就是当前字符为 0，那么前面与它不同的字符就是所有的 1，因此 \(p_i=b\)

如果下一步向上走，也就是当前字符为 1，那么 \(p_i=a\)

所以，当前位于 \((a,b)\) 时，下一步产生的 \(p_i\) 只能是 \(a\) 或者 \(b\)。这样就把原问题转化成了给定所有 \(p_i\) 的出现次数，统计有多少条格路能够产生这个多重集。

cnt[]，记录每个数字出现的次数。从 \((0,0)\) 开始，假设当前坐标满足 \(a\le b\)。

先考虑 \(a 的情况。此时，如果想产生一个值为 \(a\) 的 \(p_i\)，只能选择向上走。因为向右走产生的值是 \(b\)，而 \(b>a\)。因此，所有值为 \(a\) 的步都必须向上走，没有其他选择。

假设 cnt[a]=k，那么就可以直接将这 \(k\) 步全部走完： \(b\leftarrow b+k\)

同时将 cnt[a] 清零，表示值为 \(a\) 的数字已经全部使用。此时如果还有剩余操作，那么下一步就必须向右走，产生的 \(p_i\) 为当前的 \(b\)。因此 \(cnt[b]\) 减少一 ，\(a\leftarrow a+1\)

这样就完成了一轮操作。接下来继续处理新的 \(a\)，直到所有数字都被使用。

特殊情况 \(a=b\) 如果当前处于对角线位置 \((a,a)\)，那么情况就有所不同。

此时向右走和向上走产生的 \(p_i\) 都是 \(a\)。也就是说，当前第一步有两种选择 向右走，当前位置变成 \((a+1,a)\)，向上走，当前位置变成 \((a,a+1)\)。

这两种选择会产生完全对称的后续过程，交换横纵坐标即可得到另一种情况，因此后续方案数量相同。

所以当前答案直接乘以 \(2\) 之后只需要考虑其中一种情况即可。代码实现选择先向上走，把值为 \(a\) 的数字全部处理完，再向右走。

用 t 维护还剩多少个数字没有使用。每轮先将 cnt[a] 个值为 \(a\) 的数字全部处理掉，使 b 增加 cnt[a]，然后清空 cnt[a]。

如果此时还有剩余数字，就必须消耗一个值为 b 的数字，并令 a 增加 \(1\)。当 \(a=b\) 时，说明当前存在两种对称的选择，答案乘以 \(2\)。

#include #define rint register int
#define int long long
#define endl '\n'using namespace std;const int mod = 998244353;
const int N = 1e5 + 5;int n, cnt[N];
int a, b;signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (rint i = 1; i <= n; ++i) {int x;cin >> x;cnt[x]++;}int t = n, ans = 1;while (t) {if (a == b) ans = ans * 2 % mod;b += cnt[a], t -= cnt[a];cnt[a] = 0;if (!t) break;cnt[b]--;a++, t--;}cout << ans << endl;return 0;
}

G.Longest Common Prefix

给定 \(n\) 个字符串，按顺序加入。

对于加入第 \(i\) 个字符串后，考虑从前 \(i\) 个字符串中任选 \(j\) 个字符串，求这些字符串的最长公共前缀长度的最大值，记为 \(f_{i,j}\)。

对于每个 \(i\)，输出：

\[\sum_{j=1}^{i}(f_{i,j}\oplus j) \]

其中 \(\oplus\) 表示按位异或。

考虑把所有字符串插入 Trie。对于 Trie 上的每个节点，维护有多少个字符串经过这个节点，记为 c[p]。一个节点代表一个前缀，假设它的深度为 \(d\)，并且有 \(k\) 个字符串经过它，那么就说明这 \(k\) 个字符串拥有长度为 \(d\) 的公共前缀。

因此，对于每个 \(i\)，我们只需要维护：

\[f[i]=\max\{dep_p\mid c[p]\ge i\} \]

也就是至少有 \(i\) 个字符串经过的节点中，最大的深度。这样，\(f[i]\) 就是任选 \(i\) 个字符串时，能够得到的最大公共前缀长度。

接下来考虑如何维护答案。

假设现在已经加入了 \(i-1\) 个字符串，准备加入第 \(i\) 个字符串。

答案需要增加一项 \(f[i]\oplus i\)。由于此时还没有任何节点被 \(i\) 个字符串同时经过，所以先将 \(f[i]\) 看作 \(0\)，于是答案增加 \(0\oplus i=i\). 然后将新字符串插入 Trie，沿着它经过的每一个节点进行更新。

假设当前经过节点 \(p\)，原本有 \(c[p]-1\) 个字符串经过它，现在又加入了一个字符串，于是 \(c[p]\gets c[p]+1\) 那么这个节点就可能更新 \(f[c[p]]\)。

当前节点深度为 \(i+1\)（代码中下标从 \(0\) 开始），所以如果 \(f[c[p]] 就需要更新它。

由于答案维护的是：

\(res=\sum_{j=1}^{i}(f[j]\oplus j)\)

因此更新时先减去旧贡献，再加上新贡献：

res -= f[c[p]] ^ c[p];
f[c[p]] = i + 1;
res += f[c[p]] ^ c[p];

每插入一个字符串，只需要沿着它在 Trie 上的路径更新即可。

#include #define rint register int
#define int long long
#define endl '\n'using namespace std;const int N = 5e5 + 5;
const int M = 3e6 + 5;int n;
int ch[M][26], tot, c[M];
int f[N], res;
int cnt[N];
int len;void insert(string s)
{int p = 0;for (rint i = 0; i < len; i++){int t = s[i] - 'a';if (!ch[p][t]) ch[p][t] = ++tot;p = ch[p][t];c[p]++;if (f[c[p]] <= i){res -= f[c[p]] ^ c[p];f[c[p]] = i + 1;res += f[c[p]] ^ c[p];}}cnt[p]++;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (rint i = 1; i <= n; i++){string s;cin >> s;len = s.size();res += i;insert(s);cout << res << endl;}return 0;
}

A.Permutation Inversions

666 大家全会做我考场上没做出来，压根就没往建图上想。

给定一个长度为 \(n\) 的排列 \(p\)，其中包含 \(1\sim n\) 的所有整数。

接下来给出 \(m\) 条限制，每条限制包含两个整数 \(l,r\)，以及一个长度为 \(r-l+1\) 的序列 \(a_l,a_{l+1},\ldots,a_r\)。

对于每条限制，要求排列中对应位置的数值满足：

\[p_{a_l}

也就是说，给出的序列规定了排列中若干位置上的数值大小关系。

现在要求构造一个满足所有限制的排列，使得其逆序对数量最少。如果不存在合法排列，输出 \(-1\)。

考虑一个区间 \([l,r]\)，题目要求其中的元素按照给定顺序排列，那么只需要保证 \(a_l 这里的大小关系指的是它们在最终排列中的位置先后，而不是元素本身的数值。于是，对于每一对相邻元素，建立一条有向边：\(a_i\rightarrow a_{i+1}\) 表示 \(a_i\) 必须排在 \(a_{i+1}\) 前面。

这样，所有限制就转化成了一张有向图。问题也就变成了：求这张图的一个拓扑序。这里使用优先队列维护当前所有入度为 \(0\) 的点，每次取出编号最小的点进行拓扑排序。这样得到的就是字典序最小的拓扑序。

记录：\(ans[x]=x\text{ 在拓扑序中的位置}\) 每次取出一个点 \(x\)，令 ans[x]=++tot

如果最后 \(tot=n\)，说明所有点都成功加入拓扑序，图中不存在环，构造成功；否则说明存在环，所有限制无法同时满足，输出 \(-1\)。

#include #define rint register int
//#define int long long
#define endl '\n'using namespace std;const int N = 1e6 + 5;
const int M = 2e6 + 5;int n, m, tot;
int a[N], in[N], ans[N];
int idx, h[N], e[M], ne[M];void add(int a, int b)
{e[++idx] = b, ne[idx] = h[a], h[a] = idx, in[b]++;
}void toposort()
{priority_queue, greater> q;for (rint i = 1; i <= n; i++)if (!in[i])q.push((int)i);while (!q.empty()){int x = q.top();q.pop();ans[x] = ++tot;for (rint i = h[x]; i; i = ne[i]){int y = e[i];if (--in[y] == 0)q.push(y);}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--){idx = tot = 0;cin >> n >> m;memset(h, 0, sizeof h);memset(in, 0, sizeof in);while (m--){int l, r;cin >> l >> r;for (rint i = l; i <= r; i++){cin >> a[i];if (i > l) add(a[i - 1], a[i]);}}toposort();if (tot == n){for (rint i = 1; i <= n; i++){cout << ans[i];if (i < n) cout << " ";else cout << endl;}}else cout << -1 << endl;}return 0;
}

E. String

给定一个长度为 \(n\) 的字符串 \(S\)，下标从 \(1\) 开始，字符串中只包含字符 N 和 H。

接下来需要按顺序执行 \(T\) 次操作，每次操作由三个整数 \(op,p,k\) 描述，表示从位置 \(p\) 开始，重复执行以下过程恰好 \(k\) 次。每次重复都使用当前字符串，即前面所有操作和重复过程修改后的字符串。

每次重复时，根据 \(op\) 决定移动方向和停止字符：

  • \(op=1\)：向右移动，停止字符为 N。
  • \(op=2\)：向右移动，停止字符为 H。
  • \(op=3\)：向左移动，停止字符为 N。
  • \(op=4\)：向左移动，停止字符为 H。

每次从位置 \(p\) 开始，在每个经过的位置，先将当前字符翻转：N 变成 H，H 变成 N。

如果翻转前该位置的字符就是停止字符，那么本次重复立即结束；否则继续向指定方向移动一格。

如果移动到字符串边界，已经没有下一个位置，则翻转边界位置后结束本次重复。

请你求出执行完所有操作后的字符串。

这题的难点在于 \(k\) 最大可以达到 \(10^{18}\)，显然不能直接模拟 \(k\) 次过程。考虑如何优化重复操作。

首先观察一次操作。假设向右移动，停止字符为 N，那么从 \(p\) 开始：

  • 遇到 H，将其翻转为 N，继续向右。
  • 遇到第一个 N，将其翻转为 H，然后停止。
  • 如果一直没有遇到 N，就将后面的字符全部翻转。

所以，我们实际上只需要找到右侧第一个 N，将它前面的区间全部变成 N，再把这个 N 变成 H。向左移动同理，只不过需要找到左侧第一个停止字符。接下来考虑如何处理 \(k\) 次重复。

接下来就是这个题的关键。

然后我们直接注意到连续执行 \(2^i\) 次操作，等价于从位置 \(p+i\)（向右）或 \(p-i\)（向左）开始，执行一次上述过程。

因此可以对 \(k\) 进行二进制拆分：

\[k=\sum_{i=0}^{\lfloor\log_2 k\rfloor}b_i2^i \]

其中 \(b_i\) 表示 \(k\) 的第 \(i\) 位二进制位。

按照从低位到高位的顺序枚举二进制位：

  • 如果当前位为 \(0\)，跳过。
  • 如果当前位为 \(1\)，就从 \(p+i\) 或 \(p-i\) 开始执行一次过程。

这样就将原本需要执行 \(k\) 次的操作，优化成了最多 \(60\) 次单次处理。

剩下的问题就是如何快速找到指定位置之后（或之前）第一个停止字符，以及如何修改一段连续区间。

这里使用线段树维护即可。

对于每次处理，设目标停止字符为 \(v\)，其中 N 对应 \(0\)，H 对应 \(1\)。

如果向右处理，就在 \([st,n]\) 中寻找最靠左的 \(v\)；如果向左处理，就在 \([1,st]\) 中寻找最靠右的 \(v\)。

假设找到的位置为 \(x\)：

  • 如果没有找到，就将整个待处理区间赋值为 \(v\)。
  • 如果找到了，就将 \(x\) 与 \(st\) 之间（不包含 \(x\)）的区间赋值为 \(v\)，再将位置 \(x\) 赋值为 \(v\oplus 1\)。

这样就完成了一次处理。

复杂度 \(O(n+T\log k\log n)\)

#include #define rint register int
#define int long long
#define endl '\n'using namespace std;const int N = 1e5 + 5;int n, t;
string s;struct node
{int l, r;int cnt[2], lz;// cnt[0] : the number of N// cnt[1] : the number of H//lz = 0 change into N ; lz = 1 H; lz = -1 no tag
} tr[N << 2];struct SegmentTree
{void push_up(int p){tr[p].cnt[0] = tr[p << 1].cnt[0] + tr[p << 1 | 1].cnt[0];tr[p].cnt[1] = tr[p << 1].cnt[1] + tr[p << 1 | 1].cnt[1];}void push_down(int p){if (tr[p].lz == -1) return;int v = tr[p].lz;tr[p << 1].cnt[v] = tr[p << 1].cnt[0] + tr[p << 1].cnt[1];tr[p << 1].cnt[v ^ 1] = 0;tr[p << 1].lz = v;tr[p << 1 | 1].cnt[v] = tr[p << 1 | 1].cnt[0] + tr[p << 1 | 1].cnt[1];tr[p << 1 | 1].cnt[v ^ 1] = 0;tr[p << 1 | 1].lz = v;tr[p].lz = -1;}void build(int p, int l, int r){tr[p].l = l;tr[p].r = r;tr[p].lz = -1;if (l == r){int v = (s[l] == 'H');tr[p].cnt[v] = 1;tr[p].cnt[v ^ 1] = 0;return;}int mid = (l + r) >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);push_up(p);}void change(int p, int x, int y, int v){int l = tr[p].l, r = tr[p].r;if (x > y) return ;if (x <= l && r <= y){tr[p].cnt[v] = r - l + 1;tr[p].cnt[v ^ 1] = 0;tr[p].lz = v;return ;}push_down(p);int mid = (l + r) >> 1;if (x <= mid) change(p << 1, x, y, v);if (y > mid) change(p << 1 | 1, x, y, v);push_up(p);}int findr(int p, int x, int y, int v){int l = tr[p].l, r = tr[p].r;if (y < l || r < x || !tr[p].cnt[v]) return 0;if (l == r) return l;push_down(p);int t = findr(p << 1, x, y, v);if (t) return t;return findr(p << 1 | 1, x, y, v);}int findl(int p, int x, int y, int v){int l = tr[p].l, r = tr[p].r;if (y < l || r < x || !tr[p].cnt[v]) return 0;if (l == r) return l;push_down(p);int t = findl(p << 1 | 1, x, y, v);if (t) return t;return findl(p << 1, x, y, v);}void print(int p){int l = tr[p].l, r = tr[p].r;if (l == r){cout << (tr[p].cnt[1] ? 'H' : 'N');return ;}push_down(p);print(p << 1);print(p << 1 | 1);}
} seg;signed main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> t >> s;s = " " + s;seg.build(1, 1, n);while (t--){int op, p, k;cin >> op >> p >> k;int v = (op == 1 || op == 3) ? 0 : 1;int d = (op <= 2);for (rint i = 0; k; i++, k >>= 1){if (!(k & 1)) continue;int st = d ? p + i : p - i;if (st < 1 || st > n) break;int x;if (d) x = seg.findr(1, st, n, v);else x = seg.findl(1, 1, st, v);if (d){if (!x) seg.change(1, st, n, v);else{seg.change(1, st, x - 1, v);seg.change(1, x, x, v ^ 1);}}else{if (!x) seg.change(1, 1, st, v);else{seg.change(1, x + 1, st, v);seg.change(1, x, x, v ^ 1);}}}}seg.print(1);return 0;
}

F. Red Sequence

给定一个长度为 \(n\) 的序列。对于每个位置 \(i\)，有 \(1\sim 3\) 个棋子，每个棋子有三种颜色：红色、黄色和蓝色。保证同一个位置不会出现两个颜色相同的棋子。

现在需要将整个序列划分成若干个连续区间。如果一个区间中红色棋子的数量不少于黄色棋子的数量，并且不少于蓝色棋子的数量，那么称这个区间为一个红色区间。

也就是说，对于一个区间，需要满足：

\[R\ge Y,\qquad R\ge B \]

其中 \(R,Y,B\) 分别表示区间内红色、黄色和蓝色棋子的数量。

你需要最大化所有红色区间的长度之和，并输出这个最大值。

首先考虑如何判断一个区间是否合法。设每个位置的红、黄、蓝棋子数量分别为 \(r_i,y_i,b_i\)，定义两个前缀和：

\[a_i=\sum_{j=1}^{i}(r_j-y_j) \]

\[b_i=\sum_{j=1}^{i}(r_j-b_j) \]

那么对于区间 \([l,r]\)，它是红色区间当且仅当：

\[a_r-a_{l-1}\ge 0 \]

\[b_r-b_{l-1}\ge 0 \]

也就是：

\[a_{l-1}\le a_r,\qquad b_{l-1}\le b_r \]

这样，区间是否合法就转化成了两个前缀和之间的大小关系。

接下来考虑 DP。

设 \(f[i]\) 表示前 \(i\) 个位置中，所有红色区间的长度之和最大是多少。

对于位置 \(i\)，有两种选择：

  1. 不让位置 \(i\) 属于红色区间，那么答案就是 \(f[i-1]\)。
  2. 让某个红色区间 \([j+1,i]\) 以位置 \(i\) 结尾。

对于第二种情况，由前面的推导可知，必须满足：

\[a_j\le a_i,\qquad b_j\le b_i \]

如果选择这个区间，那么它的长度为 \(i-j\)，因此可以得到：

\[f[j]+i-j=i+(f[j]-j) \]

于是转移方程为：

\[f[i]=\max\left(f[i-1], i+\max_{\substack{0\le j

现在问题变成了：对于每个位置 \(i\)，如何快速查询所有满足 \(a_j\le a_i\) 且 \(b_j\le b_i\) 的历史状态中，\(f[j]-j\) 的最大值。

这实际上是一个二维前缀最大值查询。考虑使用二维树状数组维护。

因为两个前缀和的取值范围都在 \([-n,n]\) 内，所以先将坐标整体加上 \(n+1\)，把它们映射到正整数范围。但是直接开二维数组会导致空间复杂度过高，因此采用离线离散化的二维树状数组。

先把所有前缀点 \((a_i,b_i)\) 收集起来，预处理每个外层树状数组节点可能出现的第二维坐标，并进行排序、去重。这样就可以在较小的空间内完成二维前缀最大值查询和单点取最大值更新。

具体处理时：

  • tree.ask(x,y)：查询所有横纵坐标均不超过 \((x,y)\) 的点所维护的最大值。
  • tree.add(x,y,v)：在坐标 \((x,y)\) 处，将维护值更新为与 \(v\) 的较大值。

初始化时，将前缀点 \((a_0,b_0)=(0,0)\) 插入，权值为 \(f[0]-0=0\)。

之后从 \(1\) 到 \(n\) 枚举位置 \(i\)，先查询满足条件的最大值，再计算：

\[f[i]=\max(f[i-1],i+tree.ask(a_i+n+1,b_i+n+1)) \]

最后将当前状态插入二维树状数组：

\[tree.add(a_i+n+1,b_i+n+1,f[i]-i) \]

注意，必须先查询再插入当前点，这样才能保证转移中满足 \(j。

最终答案就是 \(f[n]\)

复杂度 \(O(n\log^2 n)\)

代码

#include #define rint register int
#define int long long
#define endl '\n'using namespace std;const int N = 1e6 + 5;
const int M = N << 1;
const int inf = 1e18;int n;
int a[N], b[N], f[N];struct BIT
{vector c[M], tr[M];int m;int lowbit(int x){return x & -x;}void build(){m = (n << 1) + 1;for (rint i = 0; i <= n; i++){int x = a[i] + n + 1;int y = b[i] + n + 1;for (rint j = x; j <= m; j += lowbit(j)) c[j].push_back(y);}for (rint i = 1; i <= m; i++){sort(c[i].begin(), c[i].end());c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());tr[i].assign(c[i].size() + 1, -inf);}}void add(int x, int y, int v){for (rint i = x; i <= m; i += lowbit(i)){int p = lower_bound(c[i].begin(), c[i].end(), y) - c[i].begin() + 1;for (rint j = p; j < tr[i].size(); j += lowbit(j))tr[i][j] = max(tr[i][j], v);}}int ask(int x, int y){int res = -inf;for (rint i = x; i; i -= lowbit(i)){int p = upper_bound(c[i].begin(), c[i].end(), y) - c[i].begin();for (rint j = p; j; j -= lowbit(j))res = max(res, tr[i][j]);}return res;}
} tree;signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (rint i = 1; i <= n; i++){int r, y, bl;cin >> r >> y >> bl;a[i] = a[i - 1] + r - y;b[i] = b[i - 1] + r - bl;}tree.build();tree.add(a[0] + n + 1, b[0] + n + 1, 0);for (rint i = 1; i <= n; i++){int x = a[i] + n + 1, y = b[i] + n + 1;f[i] = max(f[i - 1], i + tree.ask(x, y));tree.add(x, y, f[i] - i);}cout << f[n] << endl;return 0;
}