E.Nezzar and Binary String
生肉{:target=”_blank”}
题目翻译
$\text{Nezzar}$ 有个长度为 $n$ 的二进制串 $s$,现在他想对 $s$ 进行 $q$ 次操作,将二进制串 $s$ 变成二进制串 $f$。
第 $i$ 次操作由两个整数 $l _ i$ 和 $r _ i$ 描述,$\text{Nezzar}$ 将修改 $s$ 中的 $[l _ i, r _ i]$ 这一段。
每次修改分以下两种情况:
- 如果 $s[l _ i \sim r _ i]$ 中,同时包含
0
和1
,则 $\text{Nezzar}$ 会生气,将 $s$ 扔掉。 - 否则,改变 $s[l _ i \sim r _ i]$ 中,不超过一半的字符。即这些字符由
1
变成0
,由0
变成1
。注意一定要修改至少一个数
现在 $\text{Nezzar}$ 想知道,是否存在一种操作方式,可以避免他生气而将 $s$ 扔掉。
输入
第一行包含一个正整数 $t$,表示测试数据组数。
对于每组测试数据:
第一样包含两个整数 $n, q \ (1 \leq n \leq 2 \times 10 ^ 5, 0 \leq q \leq 2 \times 10 ^ 5)$。
第二行包含一个长度为 $n$ 的二进制串 $s$。
第三行包含一个长度为 $n$ 的二进制串 $f$。
接下来的 $q$ 行,每行有两个整数。第 $i$ 行的两个整数表示 $l _ i, r _ i \ (1 \leq l _ i \leq r _ i \leq n)$。
保证所有测试数据的 $n$ 之和不超过 $2 \times 10 ^ 5$,所有测试数据的 $q$ 之和不超过 $2 \times 10 ^ 5$。
输出
对于每组测试数据,如果 $\text{Nezzar}$ 能在不生气的情况下将 $s$ 变成 $f$,则输出 YES
,否则输出 NO
。
样例输入
4
5 2
00000
00111
1 5
1 3
2 1
00
01
1 2
10 6
1111111111
0110001110
1 10
5 9
7 10
1 7
3 5
6 10
5 2
10000
11000
2 5
1 3
样例输出
YES
NO
YES
NO
算法
(倒推,线段树) $O((n + q) \log n)$
假设我们有一种操作方案,可以将 $s$ 变成 $f$,且保证 $\text{Nezzar}$ 不生气。
设第 $i$ 次操作后,$s$ 变成了 $t _ i$,那么我们操作过程中的序列即为 $t _ 0, t _ 1, \cdots, t _ {q - 1}, t _ q$,且其中 $t _ 0 = s, t _ q = f$。
我们从 $t _ i$ 推出 $t _ {i + 1}$ 并不好推,因此我们可以反过来想,尝试从 $t _ {i + 1}$ 推出 $t _ i$。
因为我们只对 $t _ i [l _ i \sim r _ i]$ 进行操作,所以 $t _ i$ 和 $t _ {i + 1}$ 应只有 $[l _ i \sim r _ i]$ 这段不同。
并且我们这种操作方案不会让 $\text{Nezzar}$ 生气,所以 $t _ i[l _ i \sim r _ i]$ 这段应该全部相同。
那么我们如何确定 $t _ i [l _ i \sim r _ i]$ 应该都是 1
,还是都是 0
呢?
假设 $t _ i [l _ i \sim r _ i]$ 中都是 1
,那么因为我们修改的字符数量,不能超过区间长度的一半,所以修改之后得到的 $t _ {i + 1} [l _ i \sim r _ i]$ 中,1
的个数一定多于 0
的个数。
同理,如果 $t _ i [l _ i \sim r _ i]$ 中都是 0
,那么 $t _ {i + 1} [l _ i \sim r _ i]$ 中,0
的个数一定多于 1
的个数。
所以,我们可以通过查询 $t _ {i + 1} [l _ i \sim r _ i]$ 中的 1
的个数,来确定 $t _ i [l _ i \sim r _ i]$ 每个位置的字符。
并且我们知道 $t _ q = f$,所以我们就可以从 $t _ q$ 往前推,对于每个 $i$,由 $t _ {i + 1}$ 唯一确定 $t _ i$。
如果推的过程中,某个 $t _ {i + 1} [l _ i \sim r _ i]$ 中的 1
的个数多于 0
的个数,则将这段全部修改为 1
。
同理如果 $t _ {i + 1} [l _ i \sim r _ i]$ 中的 0
的个数多于 1
的个数,则将这段全部修改为 0
。
如果 $t _ {i + 1} [l _ i \sim r _ i]$ 中的 0
的个数和 1
的个数相同,则说明 $t _ i [l _ i \sim r _ i]$ 中,同时包含了 0
和 1
,则 $\text{Nezzar}$ 会生气,输出 NO
。
如果最后推得 $t _ 0 \neq s$,说明不能将 $s$ 变为 $f$,输出 NO
。
再总结一下,我们需要维护一个二进制串,支持以下操作:
- 查询某个区间 $[l, r]$ 中,
1
的个数和0
的个数。 - 将某个区间 $[l, r]$,全部修改为
0
或全部修改为1
。
而对于操作一,因为二进制串中只有 1
和 0
,所以 $[l, r]$ 的区间和即为 1
的个数,区间长度减去区间和即为 0
的个数。
所以操作一可变为查询区间和。
那么我们要进行的操作,可变为:
- 查询区间和
- 区间修改为某个值
而这恰可以用懒标记线段树做,那么这题就做完了。
时间复杂度
我们要维护一棵总长度为 $n$ 线段树。
我们要在线段树中进行 $n$ 次修改,将线段树初始化成 $f$,然后进行 $q$ 次区间查询与区间修改。
所以总复杂度为 $O((n + q) \log n)$。
当然我们可以分治初始化,将时间复杂度降为 $O(n + q \log n)$。但这并没啥用。
C++ 代码
#include <cstdio>
#include <cstring>
const int N = 200005;
const int M = 800005;
// 别看啦总之就是线段树啦
struct SegmentTree
{
struct Node
{
int l, r;
int sv, tag;
} tr[M];
void pushup(int u)
{
tr[u].sv = tr[u << 1].sv + tr[u << 1 | 1].sv;
}
void pushdown(int u)
{
if (~tr[u].tag)
{
int& v = tr[u].tag;
tr[u << 1].tag = v;
tr[u << 1 | 1].tag = v;
tr[u << 1].sv = (tr[u << 1].r - tr[u << 1].l + 1) * v;
tr[u << 1 | 1].sv = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * v;
v = -1;
}
}
void build(int l, int r, int u = 1)
{
tr[u].tag = -1;
tr[u].l = l, tr[u].r = r;
if (l == r) return;
int mid = l + r >> 1;
build(l, mid, u << 1);
build(mid + 1, r, u << 1 | 1);
}
void change(int l, int r, int c, int u = 1)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].tag = c;
tr[u].sv = c * (tr[u].r - tr[u].l + 1);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) change(l, r, c, u << 1);
if (mid < r) change(l, r, c, u << 1 | 1);
pushup(u);
}
int query(int l, int r, int u = 1)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sv;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(l, r, u << 1);
if (mid < l) return query(l, r, u << 1 | 1);
return query(l, r, u << 1) + query(l, r, u << 1 | 1);
}
} z;
int n, m;
char s[N], f[N];
int l[N], r[N];
int main()
{
int task;
scanf("%d", &task);
while (task -- )
{
scanf("%d%d%s%s", &n, &m, s + 1, f + 1);
for (int i = 1; i <= m; i ++ ) scanf("%d%d", l + i, r + i);
// 将线段树初始化成 s(这里直接 nlogn 暴力初始化)
z.build(1, n);
for (int i = 1; i <= n; i ++ ) z.change(i, i, f[i] - '0');
// 从 f 往前反推每个字符串
bool yes = true;
for (int i = m; i && yes; i -- )
{
int ones = z.query(l[i], r[i]); // 查 1 的个数
if (ones * 2 == r[i] - l[i] + 1) yes = false; // 如果 1 的个数恰好等于 0 的个数,则输出 NO
else if (ones * 2 < r[i] - l[i] + 1) z.change(l[i], r[i], 0); // 否则如果 1 的个数少,则将区间修改为 0
else z.change(l[i], r[i], 1); // 否则将区间修改为 1
}
// 判断最后得到的 t0 是否为等于 s
for (int i = 1; i <= n; i ++ )
if (z.query(i, i) != s[i] - '0')
{
yes = false;
break;
}
puts(yes ? "YES" : "NO");
}
return 0;
}
$$ $$