题意
在高精度二进制上,每次增加一个 $a\times 2^b$ 或者减一个 $a\times 2^b$ $(a\in[0,10^9],b\in[0,2^{3\times 10^7}])$ ,然后每次查询二进制第 $k$ 位是 $0$ 还是 $1$ 。
思路
这题做法非常多,这里仅介绍一种比较基础好想的压位+线段树做法。
我们考虑模拟一个二进制 01 序列。先不考虑 $a$ 是 $10^9$ 的情况,仅考虑 $a=1$ 的时候会怎么样。
- 加法的话,相当于是在二进制的第 $b$ 位上面先加 $1$ 。如果第 $b$ 位是 $0$ 的话就会变成 $1$ ;如果是 $1$ ,则需要找从 $b$ 开始的连续 $1$ 有多少,然后将他们都变成 $0$ 。再往后的一位 $0$ 变成 $1$ 。
- 减法的话类似加法,如果是 $1$ 就变成 $0$ ;反之就是连续的 $0$ 全变成 $1$ ,再往后的一位变成 $0$ 。
这样的话,直接把 $a\le 10^9$ 的情况直接按照二进制拆分,每一位这样做就行了。但是这样每次操作要做至多 $30$ 次操作,单次操作是 $O(\log(3\times 10^7))$ ,肯定是过不了的。
不难发现,如果线段树每一个位置只考虑一个二进制位太浪费了。我们索性做压位就完事了。由于 $a\le 10^9$ ,我们可以按照每 $30$ 个二进制位放在一个位置当中来做。每次在一个位置 $u$ 上加某值 $v$ 的话就变成了:
- 加法的话,先判断原有的 $a_u+v$ 是否大于等于 $2^{30}$ 。如果不满足则不进位,直接加。反之则要考虑进位,看他后面连续的 $2^{30}-1$ 段多长,这一段直接都赋值为 $0$ ,再往后一个位置加上 $1$ 即可。
- 减法的话,先判断原有的 $a_u-v$ 是否小于 $0$ 。如果不满足则不退位,直接减。反之则要考虑退位,看他后面连续的 $0$ 段多长,这一段直接都赋值为 $2^{30}-1$ ,再往后一个位置减去 $1$ 即可。
这样的话,我们每一个 $a\times 2^b$ 只需要拆成线段树上的至多两个位置即可(分别是在 $\frac{b}{30}$ 和 $\frac{b}{30}+1$)。然后计算这两个位置分别要操作哪个数,则看不对齐的位是多少,然后在 $a$ 上取对应位置,再做运算即可。
线段树的功能
接下来就看我们需要线段树的什么功能。
- 单点加法/减法
- 查询区间是否全 $0$ / 全 $2^{30}-1$
- 区间赋值为全 $0$ / 全 $2^{30}-1$
- 查询从某点开始的连续全 $0$ / 全 $2^{30}-1$ 段往右会伸长到什么程度
所以区间赋值 tag 是必要的,任何的区间赋值/单点查询/修改都需要 pushdown
。然后在维护是否全 $0$ / 全 $2^{30}-1$ 则维护区间或/区间与运算即可。
然后最后这个查找最长段,直接线段树上二分即可。流程如下 :
- 如果当前区间满足全 $0$ 或者全 $2^{30}-1$ ,直接返回右端点。如果不满足且已经是单点,则返回 $-1$ (表示这段查不到结果)。
- 如果查询点在当前区间右半段,直接递归查找右半段。
- 如果查询点在当前区间左半段,先递归查找左半段。如果左半段结果即为左半段的右端点,则说明还可以在右半段找,两段查找结果取最大值即为找到的最右值。
那么假设我们是在 $p$ 处操作,考虑从 $p+1$ 开始的进退位问题,假设查找结果是 $q$ 。如果 $q$ 是 $-1$ 则直接在 $p+1$ 进退位就行。反之,则是把 $[p+1,q]$ 区间赋值,然后在 $q+1$ 处理进退位。
如果查询的右半段有上限或者下限的话,则需要判断是否可以往两边找。以及注意底层返回结果要和上限取最小值,具体可见 CSP202112-4 的题解 。
分析的差不多了,然后就可以开始写了。时间复杂度 $O(n\log n)$ 。常数有点大,多写一点 inline
函数是可以优化运行时间的。但是在 AcWing 跑过还是要手动开 O2 优化才能过。
const int N = 1000010, mask = (1 << 30) - 1;
inline int lc(int u) { return (u << 1); }
inline int rc(int u) { return (u << 1) | 1; }
struct node // compress bigint a[i] -> 2^{i*30}\sim 2^{i*30+29} i\in[0,N]
{
int sum_and, sum_or;
int tag_set;
bool have_set;
} tr[(N + 10) << 2];
inline void pushup(int u)
{
tr[u].sum_and = tr[lc(u)].sum_and & tr[rc(u)].sum_and;
tr[u].sum_or = tr[lc(u)].sum_or | tr[rc(u)].sum_or;
}
inline void modify_set(int u, int val)
{
tr[u].sum_and = tr[u].sum_or = tr[u].tag_set = val;
tr[u].have_set = 1;
}
inline void pushdown(int u)
{
if (tr[u].have_set)
modify_set(lc(u), tr[u].tag_set), modify_set(rc(u), tr[u].tag_set), tr[u].tag_set = tr[u].have_set = 0;
}
inline void _add_single(int u, int pos, int L, int R, int val)
{
if (L == R)
{
tr[u].sum_and += val, tr[u].sum_or += val;
return;
}
pushdown(u);
int M = (L + R) >> 1;
(pos <= M) ? _add_single(lc(u), pos, L, M, val) : _add_single(rc(u), pos, M + 1, R, val);
pushup(u);
}
inline void add_single(int pos, int val) { _add_single(1, pos, 0, N, val); }
inline void _set(int u, int l, int r, int L, int R, int val)
{
if (l > R || r < L)
return;
if (l <= L && R <= r)
{
modify_set(u, val);
return;
}
pushdown(u);
int M = (L + R) >> 1;
_set(lc(u), l, r, L, M, val), _set(rc(u), l, r, M + 1, R, val);
pushup(u);
}
inline void set(int l, int r, int val) { _set(1, l, r, 0, N, val); }
inline int _query_single(int u, int pos, int L, int R)
{
if (L == R)
return tr[u].sum_and;
pushdown(u);
int M = (L + R) >> 1;
return (pos <= M) ? _query_single(lc(u), pos, L, M) : _query_single(rc(u), pos, M + 1, R);
}
inline int query_single(int pos) { return _query_single(1, pos, 0, N); }
// flag 1 : search mask, 0 : search 0
inline int _search_right(int u, int pos, int L, int R, bool flag)
{
bool judge = flag ? (tr[u].sum_and == mask) : (tr[u].sum_or == 0);
if (judge)
return R;
else if (L == R)
return -1;
pushdown(u);
int M = (L + R) >> 1, x = -1;
if (pos <= M)
{
x = _search_right(lc(u), pos, L, M, flag);
if (x == M)
x = std::max(x, _search_right(rc(u), pos, M + 1, R, flag));
}
else
x = _search_right(rc(u), pos, M + 1, R, flag);
return x;
}
inline int search_right(int pos, bool flag) { return _search_right(1, pos, 0, N, flag); }
inline void add(int pos, int x)
{
int ori = query_single(pos);
if (ori + x <= mask)
add_single(pos, x); // a[pos] -> (a[pos] + x)
else
{
add_single(pos, x - mask - 1); // a[pos] -> (a[pos] + x - 2^30)
int q = search_right(pos + 1, 1);
(q != -1) ? (set(pos + 1, q, 0), add_single(q + 1, 1)) : add_single(pos + 1, 1);
}
}
inline void sub(int pos, int x)
{
int ori = query_single(pos);
if (ori - x >= 0)
add_single(pos, -x); // a[pos] -> (a[pos] - x)
else
{
add_single(pos, mask + 1 - x); // a[pos] = (a[pos] + 2^30 - x)
int q = search_right(pos + 1, 0);
(q != -1) ? (set(pos + 1, q, mask), add_single(q + 1, -1)) : add_single(pos + 1, -1);
}
}
inline void add_op(int a, int b) // + a * 2^b
{
int p = b / 30, off = b % 30;
add(p, (a << off) & mask), add(p + 1, a >> (30 - off));
}
inline void sub_op(int a, int b) // - a * 2^b
{
int p = b / 30, off = b % 30;
sub(p, (a << off) & mask), sub(p + 1, a >> (30 - off));
}
inline bool query_op(int p) { return (query_single(p / 30) & (1 << (p % 30))) >> (p % 30); } // query 2^p
int main()
{
int n = rd(); rd(), rd(), rd();
int op = 0, a = 0;
while (n--)
{
op = rd(), a = rd();
if (op & 1)
(a >= 0) ? add_op(a, rd()) : sub_op(-a, rd());
else
putchar(query_op(a) ^ '0'), putchar('\n');
}
}