题目描述
在人类智慧的山巅,有着一台字长为$1048576$位的超级计算机,著名理论计算机科学家 P 博士正用它进行各种研究。 不幸的是,这天台风切断了电力系统,超级计算机无法工作,而 P 博士明天就要交实验结果了,只好求助于学过 OI 的你……
P 博士将他的计算任务抽象为对一个整数的操作。
具体来说,有一个整数$x$,一开始为$0$。
接下来有$n$个操作,每个操作都是以下两种类型中的一种:
- 1$a$$b$:将$x$加上整数$a \cdot 2 ^ b$。其中 aa 为一个整数,bb 为一个非负整数
- 2$k$:询问$x$在用二进制表示时,位权为$2 ^ k$的位的值(即这一位上的$1$代表$2 ^ k$)
保证在任何时候,$x \ge 0$。
输入格式
从标准输入读入数据。
输入的第一行包含四个正整数$n, t_1, t_2, t_3$,nn 的含义见题目描述,$t_1, t_2, t_3$的具体含义见子任务。
接下来$n$行,每行给出一个操作,具体格式和含义见题目描述。
同一行输入的相邻两个元素之间,用恰好一个空格隔开。
输出格式
输出所询问的值。
题解
这波是暴力爆踩标程 用线段树的确太麻烦了
首先,如果暴力维护每个二进制位上的值,就算不考虑进位退位,$\log_2 1e9=30$,时间复杂度是$O(30n)$的,已经不太能卡过去了
发现都是0/1的二进制位,所以我们可以用unsigned int
来压位,把32位压进一个uint
块,这样$2^k$那一位就在第$k/32$块的第$k%32$位上,每次修改只需要修改两个uint
,似乎就是$O(n)$的了
但是进位退位怎么办呢?
如果只有加法,没有减法的话,每次像高精加法一样暴力向上进位,可以证明时间复杂度是均摊$O(n)$的,但是有了减法,时间复杂度就保证不了了
所以我们把加法和减法分开计算,一个uint
数组维护累加的值,另一个数组维护累减的值,然后暴力进行高精加法
这里提一下怎么判断有没有进位:因为uint
会自然溢出,而且每次加在一块上的数肯定是小于$2^{32}$的,所以如果加完一个数发现uint
比原来还小了,就说明向上一位进了一
设$a_i$表示加数二进制$2^i$那位的值,$b_i$表示减数
最后考虑统计答案:
用$a_k$减去$b_k$就好了?然而并不是
$k$以下的二进制位相减可能会产生借位,如果有借位显然答案应该是$a_k-b_k$再取反,所以我们需要判断是否有借位
判断借位其实也很简单,假设一共加了$sum$这么多,减了$sub$这么多,只需要比较$sum%2^k$和$sub%2^k$哪个更大就行了
假设$k/32=p,\ k%32=q$,即$k$在第$p$块的第$q$位
把加数和减数 第$p$块的$0\sim q-1$位的和分别算出来,如果加数的大于减数的就肯定没有借位了,反之则有,但是如果相等的话我们就还要继续向后比较
不可能直接一位一位向后枚举,不过我们可以直接找到第一个$i<k$的$a_i\neq b_i$比较它们的大小
这个也很好实现,维护一个set
动态记录哪些块满足 加数块不等于减数块,每次修改时顺便维护一下,然后查询时直接lower_bound
就好了
然后此题就做完了。。。可能写得有点艰涩难懂但是实际上这个乱搞做法是很容易理解的
时间复杂度$O(n\log n)$,不过set
似乎跑得挺快
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include <bits/stdc++.h> #define re register using namespace std; typedef unsigned int uint;
template<typename T> inline void read(T &num) { T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
set<uint> st; uint n, t1, t2, t3; uint a[1000005], b[1000005];
void add(uint pos, uint x) { if (a[pos] + x < a[pos]) add(pos+1, 1); a[pos] += x; if (a[pos] != b[pos]) st.insert(pos); else if (st.count(pos)) st.erase(pos); }
void del(uint pos, uint x) { if (b[pos] + x < b[pos]) del(pos+1, 1); b[pos] += x; if (a[pos] != b[pos]) st.insert(pos); else if (st.count(pos)) st.erase(pos); }
int main() { read(n); read(t1); read(t2); read(t3); for (uint i = 1; i <= n; i++) { uint tp; read(tp); if (tp == 1) { int x, y; read(x); read(y); uint p = y / 32, q = y % 32; if (x > 0) { add(p, x<<q); if (q) add(p+1, x>>(32-q)); } else { x = -x; del(p, x<<q); if (q) del(p+1, x>>(32-q)); } } else { uint k; read(k); uint p = k / 32, q = k % 32; uint now = ((a[p] >> q) ^ (b[p] >> q)) & 1; uint x2 = a[p] % (1 << q), y2 = b[p] % (1 << q); if (x2 < y2) { putchar((now^1)+'0'); } else if (x2 > y2 || st.empty() || p <= *(st.begin())) { putchar(now+'0'); } else { set<uint>::iterator it = st.lower_bound(p); it--; uint pp = *it; if (a[pp] >= b[pp]) { putchar(now+'0'); } else { putchar((now^1)+'0'); } } puts(""); } } return 0; }
|