Codeforces Round #698 (Div. 2) E. Nezzar and Binary String 离线+线段树

https://codeforces.ml/contest/1478/problem/E

题意

给你两个01字符串，要求从第一个字符串转换成第二个字符串，并满足以下要求

1. 每次给定一个检查区间，要求这个区间内必须是单一的0或1
2. 你可以在检查之后偷偷修改严格小于区间一半的字符数
   如果可以转换成功输出YES，否则输出NO

分析

正难则反，我们可以考虑离线的做法，从最后的状态一步步推到最初的状态，因为从后往前方案是一定确定的。我们只需要统计当前区间内有多少个1和0，然后判断应该怎么去翻就可以了。
方案如下

1. 如果当前区间内的1严格小于一半，那么就全部翻成0
2. 如果当前区间内的1严格大于一半，那么就全部翻成1
3. 如果1和0个数相同，直接输出无解

区间覆盖统计问题用线段树就可以完美实现。

Code

#include <bits/stdc++.h>
using namespace std;
//#define ACM_LOCAL
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll INF = 1e18;
const double eps = 1e-4;
struct Node {
    int l, r, tag;
    int sum;
}t[N<<2];

struct Query {
    int x, y;
}q[N];
string s1, s2;

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

void push_down(int u) {
    if (t[u].tag != -1) {
        t[u<<1].tag = t[u].tag;
        t[u<<1|1].tag = t[u].tag;
        t[u<<1].sum = (t[u<<1].r - t[u<<1].l + 1) * t[u].tag;
        t[u<<1|1].sum = (t[u<<1|1].r - t[u<<1|1].l + 1) * t[u].tag;
        t[u].tag = -1;
    }
}

void build(int u, int l, int r) {
    t[u].l = l, t[u].r = r, t[u].tag = -1;
    if (l == r) {
        t[u].sum = s2[l-1] - '0';
        return;
    }
    int mid = l + r >> 1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
    push_up(u);
}

void modify(int u, int ql, int qr, int v) {
    if (ql <= t[u].l && qr >= t[u].r) {
        t[u].sum = v * (t[u].r - t[u].l + 1);
        t[u].tag = v;
        return;
    }
    push_down(u);
    int mid = t[u].l + t[u].r >> 1;
    if (ql <= mid) modify(u<<1, ql, qr, v);
    if (qr > mid) modify(u<<1|1, ql, qr, v);
    push_up(u);
}

int query(int u, int ql, int qr) {
    if (ql <= t[u].l && qr >= t[u].r) {
        return t[u].sum;
    }
    push_down(u);
    int mid = t[u].l + t[u].r >> 1;
    int ans = 0;
    if (ql <= mid) ans += query(u<<1, ql, qr);
    if (qr > mid) ans += query(u<<1|1, ql, qr);
    return ans;
}

void solve() {
    int T; cin >> T; while (T--) {
        int n, k; cin >> n >> k;
        cin >> s1 >> s2;
        for (int i = 1; i <= k; i++) cin >> q[i].x >> q[i].y;
        build(1, 1, n);
        int f = 0;
        for (int i = k; i >= 1; i--) {
            int tmp = query(1, q[i].x, q[i].y);
            int len = q[i].y - q[i].x + 1;
            if (tmp * 2 == len) {
                f = 1;
                break;
            }
            if (tmp * 2 < len) modify(1, q[i].x, q[i].y, 0);
            else modify(1, q[i].x, q[i].y, 1);
        }
        for (int i = 1; i <= n; i++) {
            if (query(1, i, i) != s1[i-1] - '0') f = 1;
        }
        if (f) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    solve();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106