传送门
题意：两个01字符串s和f，q个区间询问，每次询问需要保证区间全为0或1，每次询问后可修改小于区间长度一半的字符，问是否能将s经过q次转换到达f
倒序遍历询问，可以先修改再保证区间全0或全1，用线段树区间修改区间查询即可
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
using pii = pair<int, int>;
string s, f;struct node {int l, r, sum, lazy;
}tree[maxn << 2];void push_up(int root)
{tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}
void build(int root, int l, int r)
{tree[root].l = l, tree[root].r = r;tree[root].lazy = -1;if(l == r) {tree[root].sum = f[l - 1] == '1' ? 1 : 0;return;}int mid = (l + r) >> 1;build(root << 1, l, mid);build(root << 1 | 1, mid + 1, r); push_up(root);
}
void push_down(int root)
{if(tree[root].l == tree[root].r) return;tree[root << 1].lazy = tree[root << 1 | 1].lazy = tree[root].lazy;if(tree[root].lazy){tree[root << 1].sum = tree[root << 1].r - tree[root << 1].l + 1;tree[root << 1 | 1].sum = tree[root << 1 | 1].r - tree[root << 1 | 1].l + 1;}else {tree[root << 1].sum = tree[root << 1 | 1].sum = 0;}tree[root].lazy = -1;
}
void update(int root, int l, int r, int tmp)
{if(tree[root].l >= l && tree[root].r <= r){tree[root].lazy = tmp;if(tmp) tree[root].sum = tree[root].r - tree[root].l + 1;else tree[root].sum = 0;return;}if(~tree[root].lazy)push_down(root);int mid = (tree[root].r + tree[root].l) >> 1;if(mid >= l) update(root << 1, l, r, tmp);if(mid < r) update(root << 1 | 1, l, r, tmp);push_up(root);
}
int query(int root, int l, int r)
{if(tree[root].l >= l && tree[root].r <= r) return tree[root].sum;if(~tree[root].lazy) push_down(root);int mid = (tree[root].l + tree[root].r) >> 1;int res = 0;if(mid >= l) res += query(root << 1, l, r);if(mid < r) res += query(root << 1 | 1, l, r);return res;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) {int n, q;cin >> n >> q;vector<pii>a(q);cin >> s >> f;build(1, 1, n);for(int i = 0; i < q; ++i) cin >> a[i].first >> a[i].second;reverse(a.begin(), a.end());int ok = 1;for(int i = 0; i < q; ++i){int cnt1 = query(1, a[i].first, a[i].second);int cnt2 = a[i].second - a[i].first + 1 - cnt1;// cout << "**" << cnt1 << " " << cnt2 << endl;if(cnt1 == cnt2){ok = 0;break;} else if(cnt1 > cnt2){update(1, a[i].first, a[i].second, 1);} else {update(1, a[i].first, a[i].second, 0);}}for(int i = 0; i < n; ++i){int tmp = query(1, i + 1, i + 1);// cout << tmp << endl;if(s[i] - '0' != tmp){ok = 0;break;}}printf("%s\n", ok ? "YES" : "NO");}return 0;
}