Rockdu's Blog

【题目背景】
在人类智慧的山巅，有着一台字长为 1048576 位的超级计算机，著名理论计算机科
学家 P 博士正用它进行各种研究。不幸的是，这天台风切断了电力系统，超级计算机
无法工作，而 P 博士明天就要交实验结果了，只好求助于学过 OI 的你. . . . . .
【题目描述】
P 博士将他的计算任务抽象为对一个整数的操作。
具体来说，有一个整数 x ，一开始为 0。
接下来有 n 个操作，每个操作都是以下两种类型中的一种：
1 a b ：将 x 加上整数 a · 2
b，其中 a 为一个整数，b 为一个非负整数
2 k ：询问 x 在用二进制表示时，位权为 2
k 的位的值（即这一位上的 1 代表 2
k ）
保证在任何时候，x ≥ 0。
【输入格式】
从文件 integer.in 中读入数据。
输入的第一行包含四个正整数 n, t1, t2, t3，n 的含义见题目描述，t1, t2, t3 的具体含义
见子任务。
接下来 n 行，每行给出一个操作，具体格式和含义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
【输出格式】
输出到文件 integer.out 中。
对于每个询问操作，输出一行，表示该询问的答案（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
【样例 1 解释】
样例中有 10 个操作：第 1 个为将 x 加上 100 × 2
0 ，操作后，x = 100 ；
第 2 个为将 x 加上 2333 × 2
0 ，操作后，x = 2433 ；
第 3 个为将 x 加上 ?233 × 2
0 ，操作后，x = 2200 ；
第 4 个为询问 x 位权为 2
5 的位上的值，x 在二进制下为 100010011000 ，答案为 0 ；
第 5 个为询问 x 位权为 2
7 的位上的值，x 在二进制下为 100010011000 ，答案为 1 ；
第 6 个为询问 x 位权为 2
15 的位上的值，x 在二进制下为 100010011000 ，答案为
0 ；
第 7 个为将 x 加上 5 × 2
15 = 163840 ，操作后，x = 166040 ；
第 8 个为询问 x 位权为 2
15 的位上的值，x 在二进制下为 101000100010011000 ，答
案为 1 ；
第 9 个为将 x 加上 ?1 × 2
12 = ?4096 ，操作后，x = 161944 ；
第 10 个为询问 x 位权为 2
15 的位上的值，x 在二进制下为 100111100010011000 ，
答案为 0 。

首先把a*b拆分成log次单加操作。然后考虑对于一个位上的单加操作。如果不进位可以直接加，进位实际上是找到一串连续的1后的第一个0，并且把这一串1都变成0，将最后一个0变成1。可以用线段树优化。在线段树上维护两个bits信息，一个是否全0，一个是否全1。注意到这两个信息可以用位运算向上更新。复杂度O(n log^2 n)但是这样做对于100%的数据是会TLE的。发现线段树每一个节点只有0或1太浪费了。考虑状态压缩01串到一个32位整型中。这样复杂度是O(n log^2 n / 32)，可以过了。

P.S.洛谷上被卡常了555……

#include<cstdio>
#include<cctype>
using namespace std;
const int block = 30;
const int maxn = 1e6 + 150, stmax = (1LL << block) - 1;
int n, a, b, N, opt, t1, t2, t3, f = 0;
 
inline char gc(){
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
    x = 0, f = 0;static char c = gc();
    while(!isdigit(c)) {
        if(c == '-') f = 1;
        c = gc();
    }
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
    if(f) x = -x;
}
namespace Segtree {
    struct node {int bits[2], edt;node() {edt = -1;}}tree[maxn << 2];
    void push_up(int rt) {
        tree[rt].bits[0] = tree[rt << 1].bits[0] | tree[rt << 1 | 1].bits[0];
        tree[rt].bits[1] = tree[rt << 1].bits[1] & tree[rt << 1 | 1].bits[1];
    }
    void push_down(int rt) {
        if(~tree[rt].edt) {
            tree[rt << 1].edt = tree[rt << 1].bits[0] = tree[rt << 1].bits[1] = tree[rt].edt;
            tree[rt << 1 | 1].edt = tree[rt << 1 | 1].bits[0] = tree[rt << 1 | 1].bits[1] = tree[rt].edt;
            tree[rt].edt = -1;
        }
    }
    int qNful(int p, int tl, int tr, int rt, int t, int des) {
        if(tree[rt].bits[t] == des) return -1;
        if(tl == tr) return tl;
        push_down(rt);
        int mid = tl + tr >> 1;
        if(p < mid) {
            int ret = qNful(p, tl, mid, rt << 1, t, des);
            return (~ret) ? ret : qNful(p, mid + 1, tr, rt << 1 | 1, t, des);
        }
        return qNful(p, mid + 1, tr, rt << 1 | 1, t, des);
    }
    void edit(int l, int r, int tl, int tr, int rt, int msk) {
        if(tl == l && tr == r) {
            tree[rt].edt = tree[rt].bits[0] = tree[rt].bits[1] = msk;
            return ;
        }
        push_down(rt);
        int mid = tl + tr >> 1;
        if(r <= mid) edit(l, r, tl, mid, rt << 1, msk);
        else if(l > mid) edit(l, r, mid + 1, tr, rt << 1 | 1, msk);
        else {
            edit(l, mid, tl, mid, rt << 1, msk);
            edit(mid + 1, r, mid + 1, tr, rt << 1 | 1, msk);
        }
        push_up(rt);
    }
    void add(int p, int tl, int tr, int rt, int dt) {
        if(tl == tr) {
            tree[rt].bits[0] = (tree[rt].bits[1] += dt);
            return ;
        }
        push_down(rt);
        int mid = tl + tr >> 1;
        if(p <= mid) add(p, tl, mid, rt << 1, dt);
        else add(p, mid + 1, tr, rt << 1 | 1, dt);
        push_up(rt);
    }
    int query(int p, int tl, int tr, int rt) {
        if(tl == tr) return tree[rt].bits[0];
        push_down(rt);
        int mid = tl + tr >> 1;
        if(p <= mid) return query(p, tl, mid, rt << 1);
        else return query(p, mid + 1, tr, rt << 1 | 1);
    }
    void plus(int p, int msk) {
        int now = query(p, 0, N, 1);
        if(now + msk <= stmax) add(p, 0, N, 1, msk);
        else {
            add(p, 0, N, 1, -(stmax - msk + 1)); // 减去前面的连续1 
            now = qNful(p, 0, N, 1, 1, stmax);
            if(p + 1 < now)edit(p + 1, now - 1, 0, N, 1, 0);
            add(now, 0, N, 1, 1);
        }
    }
    void minus(int p, int msk) {
        int now = query(p, 0, N, 1);
        if(now - msk >= 0) add(p, 0, N, 1, -msk);
        else {
            add(p, 0, N, 1, (stmax - msk + 1)); // 加上前面的连续1
            now = qNful(p, 0, N, 1, 0, 0);
            if(p + 1 < now)edit(p + 1, now - 1, 0, N, 1, stmax);
            add(now, 0, N, 1, -1);
        }
    }
}
inline void opr(int a, int b) {
    using namespace Segtree;
    if(!a) return ;
    int type = a > 0, pw = 0;
    if(!type) a = -a;
    while(a) {
        if(a & 1)
            if(type) plus((pw + b) / block, 1 << ((pw + b) % block));
            else minus((pw + b) / block, 1 << ((pw + b) % block));
        a >>= 1, ++pw;
    }
}
int main() {
    using namespace Segtree;
    scanf("%d%d%d%d", &n, &t1, &t2, &t3), N = 1e6 + 100;
    while(n--) {
        read(opt), read(a);
        if(opt == 1) {
            read(b);
            opr(a, b);
        } else {
            putchar((query(a / block, 0, N, 1) & (1 << (a % block))) ? '1' : '0');
            putchar('\n');
        }
    }
    return 0;
}