Math jam#11770

Math jam (Editorial)

Problem Author:	Ivan Balashov, Kostiantyn Denysov
Prepared by:	Kostiantyn Denysov
Editorial by:	Ivan Balashov, Kostiantyn Denysov

First, consider the case where $r_{i} = 0$ r_i = 0 when $t_{i} = A$ t_i = A and $a_{i} = 0$ a_i = 0 when $t_{i} = R$ t_i = R. In this case, we only need to store the value $v a l_{i} = a_{i} - r_{i}$ val_i = a_i - r_i for each tower. The problem is then trivially reduced to finding the sum

s = v a l_{l} + v a l_{l + 1} + \dots + v a l_{r} .

s = val_l + val_{l+1} + \dots + val_r.

If $s > 0$ s > 0, we print "Daria"; otherwise, we print "Mary".

Now, consider the case where both $a_{i} > 0$ a_i > 0 and $r_{i} > 0$ r_i > 0, but $a_{i} > r_{i}$ a_i > r_i for $t_{i} = A$ t_i = A or $r_{i} > a_{i}$ r_i > a_i for $t_{i} = R$ t_i = R. It is easy to see that this situation is no different from the previous one since eating more than one sandwich per turn is of no use.

Finally, consider the case where $t_{i} = A$ t_i = A and $a_{i} \leq r_{i}$ a_i \leq r_i. The simplest tower of this type is "AR". Note that a game with two "AR" towers reduces to a game with one "A" tower after two moves (regardless of who moves first). This is true for any tower with $t_{i} = A$ t_i = A as long as $r_{i} - a_{i} = 0$ r_i - a_i = 0. Similarly, if $r_{i} - a_{i} = 1$ r_i - a_i = 1, playing on two such towers is equivalent to playing on one "AR" tower, and so on.

Now observe that our answer does not change if we count each tower $2^{1 0^{5}}$ 2^{10^5} times instead of once. Based on this, we define $v a l_{i}$ val_i for each tower case:

$v a l_{i} = 2^{1 0^{5}} \cdot (a_{i} - r_{i})$ val_i = 2^{10^5} \cdot (a_i - r_i) for $a_{i} > r_{i} and t_{i} = A$ a_i > r_i \text{ and } t_i = A, or $r_{i} > a_{i} and t_{i} = R$ r_i > a_i \text{ and } t_i = R;
$v a l_{i} = 2^{1 0^{5} - 1 + a_{i} - r_{i}}$ val_i = 2^{10^5 - 1 + a_i - r_i} for $a_{i} \leq r_{i} and t_{i} = A$ a_i \leq r_i \text{ and } t_i = A;
$v a l_{i} = - 2^{1 0^{5} - 1 + r_{i} - a_{i}}$ val_i = -2^{10^5 - 1 + r_i - a_i} for $r_{i} \leq a_{i} and t_{i} = R$ r_i \leq a_i \text{ and } t_i = R.

To answer the query, we need to determine whether

v a l_{l} + v a l_{l + 1} + \dots + v a l_{r} > 0.

val_l + val_{l+1} + \dots + val_r > 0.

Define $p$ as the prefix sum array of $v a l$ , where $p_{0} = 0$ p_0 = 0 and $p_{i} = p_{i - 1} + v a l_{i}$ p_i = p_{i-1} + val_i. The problem reduces to checking whether $p_{r} > p_{l - 1}$ p_r > p_{l-1}.

Naively, we cannot compute $p_{i}$ p_i directly because the numbers are too large, each having approximately $1 0^{5} + 40$ 10^5 + 40 bits (the additional $40$ comes from values of type $1$ ). However, we can use a persistent segment tree to solve this problem efficiently.

For $v a l_{i}$ val_i of types $2$ and $3$ , the value adds or subtracts a power of two. This can be handled using a segment tree with pushes (promises) where each leaf stores the corresponding bit value.

For $v a l_{i}$ val_i of type $1$ , we can handle the $40$ highest bits by first loading them from the segment tree, converting them into a long long value, performing the addition, and then updating these $40$ bits in the segment tree using the resulting integer. This operation works in $O (lo g (bits))$ O(\log(\text{bits})) because the $40$ bits are consecutive in the segment tree.

Using hashes, we can compare two versions of the persistent segment tree to efficiently determine whether $p_{r} > p_{l - 1}$ p_r > p_{l-1} to get the answer for a query.

Time complexity: $O ((n + q) lo g max a)$ O((n + q) \log {\max a})

Memory complexity: $O (n lo g max a)$ O(n \log {\max a})

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 2e7 + 5e6 + 11, inf = 1000111222;


struct num {
    static const int MA = 1e9 + 7, MB = 1e9 + 9;

    int a, b;

    num() : a(0), b(0) { }
    num( int x ) : a(x), b(x) { }
    num( int a, int b ) : a(a), b(b) { }

    num operator + ( const num &x ) const { return num((a + x.a) % MA, (b + x.b) % MB); }
    num operator - ( const num &x ) const { return num((a + MA - x.a) % MA, (b + MB - x.b) % MB); }
    num operator * ( int x ) const { return num(((ll)a * x) % MA, ((ll)b * x) % MB); }
    num operator * ( const num &x ) const { return num(((ll)a * x.a) % MA, ((ll)b * x.b) % MB); }
    bool operator == ( const num &x ) const { return a == x.a && b == x.b; }
    bool operator != ( const num &x ) const { return !(a == x.a && b == x.b); }

};




const int mx = 40;

const int m = 1e5 + mx;
num prec[2][m + 1];
num st[m + 1];


struct node {
    int push, l, r;
    num h;

    node () : h(0), push(-1) {}

    node (int x) : h(prec[x][1]), push(x) {}

    node (num h) : h(h), push(-1) {}
};


inline node comb (node a, node b, int l, int L, int R) {
    node res(a.h + b.h * st[l]);
    res.l = L;
    res.r = R;
    return res;
}

node t[max_n];
int cur = 0;


inline int build (int tl, int tr) {
    int now = cur++;
    if (tl == tr) {
        t[now] = node(tr == 0);
        return now;
    }
    int tm = (tl + tr) >> 1;
    int L = build( tl, tm);
    int R = build(tm + 1, tr);
    t[now] = comb(t[L], t[R], tm - tl + 1, L, R);
    return now;
}


inline int init () {
    return build(0, m - 1);
}

int prv = -1;

inline void save_tick() {
    prv = cur;
}

inline int make_copy (int v) {
    if (prv < v) {
        return v;
    }
    int ver = cur++;
    assert(ver < max_n);
    t[ver].push = t[v].push;
    t[ver].h = t[v].h;
    t[ver].l = t[v].l;
    t[ver].r = t[v].r;
    return ver;
}


inline void push (int v, int tl, int tr) {
    if (t[v].push != -1 && tl != tr) {
        int tm = (tl + tr) >> 1;
        t[t[v].l].h = prec[t[v].push][tm - tl + 1];
        t[t[v].r].h = prec[t[v].push][tr - tm];
        t[t[v].l].push = t[v].push;
        t[t[v].r].push = t[v].push;
        t[v].push = -1;
    }
}

inline void copy_sons (int v) {
    t[v].l = make_copy(t[v].l);
    t[v].r = make_copy(t[v].r);
}

inline void upd (int v, int tl, int tr, int l, int r, int val) {
    if (l > r) {
        return;
    }
    if (tl != tr) {
        copy_sons(v);
        push(v, tl, tr);
    }
    if (tl == l && tr == r) {
        t[v].h = prec[val][tr - tl + 1];
        t[v].push = val;
        return;
    }
    int tm = (tl + tr) >> 1;
    upd(t[v].l, tl, tm, l, min(r, tm), val);
    upd(t[v].r, tm + 1, tr, max(tm + 1, l), r, val);
    t[v] = comb(t[t[v].l], t[t[v].r], tm - tl + 1, t[v].l, t[v].r);
}

inline num get_h (int s, int v, int l) {
    if (s == -1) {
        return t[v].h;
    }
    return prec[s][l];
}

inline bool have_val (int v, int val, int l, int s) {
    return get_h(s, v, l) != prec[val ^ 1][l];
}

inline int _merge (int s, int v) {
    if (s != -1 || t[v].push == -1) {
        return s;
    }
    return t[v].push;
}

inline int find_last (int v, int tl, int tr, int r, int val, int s) {
    s = _merge(s, v);
    if (tl > r || !have_val(v, val, tr - tl + 1, s)) {
        return -1;
    }
    if (tl == tr) {
        return tr;
    }
    int tm = (tl + tr) >> 1;
    int R = find_last(t[v].r, tm + 1, tr, r, val, s);
    if (R != -1) {
        return R;
    }
    return find_last(t[v].l, tl, tm, min(r, tm), val, s);
}


inline void add_st (int v, int x) {
    x += mx;
    int pos = find_last(v, 0, m - 1, x, 0, -1);
    upd(v, 0, m - 1, pos, pos, 1);
    upd(v, 0, m - 1, pos + 1, x, 0);
}

inline void sub_st (int v, int x) {
    x += mx;
    int pos = find_last(v, 0, m - 1, x, 1, -1);
    upd(v, 0, m - 1, pos, pos, 0);
    upd(v, 0, m - 1, pos + 1, x, 1);
}


ll cur_val;

inline void load_val (int v, int r, int tl, int tr) {
    if (tl > r) {
        return;
    }
    if (tl == tr) {
        cur_val |= ll(t[v].push) << (mx - 1ll - tr);
        return;
    }
    copy_sons(v);
    push(v, tl, tr);
    int tm = (tl + tr) >> 1;
    load_val(t[v].l, min(r, tm), tl, tm);
    load_val(t[v].r, r, tm + 1, tr);
}

inline void load_back (int v, int r, int tl, int tr) {
    if (tl > r) {
        return;
    }
    if (tl == tr) {
        t[v] = node(bool(cur_val & (1ll << (mx - 1ll - tr))));
        return;
    }
    int tm = (tl + tr) >> 1;
    load_back(t[v].l, min(r, tm), tl, tm);
    load_back(t[v].r, r, tm + 1, tr);
    t[v] = comb(t[t[v].l], t[t[v].r], tm - tl + 1, t[v].l, t[v].r);
}


inline void change (int v, int x) {
    cur_val = 0;
    load_val(v, mx - 1, 0, m - 1);
    cur_val += x;
    assert(cur_val > 0);
    load_back(v, mx - 1, 0, m - 1);
}





inline bool go_check (int v1, int v2, int tl, int tr, int s1, int s2) {
    s1 = _merge(s1, v1);
    s2 = _merge(s2, v2);
    if (tl == tr) {
        return s1 > s2;
    }

    int tm = (tl + tr) >> 1;
    if (get_h(s1, t[v1].l, tm - tl + 1) != get_h(s2, t[v2].l, tm - tl + 1)) {
        return go_check(t[v1].l, t[v2].l, tl, tm, s1, s2);
    }
    return go_check(t[v1].r, t[v2].r, tm + 1, tr, s1, s2);
}

inline bool bigger (int v1, int v2) {
    return go_check(v1, v2, 0, m - 1, -1, -1);
}


const num base(998244353, 437243);


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    st[0] = 1;
    prec[0][0] = 0;
    prec[1][0] = 0;
    for (int i = 1; i <= m; i++) {
        st[i] = st[i - 1] * base;
        prec[0][i] = prec[0][i - 1] * base + 0;
        prec[1][i] = prec[1][i - 1] * base + 1;
    }

    int n, q;
    cin >> n >> q;
    char c;
    vector <int> pref(n + 1);
    pref[0] = init();
    for (int i = 0, x, y; i < n; i++) {
        save_tick();
        int v = make_copy(pref[i]);
        pref[i + 1] = v;
        cin >> c >> x >> y;
        x -= y;
        if (c == 'A') {
            if (x > 0) {
                change(v, x);
            }
            else {
                x = -x;
                add_st(v, x);
            }
        }
        else {
            if (x < 0) {
                x = -x;
                change(v, -x);
            }
            else {
                sub_st(v, x);
            }
        }
    }

    for (int i = 0, l, r; i < q; i++) {
        cin >> l >> r;
        --l;
        if (bigger(pref[r], pref[l])) {
            cout << "Daria\n";
        }
        else {
            cout << "Mary\n";
        }
    }
}

C++