NOI2017D1T1 Integer

#include <cstdio>
#include <cstdint>
#include <cstddef>

#include <algorithm>

using namespace std;

struct node {
    int l, r;
    node *ls, *rs;
    uint64_t d;

    void push_down();
    void update();
    bool plus(int x, uint64_t y);
    bool plus();
    bool minus(int x, uint64_t y);
    bool minus();
    uint64_t query(int x);
};

const int N = 1000010;

int n;
node* root;

node* build_tree(int l, int r);

int main() {
    int op, b, rest;
    long long a;
    {
        int ig;
        scanf("%d%d%d%d", &n, &ig, &ig, &ig);
    }
    root = build_tree(0, max(52, (n >> 1) + 2));
    while (n--) {
        scanf("%d%lld", &op, &a);
        if (op == 1) {
            scanf("%d", &b);
            rest = b & 63;
            b >>= 6;
            if (a < 0) {
                a = -a;
                if (rest) {
                    root->minus(b, (uint64_t)a << rest);
                    root->minus(b + 1, a >> (64 - rest));
                } else
                    root->minus(b, a);
            } else if (rest) {
                root->plus(b, (uint64_t)a << rest);
                root->plus(b + 1, a >> (64 - rest));
            } else
                root->plus(b, a);
        } else
            printf("%d\n", bool(root->query(a >> 6) & (1ULL << (a & 63))));
    }
    return 0;
}

node* build_tree(int l, int r) {
    static node pool[N];
    static int top;
    node* p = pool + ++top;
    p->l = l;
    p->r = r;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    p->ls = build_tree(l, mid);
    p->rs = build_tree(mid + 1, r);
    return p;
}

inline void node::push_down() {
    if (d == 0)
        ls->d = rs->d = 0;
    else if (d == UINT64_MAX)
        ls->d = rs->d = UINT64_MAX;
}

inline void node::update() {
    if (ls->d == rs->d)
        d = ls->d;
    else d = 1;
}

inline uint64_t node::query(int x) {
    if (l == r)
        return d;
    push_down();
    if (ls->r >= x)
        return ls->query(x);
    return rs->query(x);
}

bool node::plus(int x, uint64_t y) {
    if (l == r) {
        uint64_t cur = d;
        d += y;
        return cur > d;
    }
    push_down();
    if (ls->r >= x) {
        if (ls->plus(x, y))
            if (rs->plus()) {
                update();
                return true;
            }
        update();
        return false;
    }
    if (rs->plus(x, y)) {
        update();
        return true;
    }
    update();
    return false;
}

bool node::minus(int x, uint64_t y) {
    if (l == r) {
        uint64_t cur = d;
        d -= y;
        return cur < d;
    }
    push_down();
    if (ls->r >= x) {
        if (ls->minus(x, y))
            if (rs->minus()) {
                update();
                return true;
            }
        update();
        return false;
    }
    if (rs->minus(x, y)) {
        update();
        return true;
    }
    update();
    return false;
}

bool node::plus() {
    if (d == UINT64_MAX) {
        d = 0;
        return true;
    }
    if (l == r) {
        ++d;
        return false;
    }
    if (!ls->plus()) {
        update();
        return false;
    }
    bool f = rs->plus();
    update();
    return f;
}

bool node::minus() {
    if (!d) {
        d = UINT64_MAX;
        return true;
    }
    if (l == r) {
        --d;
        return false;
    }
    if (!ls->minus()) {
        update();
        return false;
    }
    bool f = rs->minus();
    update();
    return f;
}