暑训#3补题

C

题目大意：
给定一个由小写字母构成的字符串和若干次修改操作。在每次修改后，求其符合以下要求的最大子串长度：出现奇数次的字母有奇数个，出现非零偶数次的字母有偶数个。

难度： ~2000
知识点： 线段树，分类讨论

观察可以得到，要求等价于：串长和字符集大小都为奇数。这一点可以通过枚举串长和字符集大小各自的奇偶性来验证。

然后进行分类讨论。

• 当字符集大小为奇数时：

  • 如果串长为奇数：直接取原串即可。

  • 如果串长为偶数：

    • 如果首或尾字母出现了超过一次，那么删去它不改变字符集大小，但让串长变为奇数，符合了要求。

    • 如果首尾字母都只出现了一次，我们正序和倒序分别找到第一个出现多次的字母。为了方便下文叙述，我们不妨设原串形如 [abcd X ... Y uvw]，其中小/大写字母分别代表出现一/多次的字母。

      那么如果我们只删去头尾的若干字母，字符集大小和串长的奇偶性一定同时改变，不可能同时变为奇数。因此，我们至少需要删到串中的 X 或 Y 。

      • 如果删去的串长为奇数（如 [abcdX]），则剩下的串长和字符集大小都为奇数，符合了要求。
      • 如果删去的串长为偶数（如 [Yuvw]），则剩下的串长和字符集大小都为偶数，我们再删去另一端的一个字母即可符合要求。

      分别求解删除两端的情形后，对答案取较大值即可。

• 当字符集大小为偶数时：

  我们可以这样做：对于每种字符，求不含它的极大子串。可以证明，所有极长子串中最长的一个的字符集大小一定就是原串字符集大小减一，是一个奇数。

  证明很显然。记原串形如 ...A[...]A.. ，[...] 是最大极长子串，不包含的字母是 A。

  使用反证法，假设该子串字符集大小不为原串字符集大小减一，说明一定存在某不为 A 的字母不在该子串中，记为 B。无论原串的形式为 ..B...A[...]A.. 还是 ..B..A[...]A..B.. ，不含 B 的极大子串一定比不含 A 的极大子串更长，这与 [...] 是最大极长子串相矛盾。因此假设不成立，证明完成。

  由于至少需要删去一种字符，最终的答案一定不长于最大极长子串，此处设该最大极长子串长度为 \(L\)。

  • 如果最大极长子串串长为奇数，直接取，答案就是 \(L\)。

  • 如果最大极长子串串长为偶数，与第一类讨论类似地：

    • 如果子串首或尾字母在串内出现了超过一次，那么删去它不改变字符集大小，但让串长变为奇数，符合了要求。答案是 \(L - 1\)。

    • 如果首尾字母都只出现了一次，记原串形如 ...A [abc X ... Y uvw] A...，其中小/大写字母分别代表在子串内出现一/多次的字母，[] 内为最大极长子串。

      观察后可知，A 右侧为 a 或右边界。否则 a 分割成的子串将长于最大极长子串。该性质可以向左右推广，也就是说原串一定是 ...uvw A [abc X ... Y uvw] A abc... 的子串。

      我们考虑 ...A(abc X ... Y uvw A)... 括号内的串，初始字符集大小为偶数，串长为奇数。

      试着往右侧移动括号范围。括号内最左侧仍为单次出现的字母时，括号内子串奇偶性质保持不变。

      当最左侧为多次出现字母时（如 ...A abc (X ... Y uvw A abc)... 所示）我们直接删去最左侧的 X 和最右侧的 c，剩下的串长和字符集大小都为奇数。这个奇数是不大于最大极长子串长度的最大奇数，是最优值。向左侧移动同理。只要有一侧能移到，答案就是 \(L - 1\)。这个过程中移动不超过 \(26\) 次。

      移不到的情况形如 vw A ab(c X ... Y uvw A ab)，子串两侧的部分长度很短。

      由于初始时 () 内字符集大小为偶数，串长为奇数。而删单次出现字符会使字符集大小和串长的奇偶性同时改变，不能使两者同时变为奇数。必须删多次出现的字母。

      以上串为例，再删去括号内的 cX 后，剩下部分的字符集大小和串长的奇偶性就相同了。如果是偶数就再删去另一侧的一个单次出现字母即可。求解只需要找到 X 和 Y 的位置，根据其到另一侧的距离计算即可。

  可以看见，解决问题的关键就是维护当前最大极长子串。

  我们开 \(26\) 个线段树，维护各字母对应的极长子串。将当前字母视为 \(1\)，其他字母视为 \(0\)，则问题转化为求最长的连续零段。

  线段树内每个节点维护以下信息：【1】区间内最长连续零段的长度；【2】区间内最长连续零段的起始位置【3】从区间最左端起的连续零段的长度；【4】在区间最右端止的连续零段的长度。【5】区间和。

  其中维护【5】是为了快速得到某区间内某字母是否多次出现。

Code：

#include <bits/stdc++.h>
using namespace std;#define pii pair<int, int>
#define FOR(i, a, b) for (int i = a; i <= b; i++)const int N = 2e5 + 10;int n, q, cnt;
int Ans;
string ss, s;map<char, int> mp;struct seg_tree {char id;struct node {int mx, lmx, rmx, pos, val;} t[N << 2];void pushup(int u, int l, int r) {t[u].val = t[u << 1].val + t[u << 1 | 1].val;int mmx = t[u << 1].rmx + t[u << 1 | 1].lmx;t[u].mx = max(max(t[u << 1].mx, t[u << 1 | 1].mx), mmx);t[u].lmx = t[u << 1].lmx;int mid = (l + r) / 2;if (t[u << 1].lmx == mid - l + 1) t[u].lmx += t[u << 1 | 1].lmx;t[u].rmx = t[u << 1 | 1].rmx;if (t[u << 1 | 1].rmx == r - mid) t[u].rmx += t[u << 1].rmx;if (t[u].mx == mmx) t[u].pos = mid - t[u << 1].rmx + 1;else if (t[u].mx == t[u << 1].mx) t[u].pos = t[u << 1].pos;else t[u].pos = t[u << 1 | 1].pos;}void build(int u, int l, int r) {if (l == r) {if (id == s[l]) {t[u].val = 1;t[u].mx = t[u].lmx = t[u].rmx = 0;t[u].pos = 0;} else {t[u].val = 0;t[u].mx = t[u].lmx = t[u].rmx = 1;t[u].pos = l;}return;}int mid = (l + r) / 2;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u, l, r);}void modify(int u, int l, int r, int x, int op) {if (l == r && l == x) {if (op) {t[u].val = 0;t[u].mx = t[u].lmx = t[u].rmx = 1;t[u].pos = l;} else {t[u].val = 1;t[u].mx = t[u].lmx = t[u].rmx = 0;t[u].pos = 0;}return;}int mid = (l + r) / 2;if (x <= mid) modify(u << 1, l, mid, x, op);else modify(u << 1 | 1, mid + 1, r, x, op);pushup(u, l, r);}int query(int u, int l, int r, int L, int R) {if (L <= l && r <= R) return t[u].val;int ret = 0, mid = (l + r) / 2;if (L <= mid) ret += query(u << 1, l, mid, L, R);if (R > mid) ret += query(u << 1 | 1, mid + 1, r, L, R);return ret;}} tree[26];pii fnd() {int mxl = 0, mxr = -1;FOR(i, 0, 25) {int mxi = tree[i].t[1].mx, p = tree[i].t[1].pos;if (p == 1 && p + mxi - 1 == n) continue;if (mxi > mxr - mxl + 1) {mxl = p; mxr = p + mxi - 1;}}return make_pair(mxl, mxr);
}int solve() {if (cnt & 1) {if (n & 1) {return n;} else {if (mp[s[1]] > 1 || mp[s[n]] > 1) {return n - 1;} else {int ix = 0, iy = 0, ans1, ans2;while (ix + 1 <= n && mp[s[ix + 1]] == 1) ix++;while (n - iy >= 1 && mp[s[n - iy]] == 1) iy++;if (ix & 1) ans1 = n - ix - 2;else ans1 = n - ix - 1; if (iy & 1) ans2 = n - iy - 2;else ans2 = n - iy - 1;return max(ans1, ans2);}}} else {pii tt = fnd();int len = tt.second - tt.first + 1;if (len & 1) return len;else {int l = tt.first, r = tt.second;if (tree[s[l] - 'a'].query(1, 1, n, l, r) > 1) return len - 1;if (tree[s[r] - 'a'].query(1, 1, n, l, r) > 1) return len - 1;int cntl = 0, cntr = 0;while (l + cntl <= r && tree[s[l + cntl] - 'a'].query(1, 1, n, l, r) == 1) cntl++;while (r - cntr >= l && tree[s[r - cntr] - 'a'].query(1, 1, n, l, r) == 1) cntr++;if (l - 2 >= cntr) return len - 1;if (n - r - 1 >= cntl) return len - 1;int ans1 = n - (cntl + l);if (ans1 % 2 == 0) ans1 -= 1;int ans2 = r - cntr - 1;if (ans2 % 2 == 0) ans2 -= 1;return max(ans1, ans2);} }
}int main() {cin >> n >> q >> ss;s = ' ' + ss;FOR(i, 0, 25) {tree[i].id = i + 'a';tree[i].build(1, 1, n);}FOR(i, 1, n) {if (mp[s[i]] == 0) cnt += 1;mp[s[i]] += 1;}Ans = solve();cout << Ans << '\n';while (q--) {int x; char c; cin >> x >> c;if (s[x] == c) { cout << Ans << '\n'; continue; }tree[c - 'a'].modify(1, 1, n, x, 0);tree[s[x] - 'a'].modify(1, 1, n, x, 1);mp[s[x]] -= 1;if (mp[s[x]] == 0) cnt -= 1;s[x] = c;mp[s[x]] += 1;if (mp[s[x]] == 1) cnt += 1;Ans = solve();cout << Ans << '\n';}
}