博主的 BiBi 时间
博主今天被踩爆了已经不想哔哔了。
Solution
所以,这题是个打表题?
有一个结论:
若 (n) 为奇数,则在 ([1,n]) 中有奇数个 (1) 的数字个数为 ((n+1)/2);若 (n) 为偶数,则 ([1,n-1]) 中有偶数个 (1) 的数字个数为 (n/2)。
其实这两个结论本质上是一样的。
我们只考虑 (x,y) 分别 (1) 的数量(两个 (0) 是没有未来的滑稽),那么只有 (1/0) 与 (1/1) 两种情况。那么显然只有最后一种情况有影响,而且影响恒为偶。
偶数是不会改变奇偶性的。这就意味着我们可以摆脱异或的限制,把数字分成奇偶两坨。(统计区间内有奇/偶数个 (1) 的数字个数)
这个东西可以用动态开点线段树维护,最后输出大区间内有奇/偶数个 (1) 的数字个数之积。
每次插入最多增加 (log)(区间长度) 个点,空间复杂度 (S(n*32))。(把数组开小了也过了主要是数据水)
Code
#include <cstdio>
typedef long long ll;
const int N = 1e5 + 5;
const ll inf = (1ll << 32) - 1;
int n, l, r, root, odd[N * 20], even[N * 20], cnt, lson[N * 20], rson[N * 20];
bool mark[N * 20];
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
return x * f;
}
int get(const int x) {
if(x & 1) return x + 1 >> 1;
else return (x >> 1) + (__builtin_popcount(x) & 1);
}
void pushUp(const int o) {
odd[o] = odd[lson[o]] + odd[rson[o]];
even[o] = even[lson[o]] + even[rson[o]];
}
void add(const int o, const ll l, const ll r) {
odd[o] = get(r) - get(l - 1);
even[o] = r - l + 1 - odd[o];
}
void update(int &o, const ll l, const ll r, const ll L, const ll R) {
if(l > R || r < L) return;
if(mark[o]) return;
if(! o) o = ++ cnt;
if(l >= L && r <= R) {mark[o] = 1; add(o, l, r); return;}
int mid = l + r >> 1;
update(lson[o], l, mid, L, R); update(rson[o], mid + 1, r, L, R);
pushUp(o);
}
int main() {
n = read();
for(int i = 1; i <= n; ++ i) {
l = read(), r = read();
root = 0;
if(i > 1) root = 1;
update(root, 1, inf, l, r);
printf("%lld
", 1ll * odd[1] * even[1]);
}
return 0;
}