题解 CF1477B 【Nezzar and Binary String】

· · 题解

E - Nezzar and Binary String

A 有一个长度为 n 的二进制串 S，他想让自己最好的朋友 B 看，B将会用 q 天的时间来检查这个二进制串。 第 i 天， B会在这一天早上检查这个二进制串的一个区间 [l_i,r_i] ，如果这个区间内的数字全部都是一致的，也就是全部都为 1 或者全部都为 0 ，B就会很开心，否则她就会不开心。 A为了使 B 每次检查都能变得开心，所以 A 会在每天 B 检查之后的当天晚上偷偷地去修改这个二进制串，使得 B 第二天检查的时候能够开心。为了不被 B 发现，A 每次只能修改今天早上 B 检查过的那个区间 [l_i,r_i]，并且修改的字符的个数必须小于这个区间字符总数的一半，

与此同时，A还有一个任务，就是他希望可以通过这 q 天的修改，将二进制串 s 变成 f 。请问 A 能够在每天都保证 B 开心的同时，将二进制串 s 修改为 f 呢吗？

$1 \le t \le 2 \cdot 10^5,1 \le n \le 2 \cdot 10^5,0 \le q \le 2 \cdot 10^5 
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

Solution

我们本来按照题意的顺序，是她先查看，我们再修改，但是每次改都要受到之后她查看的区间的影响。

比如样例一：

第一天，她要看 [1,5] ，很开心走了 ~

第一天晚上，我可以改 [1,5] ，但是她明天要看 [1,3] ，所以我要先保证 [1,3] 是没有 0,1 同时存在的，再看能不能改 [1,5] 的其他元素使得s\to f，就很怪，当前的操作需要考虑之后的影响，我们还需要提前知道下一次的操作区间，就很奇怪。

第二天，她要看 [1,3]，因为前一天晚上我的努力，她很开心的走了 ~

第二天晚上，我可以改 [1,3]，明天她不看了，我就尽量改

[1,3]$ 使得$s\to f

但是如果我们反过来，变成我们先改，她再看，也就是我们早上先改，晚上她再看，就很舒服。

第一天早上，我可以改 [1,3] ，因为她晚上要看 [1,3] ，所以我们只需要保证 [1,3] 是没有 0,1 同时存在的，再尽量朝着 f\to s 的方向改 [1,3] 。

第一天晚上，她看完 [1,3] ，开心地走了 ~

第二天早上，我可以改 [1,5]，因为她晚上要看 [1,5]，我们就保证 [1,5] 是没有 0,1 同时存在的，再尽量朝着 f\to s 的方向改 [1,5] ，因为这是最后一天了，我发现可以直接把 f 变成 s ，并且 s 串全是 0，她看了一定很开心 (●ˇ∀ˇ●) ，我就这么做了

第二天，她要看 [1,5]，因为早上我的努力，她开心地蹦蹦跳跳的走了 ~

其实正序做不只是很做起来，而且最关键的是，我们需要自己考虑最优解，这是非常困难的，而我们交换顺序对题目的答案不会造成任何影响，但是却会给我们的实现带来很大的方便，并且稍微分析一下就会发现，逆序做，不需要我们有任何操作空间。

使用逆向思维，可以帮助我们简化这个问题。然后我们来考虑怎么解决这个问题。

我们将会从 f 出发，满足每次区间的一致性，致力于得到 s 。

由于我们只有一个操作：修改定区间内的二进制串，并且每次最多只能修改个数小于区间长度的一半。

实际上这就代表着我们只能有一种修改方式：将 0,1 中数量少的那一方修改为另一方，因为只有这样修改，我们才既能保证区间内的字符完全相同，又能保证修改的数量不超过区间长度的一半。

但是如果区间内 0,1 的数量相同，那就没办法修改了，无论偏袒哪一方都不能在修改小于区间长度的一半的条件下修改成同一个数字，直接输出 NO 即可。

然后我们发现我们会跟着这个区间的设定，一步一步没有任何操作空间地从头修改到最后，所以如果最后我们得到的字符串，如果就是 s，那么恭喜你，成功完成了这个任务，你会很开心，她会很开心，我们都获得了快乐，直接输出 YES 即可。

同理，如果最后得到的不是 s，那么抱歉，输出 NO 。

最后一个问题，如果快速地实现区间修改呢？

我们发现我们只需要有两个操作即可：区间全部修改（区间染色），区间查询（查询 0,1 的个数）

而数据很大：1 \le t \le 2 \cdot 10^5,1 \le n \le 2 \cdot 10^5,0 \le q \le 2 \cdot 10^5，需要 O(Tqlogn) 的时间复杂度以及高超的卡常技巧，这一切无不指引着一个神奇的数据结构：线段树 ~

我们只需要维护区间和就行了，因为区间和就是1的个数。

由于需要区间查询，所以我们需要加上lazytag，就是我们修改的时候，区间是 0 还是 1。由于不能初始化为 0 ，重复了，所以我们记得初始化为 -1 就好。

然后就是很简单的代码了：

Code

注意：毒瘤出题人把数据开到了 2\times 10^5，而线段树需要开四倍空间。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef int itn;
const int N = 3e5 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;

int n, m, q;
int L[N], R[N];
char s[N], f[N];

struct Tree
{
    int l, r;
    int sum;//维护 1 的个数, 因为 0 求和还是 0 和就是 1 的个数
    int lz;//1 / 0
}tr[N << 2];

void push_up(int p)
{
    tr[p].sum = tr[p << 1].sum +  tr[p << 1 | 1].sum;
}

void push_down(int p)
{
     if(tr[p].lz == -1) return ;
     tr[p << 1].lz = tr[p].lz;
     tr[p << 1 | 1].lz = tr[p].lz;
     tr[p << 1].sum = (tr[p << 1].r - tr[p << 1].l + 1) * tr[p].lz;//都是等于而不是加
     tr[p << 1 | 1].sum = (tr[p << 1 | 1].r - tr[p << 1 | 1].l + 1) * tr[p].lz;
     tr[p].lz = -1;
}

void build(int p, int l, int r)//f
{
    tr[p].l = l, tr[p].r = r, tr[p].lz = -1;
    if(l == r) {
        tr[p].sum = f[l] - '0';
        tr[p].lz = -1;
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
}

void modify(int p, int l, int r, int val)
{
    if(tr[p].l >= l && tr[p].r <= r) {
        tr[p].sum = (tr[p].r - tr[p].l + 1) * val;//这里全部变成 1 ，sum 等于区间长度，全部变成 0, sum 就是 0
        tr[p].lz = val;
        return ;
    }
    push_down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if(l <= mid) modify(p << 1, l, r, val);
    if(r > mid) modify(p << 1 | 1, l, r, val);
    push_up(p);
}

int query(int p, int l, int r)
{
    if(tr[p].l >= l && tr[p].r <= r) {
        return tr[p].sum;
    }
    push_down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    int res = 0;
    if(l <= mid) res += query(p << 1, l, r);
    if(r > mid) res += query(p << 1 | 1, l, r);
    return res;
}

bool check()
{
    for(int i = 1; i <= n; ++ i) {
        if(query(1, i, i) != s[i] - '0') {
            return false;
        }
    }
    return true;
}

bool solve()
{
    scanf("%d %d", &n, &q);
    scanf("%s %s", s + 1, f + 1);
    for (int i = 1; i <= q; ++ i) {
        scanf("%d %d", &L[i], &R[i]);
    }
    build (1, 1, n);
    for(int i = q; i >= 1; -- i) {
        int l = L[i], r = R[i];
        int num1 = query(1, l, r);//sum
        int len = r - l + 1;
        if (num1 * 2 == len) return false;// 0 和 1 的长度相等 
        else if(num1 * 2 < len) modify(1, l, r, 0);
        else modify(1, l, r, 1);
    }

    if (!check()) {
        return false;
    }
    return true;
}

itn t;

int main()
{
    scanf("%d", &t);
    while (t -- ) {
        if (solve()) {
            puts("YES");
        }
        else {
            puts("NO");
        }
    }
    return 0;
}