题解：P11421 [清华集训 2024] 最大匹配 2
Bb1t
·
·
题解
题意
有 n 个括号，第 i 个括号颜色是 a_i，类型是 b_i（b_i=0 表示是左括号，b_i=1 表示是右括号）。你首先要尽可能多的匹配同色括号，再匹配尽可能多的异色括号。有 m 次询问，每次询问之前都还会有修改一个位置的括号颜色和类型，问在上述规则下匹配的括号数量。
### 解法
首先我们会先想没有颜色一般括号匹配会怎么做。如果用栈去匹配不便于后续的修改。但如果我们将左括号看作 $1$，右括号看作 $-1$，那么失配的右括号就是 $<0$ 的前缀最小值的位置，并且这个看起来相对好维护一些。
这样的话，我们正反都做一遍就可以求出总的失配括号数量，匹配的也就自然好求了。
把颜色加上，为了让最后没有颜色的括号匹配尽量多，我们在匹配同一种颜色的括号时会让失配的右括号尽量向右，（注意左括号我们在反着做的时候考虑）。这样所有颜色都做了一遍之后我们对最后的失配的括号再求一次匹配数量就可以了。
把修改加上，可以发现失配的位置变化是 $O(1)$ 的，现在我们要用数据结构快速维护这个过程，我们可以用 $n+1$ 个动态开点线段树来分别维护 $n$ 种颜色和失配的括号匹配情况，需要支持插入删除括号的操作。具体地，我们将我们将左括号看作 $1$，右括号看作 $-1$ 后，维护每个位置的值。线段树需要支持区间加，查询区间最小值和在线段树上二分从某个位置开始第一个大于等于某个数的位置，修改时如果某个括号失配或者重新匹配，就在第 $n+1$ 个线段树上修改。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 2e5 + 5, M = N * 100, inf = 1e9;
int n, m, a[N], b[N];
struct seg {
int a[N], b[N], rt[N], ls[M], rs[M], mn[M], tag[M], tot, res, sum;
void init()
{
for (int i = 1; i <= n; ++i) a[i] = ::a[i], b[i] = ::b[i];
}
void push_up(int k)
{
mn[k] = min(mn[ls[k]], mn[rs[k]]);
}
void push(int k, int v)
{
mn[k] += v, tag[k] += v;
}
void push_down(int k)
{
if (tag[k]) {
if (!ls[k]) ls[k] = ++tot;
if (!rs[k]) rs[k] = ++tot;
push(ls[k], tag[k]);
push(rs[k], tag[k]);
tag[k] = 0;
}
}
void add(int L, int R, int v, int &k, int l = 1, int r = n)
{
if (!k) k = ++tot;
if (L <= l && r <= R) {
push(k, v);
return;
}
push_down(k);
int mid = l + r >> 1;
if (L <= mid) add(L, R, v, ls[k], l, mid);
if (R > mid) add(L, R, v, rs[k], mid + 1, r);
push_up(k);
}
int query(int L, int R, int k, int l = 1, int r = n)
{
if (!k) return 0;
if (L <= l && r <= R) return mn[k];
push_down(k);
int mid = l + r >> 1, ans = inf;
if (L <= mid) ans = min(ans, query(L, R, ls[k], l, mid));
if (R > mid) ans = min(ans, query(L, R, rs[k], mid + 1, r));
return ans;
} pii find(int p, int v, int k, int l = 1, int r = n)
{
if (!k || mn[k] >= v) return pii(-1, -1);
if (l == r) return pii(l, mn[k]);
push_down(k);
int mid = l + r >> 1;
if (mid >= p) {
auto [pos, val] = find(p, v, ls[k], l, mid);
if (pos != -1) return pii(pos, val);
}
return find(p, v, rs[k], mid + 1, r);
}
int ins_(int x, int v, int c)
{
add(x, n, v, rt[c]);
int pre = min(0, x > 1 ? query(1, x - 1, rt[c]) : 0);
auto [pos, val] = find(x, pre, rt[c]);
if (pos != -1 && val == pre - 1) {
++res;
return pos;
}
return 0;
}
int del_(int x, int v, int c)
{
int pre = min(0, x > 1 ? query(1, x - 1, rt[c]) : 0);
auto [pos, val] = find(x, pre, rt[c]);
add(x, n, -v, rt[c]);
if (pos != -1 && val == pre - 1) {
--res;
return pos;
}
return 0;
}
int ins(int x, int v, int c)
{
if (v == -1) {
++sum;
return -ins_(x, -1, c);
}
else return del_(x, -1, c);
}
int del(int x, int v, int c)
{
if (v == -1) {
--sum;
return del_(x, -1, c);
}
else return -ins_(x, -1, c);
}
}z, f, al;
bool en;
int main()
{
#ifdef IAKIOI
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n----------------------------" << endl;
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) {
cin >> b[i];
if (!b[i]) b[i] = 1;
else b[i] = -1;
}
z.init();
reverse(a + 1, a + 1 + n), reverse(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++i) b[i] = -b[i];
f.init();
reverse(a + 1, a + 1 + n), reverse(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++i) b[i] = -b[i];
for (int i = 1; i <= n; ++i) {
int pos = z.ins(i, z.b[i], z.a[i]);
if (pos > 0) {
al.del(pos, z.b[pos], 0);
} else if (pos < 0) {
al.ins(-pos, z.b[-pos], 0);
}
pos = f.ins(i, f.b[i], f.a[i]);
if (pos > 0) {
al.del(n - pos + 1, -f.b[pos], 0);
} else if (pos < 0) {
al.ins(n - (-pos) + 1, -f.b[-pos], 0);
}
}
assert(z.sum - z.res == f.sum - f.res);
cout << z.sum - z.res + al.sum - al.res << '\n';
while (m--) {
int x, p, q;
cin >> x >> p >> q;
if (!q) q = 1;
else q = -1;
int pos = z.del(x, z.b[x], z.a[x]);
if (pos > 0) {
al.del(pos, z.b[pos], 0);
} else if (pos < 0) {
al.ins(-pos, z.b[-pos], 0);
}
pos = f.del(n - x + 1, f.b[n - x + 1], f.a[n - x + 1]);
if (pos > 0) {
al.del(n - pos + 1, -f.b[pos], 0);
} else if (pos < 0) {
al.ins(n - (-pos) + 1, -f.b[-pos], 0);
}
z.a[x] = p, f.a[n - x + 1] = p;
z.b[x] = q, f.b[n - x + 1] = -q;
pos = z.ins(x, z.b[x], z.a[x]);
if (pos > 0) {;
al.del(pos, z.b[pos], 0);
} else if (pos < 0) {
al.ins(-pos, z.b[-pos], 0);
}
pos = f.ins(n - x + 1, f.b[n - x + 1], f.a[n - x + 1]);
if (pos > 0) {
al.del(n - pos + 1, -f.b[pos], 0);
} else if (pos < 0) {
al.ins(n - (-pos) + 1, -f.b[-pos], 0);
}
assert(z.sum - z.res == f.sum - f.res);
cout << z.sum - z.res + al.sum - al.res << '\n';
}
return 0;
}
```