代码

#include<bits/stdc++.h>
#define ll long long
#define ui unsigned int
#define ull unsigned long long
using namespace std;
const int N = 1e6+7;
char gc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2) ? EOF : *p1++;
}
int qr()
{
    char ch = gc();
    int f = 1, sum = 0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = gc();
    }
    while(ch>='0'&&ch<='9')
    {
        sum = sum*10+ch-'0';
        ch = gc();
    }
    return sum*f;
}
set<int> s;
ui x[N], y[N];
void ADD(ull a, int b, ui* t, ui* an)
{
    int p = b/32, c = b%32;
    ull tmp = (ull)t[p]+(a<<c);
    a = tmp>>32;t[p] = (tmp&(((ull)1<<33)-1));
    if(t[p]^an[p])
    {
        s.insert(p);
    }
    else
    {
        s.erase(p);
    }
    for(int i = p+1; a; i++)
    {
        tmp = (ull)t[i]+a;
        a = (tmp)>>32;t[i] = (tmp&(((ull)1<<33)-1));
        if(t[i]^an[i])
        {
            s.insert(i);
        }
        else
        {
            s.erase(i);
        }
    }
    return;
}
bool query(int k)
{
    int p = k/32, c = k%32;
    ui ans = ((x[p]>>c)^(y[p]>>c))&1;
    ui a = (x[p]&((1<<c)-1)), b = (y[p]&((1<<c)-1));
    if(a<b)
    {
        return ans^1;
    }
    else if(a>b||s.empty()||p<=*s.begin())
    {
        return ans;
    }
    set<int>::iterator it = s.lower_bound(p);it--;
    if(x[*it]>y[*it])
    {
        return ans;
    }
    return ans^1;
}
int main()
{
    int n = qr(), t1 = qr(), t2 = qr(), t3 = qr();
    for(int i = 1; i <= n; i++)
    {
        int o = qr(), a, b, k;
        if(o&1)
        {
            a = qr();
            b = qr();
            if(a>0)
            {
                ADD(a, b, x, y);
            }
            else
            {
                ADD(-a, b, y, x);
            }
        }
        else
        {
            printf("%d\n", query(qr()));
        }
    }
    return 0;
}

评测结果