题目地址：洛谷：【P3822】[NOI2017]整数 – 洛谷、BZOJ：Problem 4942. — [Noi2017]整数

题目描述

P博士将他的计算任务抽象为对一个整数的操作。
具体来说，有一个整数x，一开始为0。
接下来有n个操作，每个操作都是以下两种类型中的一种：

• 1 a b：将x加上整数a \cdot 2^b，其中a为一个整数，b为一个非负整数
• 2 k：询问x在用二进制表示时，位权为2^k的位的值（即这一位上的1代表2^k）

保证在任何时候，x \geq 0。

输入输出格式

输入格式：
输入的第一行包含四个正整数n,t1,t2,t3，n的含义见题目描述，t1,t2,t3的具体含义见子任务。
接下来n行，每行给出一个操作，具体格式和含义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。

输出格式：
对于每个询问操作，输出一行，表示该询问的答案（0或1）。对于加法操作，没有任何输出。

输入输出样例

输入样例#1：

10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15

输出样例#1：

0
1
0
1
0

说明

n≤1000000

题解

参考资料：【bzoj4942】[Noi2017]整数 压位+线段树 – GXZlegend – 博客园
这是我省选结束后正经做的第一个近年NOI题目，下面内容会涉及到我的口胡部分分思路。
首先，我们发现其实如果|a|=1，进位是找到前面的第一个1或0，对于这之间的一整段0或1进行区间取反。于是我们可以预处理出前面的第一个1和0，用三个线段树分别维护当前数字、前面的第一个1和0的位置。单次修改O(\log n)，总复杂度O(n \log n)，可以通过|a|=1的部分分。
因为我们发现对于一段连续的0，它前面第一个0是该位置+1，前面第一个1是一个定值；对于一段连续的1也有类似性质。我们可以考虑用三个标记表示当前区间内的值都是该位置+1还是一个定值还是两种都有，这样就可以用线段树来维护我们要记录的信息啦。
实际上呢，我们也可以不存储这些信息，我们考虑直接用线段树查，线段树存储当前区间全0全1或者混合，然后怎么脑补一下查找方法就好了。
我们可以把a转换成二进制表示，对于每一位非0的进行如上操作，由于|a| \leq 10^9，操作的位数不会超过30位，因此我们的单次修改复杂度实际上是O(30 \log n)的，总复杂度是O(n \log n)，看似能过剩下的点了，但是实际上似乎需要卡一卡常数。
我们可以想到什么卡常的办法呢？对了，压位！线段树上每个点来维护一个位置的01取值常数大，那么我们一口气存它30位！那么对于合并区间信息怎么来做呢，我们考虑记子区间的或以及子区间的与。该位置的与值如果为30个1这种情况，说明区间内全1；该位置的或值如果为0，说明区间内全0。只需要魔改我们之前的那个线段树就可以了，改动其实并不大。
实现细节见代码中的注释。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005, INF = (1 << 30) - 1;

int n;

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
int valo[MAXN << 2], vala[MAXN << 2], tag[MAXN << 2]; // tag表示该区间内全部变为某个值

inline void pushdown(int o) {
    if(~tag[o]) {
        valo[lch] = vala[lch] = tag[lch] = tag[o];
        valo[rch] = vala[rch] = tag[rch] = tag[o];
        tag[o] = -1; // 以-1为无标记的标志，可能存在要求变为0的情况
    }
}

// 将区间全都修改为某个值
inline void modify(int o, int l, int r, int ll, int rr, int v) {
    if(l >= ll && r <= rr) {
        valo[o] = vala[o] = tag[o] = v;
        return;
    }
    pushdown(o);
    if(ll <= mid) modify(lch, l, mid, ll, rr, v);
    if(rr > mid) modify(rch, mid + 1, r, ll, rr, v);
    valo[o] = valo[lch] | valo[rch];
    vala[o] = vala[lch] & vala[rch];
}

// 单点加
inline void add(int o, int l, int r, int x, int v) {
    if(l == r) {
        valo[o] += v; vala[o] += v;
        return;
    }
    pushdown(o);
    if(x <= mid) add(lch, l, mid, x, v);
    else add(rch, mid + 1, r, x, v);
    valo[o] = valo[lch] | valo[rch];
    vala[o] = vala[lch] & vala[rch];
}

// 查询某一段
inline int query(int o, int l, int r, int x) {
    if(l == r) {
        return valo[o];
    }
    pushdown(o);
    if(x <= mid) return query(lch, l, mid, x);
    else return query(rch, mid + 1, r, x);
}

// 找到该段往前第一段非全1的位置，-1表示没找到
inline int queryinf(int o, int l, int r, int x) {
    if(vala[o] == INF) return -1;
    if(l == r) return l;
    pushdown(o);
    if(x <= mid) {
        int t = queryinf(lch, l, mid, x);
        return ~t ? t : queryinf(rch, mid + 1, r, x);
    } else {
        return queryinf(rch, mid + 1, r, x);
    }
}

// 找到该段往前第一段非全0的位置，-1表示没找到
inline int queryblk(int o, int l, int r, int x) {
    if(!valo[o]) return -1;
    if(l == r) return l;
    pushdown(o);
    if(x <= mid) {
        int t = queryblk(lch, l, mid, x);
        return ~t ? t : queryblk(rch, mid + 1, r, x);
    } else {
        return queryblk(rch, mid + 1, r, x);
    }
}

// 在x段加v
inline void add(int x, int v) {
    int t = query(1, 0, MAXN, x);
    if(t + v <= INF) {
        add(1, 0, MAXN, x, v);
    } else { // 处理进位
        add(1, 0, MAXN, x, v - INF - 1);
        int y = queryinf(1, 0, MAXN, x + 1);
        if(y != x + 1) modify(1, 0, MAXN, x + 1, y - 1, 0);
        add(1, 0, MAXN, y, 1);
    }
}

// 在x段减v
inline void minus(int x, int v) {
    int t = query(1, 0, MAXN, x);
    if(t - v >= 0) {
        add(1, 0, MAXN, x, -v);
    } else { // 处理进位
        add(1, 0, MAXN, x, INF + 1 - v);
        int y = queryblk(1, 0, MAXN, x + 1);
        if(y != x + 1) modify(1, 0, MAXN, x + 1, y - 1, INF);
        add(1, 0, MAXN, y, -1);
    }
}

int op, a, b;

int main() {
    n = readint(); readint(); readint(); readint();
    while(n--) {
        op = readint();
        if(op == 1) {
            a = readint(); b = readint();
            if(a > 0) {
                add(b / 30, (a << (b - b / 30 * 30)) & INF);
                add(b / 30 + 1, a >> (30 - (b - b / 30 * 30)));
            } else if(a < 0) {
                a *= -1;
                minus(b / 30, (a << (b - b / 30 * 30)) & INF);
                minus(b / 30 + 1, a >> (30 - (b - b / 30 * 30)));
            }
        } else {
            a = readint();
            printf("%d\n", query(1, 0, MAXN, a / 30) & (1 << (a - a / 30 * 30)) ? 1 : 0);
        }
    }
    return 0;
}