本文参考博客 [蓝桥杯 2021 国 AB] 翻转括号序列(线段树上二分)
一、问题简析
线段树 + 二分
初步分析
令 ( 的值为 1，) 的值为 -1，则对于序列 \(a_La_{L+1}a_{L+2}...a_R\)，其为合法序列的条件为
用前缀和 presum 来表示，则为
因此，我们需要维护区间前缀和的最小值。
建立线段树
节点信息
struct node
{
int l, r;
int mmax, mmin; // [l, r]中前缀和的最大值为mmax，最小值为mmin
int tag_rev, tag_add; // tag_rev -- 是否需要翻转; tag_add -- 待增加的值
} tree[N << 2];
操作一
操作一要翻转 \([L,R]\) 中的括号，我们可以将该操作分成两部分：
\[reverse(L,R)=reverse(1,L-1)+reverse(1,R) \]为什么要这样做呢？我们来看翻转序列 \([1,R]\)。翻转后，会对整个数列的前缀和产生影响，进而影响维护的 mmin 和 mmax 产生影响。
- 对于 \([1,R]\)，相当于 \(\text{presum[1,2, ...,R]}\) 取相反数。因此
mmin和mmax交换，并取相反数即可。 - 对于 \([R+1,n]\)，因为只取反了 \([1,R]\)，所以在 \(-\text{presum[R]}\) 的基础上加上原来的数，相当于在原来的前缀和上减去两倍的 \(\text{presum[R]}\)。因此，
mmin和mmax也要减去两倍的 \(\text{presum[R]}\)。
所以，要翻转序列 \([1,R]\)，要先后进行两种更新：
- 更新一，区间 \([1,R]\) 的前缀和取反，即
mmin和mmax交换，并取相反数。 - 更新二，区间 \([R+1,n]\) 的前缀和减去两倍的 \(\text{presum[R]}\)，即
mmin和mmax减去两倍的 \(\text{presum[R]}\)。
因此，我们需要两个懒惰标记。值得注意的是，tag_rev 会对 tag_add 产生影响——令 tag_add 取相反数，反过来则不会有影响。在进行 pushdown 时，要先更新 tag_rev，再是 tag_add。（作者尚未明白原因）
操作二
操作二要用二分来实现。我们先来看二分的前提条件——单调性。区间 \([L,R]\) 前缀和的最小值 mmin 随 \(R\) 单调不增。因此，我们可以利用二分找到最大的 \(R\)，满足区间 \([L,R]\) 前缀和的最小值 mmin 大于等于 \(\text{presum[L - 1]}\)。再判断此时的 \(R\) 是否满足 \(\text{presum[R]}=\text{presum[L - 1]}\)。
因此，query 的作用是查找区间 \([L,R]\) 前缀和的最小值 mmin。
需要注意，二分的条件是：
- 若 \([L,M]\) 的
mmin小于 \(\text{presum[L - 1]}\)，令 \(R=M-1\)。 - 若 \([L,M]\) 的
mmin大于等于 \(\text{presum[L - 1]}\) 且 \([M,R]\) 的mmin大于 \(\text{presum[L - 1]}\)，也要令 \(R=M-1\)。 - 否则，令 \(L=M+1\)。
二、Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickin(void)
{
ll ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
#define lc(p) p << 1
#define rc(p) p << 1 | 1
const int N = 1e6 + 5;
int n, m;
int presum[N];
char s[N];
struct node
{
int l, r;
int mmax, mmin; // [l, r]中前缀和的最大值为mmax，最小值为mmin
int tag_rev, tag_add; // tag_rev -- 是否需要翻转; tag_add -- 待增加的值
} tree[N << 2];
void amend_rev(node &p)
{
int tmp1 = p.mmax, tmp2 = p.mmin;
p.mmax = -tmp2;
p.mmin = -tmp1;
p.tag_rev ^= 1;
p.tag_add *= -1;
}
void amend_add(node &p, int val)
{
p.mmax += val;
p.mmin += val;
p.tag_add += val;
}
void pushup(int p)
{
tree[p].mmax = max(tree[lc(p)].mmax, tree[rc(p)].mmax);
tree[p].mmin = min(tree[lc(p)].mmin, tree[rc(p)].mmin);
}
void pushdown(int p)
{
if (tree[p].tag_rev)
{
amend_rev(tree[lc(p)]);
amend_rev(tree[rc(p)]);
tree[p].tag_rev = 0;
}
if (tree[p].tag_add)
{
amend_add(tree[lc(p)], tree[p].tag_add);
amend_add(tree[rc(p)], tree[p].tag_add);
tree[p].tag_add = 0;
}
}
void build(int p, int l, int r)
{
tree[p] = {l, r, presum[l], presum[l], 0, 0};
if (l == r) return;
int m = (l + r) >> 1;
build(lc(p), l, m);
build(rc(p), m + 1, r);
pushup(p);
}
void update_rev(int p, int x, int y)
{
if (x > y) return;
if (x <= tree[p].l && tree[p].r <= y)
{
amend_rev(tree[p]);
return;
}
pushdown(p);
int m = (tree[p].l + tree[p].r) >> 1;
if (x <= m) update_rev(lc(p), x, y);
if (y > m) update_rev(rc(p), x, y);
pushup(p);
}
void update_add(int p, int x, int y, int val)
{
if (x > y) return;
if (x <= tree[p].l && tree[p].r <= y)
{
amend_add(tree[p], val);
return;
}
pushdown(p);
int m = (tree[p].l + tree[p].r) >> 1;
if (x <= m) update_add(lc(p), x, y, val);
if (y > m) update_add(rc(p), x, y, val);
pushup(p);
}
int query(int p, int x, int y)
{
if (x == 0 && y == 0) return 0;
if (x <= tree[p].l && tree[p].r <= y)
return tree[p].mmin;
pushdown(p);
int m = (tree[p].l + tree[p].r) >> 1;
int ans = 1e8;
if (x <= m) ans = min(ans, query(lc(p), x, y));
if (y > m) ans = min(ans, query(rc(p), x, y));
return ans;
}
void update(int x, int y)
{
int val = query(1, x - 1, x - 1);
update_rev(1, 1, x - 1);
update_add(1, x, n, -2 * val);
val = query(1, y, y);
update_rev(1, x, y);
update_add(1, y + 1, n, -2 * val);
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
n = quickin(), m = quickin();
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i)
{
presum[i] = s[i] == '(' ? 1 : -1;
presum[i] += presum[i - 1];
}
build(1, 1, n);
for (int i = 0; i < m; ++i)
{
int a, b, c;
a = quickin();
if (a == 1)
{
b = quickin(), c = quickin();
update(b, c);
}
else if (a == 2)
{
b = quickin();
int key = query(1, b - 1, b - 1);
int l = b, r = n;
while (l <= r)
{
int m = (l + r) >> 1;
int mmin = query(1, l, m);
if (mmin < key || mmin >= key && query(1, m, n) > key)
r = m - 1;
else
l = m + 1;
}
if (r >= b && query(1, r, r) == key) printf("%d\n", r);
else printf("0\n");
}
}
return 0;
}
完
标签：P8765,AB,int,text,update,mmin,蓝桥,add,presum From： https://www.cnblogs.com/hoyd/p/18211661