代码

// 压32bit，否则不好处理 
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;

typedef int i32;
typedef long long i64;
typedef __int128 i128;

typedef unsigned u32;
typedef unsigned long long u64;
typedef unsigned __int128 u128;

const int MAXN = 1e6+2;
const u32 NONEMARK = 0x3f3f3f3fu;
const u32 FULL = 0xffffffffu;
int q;
u32 andv[(MAXN+10)<<2], orv[(MAXN+10)<<2], setv[(MAXN+10)<<2];

struct FastIO {
    char bufin[1<<27], bufout[1<<24];
    char *pin, *pout;
    FastIO() {
        fseek(stdin, 0, SEEK_END);
        int len = ftell(stdin);
        fseek(stdin, 0, SEEK_SET);
        fread(bufin, sizeof(char), len, stdin);
        pin = bufin; pout = bufout;
    }
    
    template<typename T>
    inline void readint(T& x) {
        T f=1, r=0;
        while(!isdigit(*pin)) { if(*pin=='-')f=-1; pin++; }
        while(isdigit(*pin)) { r=r*10+*pin-'0'; pin++; }
        x = f*r;
    }
    
    template<typename T>
    inline void writeint(T x) {
        static char t[25], *pt; pt = t;
        if(x<0) { *pout++ = '-'; x = -x; }
        do {
            *pt++ = x%10 + '0'; x /= 10;
        } while(x);
        pt--;
        while(pt>=t) *pout++ = *pt--;
        *pout++ = '\n';
    }
    
    ~FastIO() {
        fwrite(bufout, sizeof(char), pout - bufout, stdout);
    }
    
} fio;
#define readint fio.readint
#define writeint fio.writeint

#define lc(o) ((o)<<1)
#define rc(o) ((o)<<1|1)

inline void maintain(int o, int l, int r) {
    andv[o] = orv[o] = 0u;
    if(l != r) {
        andv[o] = andv[lc(o)] & andv[rc(o)];
        orv[o]  = orv[lc(o)]  | orv[rc(o)];
    }
    if(setv[o] != NONEMARK) {
        andv[o] = setv[o];
        orv[o] = setv[o];
    }
}

inline void pushdown(int o) {
    if(setv[o] != NONEMARK) {
        setv[lc(o)] = setv[o];
        setv[rc(o)] = setv[o];
        setv[o] = NONEMARK;
    }
}

u32 getval(int o, int l, int r, int p) {
    maintain(o, l, r);
    if(l == r) return andv[o];
    else {
        int mid = (l + r) / 2;
        pushdown(o);
        
        if(p <= mid) {
            maintain(rc(o), mid + 1, r);
            return getval(lc(o), l, mid, p);
        } else {
            maintain(lc(o), l, mid);
            return getval(rc(o), mid + 1, r, p);
        }
    }
}

void cover(int o, int l, int r, int ql, int qr, u32 val) {
    if(ql <= l && r <= qr)
        setv[o] = val;
    else {
        int mid = (l + r) / 2;
        pushdown(o);
        
        if(ql <= mid) cover(lc(o), l, mid, ql, qr, val);
        else maintain(lc(o), l, mid);
        
        if(qr >= mid + 1) cover(rc(o), mid + 1, r, ql, qr, val);
        else maintain(rc(o), mid + 1, r);
    }
    maintain(o, l, r);
}

// find the end pointer of consecutive 1's
int end1(int o, int l, int r, int ql) {
    maintain(o, l, r);
    
    if(ql <= l) {
        if(l == r) return andv[o] == FULL ? l : ql - 1;
        
        if(andv[o] == FULL) return r;
        else {
            int mid = (l + r) / 2, ret = ql - 1;
            
            pushdown(o);
            maintain(lc(o), l, mid), maintain(rc(o), mid + 1, r);
            
            if(andv[lc(o)] == FULL) {
                ret = max(ret, mid);
                ret = max(ret, end1(rc(o), mid + 1, r, ql));
            } else {
                ret = max(ret, end1(lc(o), l, mid, ql));
            }
            return ret;
        }
    } else {
        int mid = (l + r) / 2, ret = ql - 1;
        pushdown(o);
        
        if(ql <= mid) ret = max(ret, end1(lc(o), l, mid, ql));
        else maintain(lc(o), l, mid);
        
        if(ql > mid || ret == mid)
            ret = max(ret, end1(rc(o), mid + 1, r, ql));
        else maintain(rc(o), mid + 1, r);
        
        return ret;
    }
}

// 0's
int end0(int o, int l, int r, int ql) {
    maintain(o, l, r);
    
    if(ql <= l) {
        if(l == r) return orv[o] == 0u ? l : ql - 1;
        
        if(orv[o] == 0u) return r;
        else {
            int mid = (l + r) / 2, ret = ql - 1;
            
            pushdown(o);
            maintain(lc(o), l, mid), maintain(rc(o), mid+1, r);
            
            if(orv[lc(o)] == 0u) {
                ret = max(ret, mid);
                ret = max(ret, end0(rc(o), mid + 1, r, ql));
            } else {
                ret = max(ret, end0(lc(o), l, mid, ql));
            }
            return ret;
        }
    } else {
        int mid = (l + r) / 2, ret = ql - 1;
        pushdown(o);
        
        if(ql <= mid) ret = max(ret, end0(lc(o), l, mid, ql));
        else maintain(lc(o), l, mid);
        
        if(ql > mid || ret == mid) 
            ret = max(ret, end0(rc(o), mid + 1, r, ql));
        else maintain(rc(o), mid + 1, r);
        
        return ret;
    }
}

#undef lc
#undef rc

inline int get_bucket(int p) {
    return (p >> 5) + 1;
}

inline int get_bit(int p) { // shl
    return (p & 31);
}

inline void do_add(int x, int p) {
    // consider compressing into a byte
    // 01234567 01234567
    // 00001001 11001000
    //	   +100 00101
    register int bucket = get_bucket(p), bit = get_bit(p);
    register i128 cur; register u64 low, high;
    
    low = getval(1, 1, MAXN, bucket);
    high = getval(1, 1, MAXN, bucket+1);
    cur = low | (high << 32);
    cur += i128(x) << bit;
    
    cover(1, 1, MAXN, bucket, bucket, cur & FULL);
    cover(1, 1, MAXN, bucket+1, bucket+1, (cur >> 32) & FULL);
    
    if(cur > ULLONG_MAX) { // overflow
        int ql = bucket + 2, qr;
        qr = end1(1, 1, MAXN, ql);
        
        if(ql <= qr) cover(1, 1, MAXN, ql, qr, 0);
        u32 t = getval(1, 1, MAXN, qr + 1);
        
        register int i;
        for(i = 0; ((t >> i) & 1) && i < 32; i++);
        for(; ~i; --i) t ^= (1 << i);
        
        cover(1, 1, MAXN, qr + 1, qr + 1, t);
    } else if(cur < 0) { // underflow
        int ql = bucket + 2, qr;
        qr = end0(1, 1, MAXN, ql);
        
        if(ql <= qr) cover(1, 1, MAXN, ql, qr, FULL);
        u32 t = getval(1, 1, MAXN, qr + 1);
        
        register int i;
        for(i = 0; (not ((t >> i) & 1)) && i < 32; i++);
        for(; ~i; --i) t ^= (1 << i);
        
        cover(1, 1, MAXN, qr + 1, qr + 1, t);
    }
}

inline int query_bit(int p) {
    int bucket = get_bucket(p), bit = get_bit(p);
    return (getval(1, 1, MAXN, bucket) >> bit) & 1;
}

int main() {
    int t;
    memset(setv, 0x3f, sizeof(setv));
    
    readint(q);
    for(int i = 1; i <= 3; i++)
        readint(t);
    while(q--) {
        int op, a, b;
        readint(op);
        switch(op) {
            case 1:
                readint(a); readint(b);
                do_add(a, b);
                break;
            case 2:
                readint(a);
                writeint(query_bit(a));
                break;
        } 
    }
    return 0;
}

评测结果