Камбек#12199
Problem Author: | Maksym Shvedchenko |
Prepared by: | Maksym Shvedchenko and Iliia Shevchenko |
Editorial by: | Maksym Shvedchenko |
The definition of majorization can be stated as follows: let prefA_i be the prefix sum of string up to index , and prefB_i for string . Then majorizes if prefA_i \ge prefB_i for all 1 \le i \le n.
Introduce c_i = a_i - b_i. Then the condition is equivalent to prefC_i \ge 0 for all 1 \le i \le n, which already makes the problem solvable with a persistent segment tree supporting range updates. However, in terms of implementation and constants this is not optimal.
Notice: if l_b < l_a and there is at least one in on the interval [l_b, l_a], then both segments [l_a, r_a] and [l_b, r_b] must contain no s. Otherwise, we could simply set l_b = l_a without changing anything.
Thus, we compute the balance on the prefix, update with it, and descend in the tree to the first index where prefC_i - bal < 0. From there we take the minimum of the number of s in and , and with another descent we determine the boundaries r_a and r_b. If l_a < l_b, this only affects the balance, and everything else stays the same.
Result: time complexity O(n \log n), memory .
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define inf 1000'000'000LL
#define len(x) (int) x.size()
#define low_bit(x) ((x) & (-(x)))
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
template<typename T>
using vec = vector<T>;
struct fenvik {
vec<int> fen;
vec<int> a;
int get(int i) {
int res = 0;
for (; i > 0; i -= low_bit(i)) {
res += fen[i];
}
return res;
}
public:
fenvik(int n) : fen(n + 1, 0), a(n, 0) {}
void set(int i, int x) {
int delta = x - a[i];
a[i] = x;
i++;
for (; i < len(fen); i += low_bit(i)) {
fen[i] += delta;
}
}
int get(int l, int r) {
if (l > r) return 0;
return get(r + 1) - get(l);
}
void flip(int i) {
set(i, 1 - a[i]);
}
int lower_bound(int x) {
if (x <= 0) return 0;
int res = 0;
int n = len(fen);
for (int i = 20; i >= 0; i--) {
if (res + (1 << i) < n and fen[res + (1 << i)] < x) {
x -= fen[res + (1 << i)];
res += (1 << i);
}
}
n--;
if (res >= n) return n;
return res;
}
};
const int maxN = 1e6 + 5;
struct Vertex {
int min_pref;
int sum;
};
Vertex merge(const Vertex &a, const Vertex &b) {
Vertex res{};
res.sum = a.sum + b.sum;
res.min_pref = a.min_pref;
chmin(res.min_pref, a.sum + b.min_pref);
return res;
}
Vertex stree[maxN * 4];
void build(int v, int tl, int tr, vec<int> &a) {
if (tl == tr) {
stree[v] = {a[tl], a[tl]};
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm, a);
build(v * 2 + 1, tm + 1, tr, a);
stree[v] = merge(stree[v * 2], stree[v * 2 + 1]);
}
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
stree[v].min_pref += val;
stree[v].sum += val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(v * 2, tl, tm, pos, val);
} else {
update(v * 2 + 1, tm + 1, tr, pos, val);
}
stree[v] = merge(stree[v * 2], stree[v * 2 + 1]);
}
int find_first(int v, int tl, int tr, int l, int r, int K) {
if (stree[v].min_pref >= K) return -1;
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
if (r <= tm) {
return find_first(v * 2, tl, tm, l, r, K);
}
int d = stree[v * 2].sum;
if (l > tm) {
return find_first(v * 2 + 1, tm + 1, tr, l, r, K - d);
}
int res = find_first(v * 2, tl, tm, l, tm, K);
if (res != -1) {
return res;
}
return find_first(v * 2 + 1, tm + 1, tr, tm + 1, r, K - d);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, q;
cin >> n >> q;
vec<int> a(n);
fenvik fa(n);
for (int i = 0; i < n; i++) {
char c;
cin >> c;
a[i] = c - '0';
fa.set(i, a[i]);
}
vec<int> b(n);
fenvik fb(n);
for (int i = 0; i < n; i++) {
char c;
cin >> c;
b[i] = c - '0';
fb.set(i, b[i]);
}
vec<int> c(n);
for (int i = 0; i < n; i++) {
c[i] = a[i] - b[i];
}
build(1, 0, n - 1, c);
auto add = [&](int i, int x) {
update(1, 0, n - 1, i, x);
};
while (q--) {
int t;
cin >> t;
if (t == 1) {
int delta = 0;
char tc;
int x;
cin >> tc >> x;
--x;
if (tc == 'a') {
if (a[x] == 0) {
delta = 1;
} else {
delta = -1;
}
a[x] ^= 1;
fa.flip(x);
} else {
if (b[x] == 0) {
delta = -1;
} else {
delta = 1;
}
b[x] ^= 1;
fb.flip(x);
}
add(x, delta);
} else {
int la, lb;
cin >> la >> lb;
--la, --lb;
int mx_cnt = inf;
int cnt_a = 0;
int cnt_b = 0;
int K = 0;
int Brd = n;
int gt;
if (lb < la) {
if (fb.get(lb, la - 1) > 0) {
mx_cnt = 0;
goto h;
}
if (b[la] == 1 and a[la] == 0) {
mx_cnt = 0;
goto h;
}
}
K += fa.get(0, la - 1);
K -= fb.get(0, lb - 1);
gt = find_first(1, 0, n - 1, la, n - 1, K);
if (gt != -1) {
Brd = gt;
}
if (Brd <= la or Brd <= lb) {
cout << "-1 -1" << endl;
continue;
}
cnt_a = fa.get(la, Brd - 1);
cnt_b = fb.get(lb, Brd - 1);
h:
cnt_a = min({cnt_a, cnt_b, mx_cnt});
cnt_b = cnt_a;
int da = fa.get(0, la - 1);
int ra = fa.lower_bound(cnt_a + 1 + da);
int rb = n;
int db = fb.get(0, lb - 1);
rb = fb.lower_bound(cnt_b + 1 + db);
if (la == ra or lb == rb) {
cout << "-1 -1" << endl;
continue;
}
cout << ra << " " << rb << endl;
}
}
}