BZOJ4942 [NOI2017] 整数

2018 年 03 月 19 日发布.

Description

你要维护一个二进制数 $x$ ，有 $n$ 个操作：

初始时 $x = 0$ 。

$n \leqslant 10^6, |a| \leqslant 10^9, b, k \leqslant 3 \times 10^7$

Solution

先考虑只有 $a > 0$ 的时候怎么做。

考虑暴力：把 $a$ 的每一位拆开加；每次要在第 $i$ 位上加的时候不停往前进位直到进不上去为止。

分析一下复杂度：

每次加的时候会把某一些二进制位从 1 变成 0 ，但是只有一个二进制位从 0 变成 1 。从 0 变成 1 的位至多有 $O(n\log a)$ 个，它们一共也只会花 $O(n\log a)$ 的时间变回 0 。所以总时间复杂度就是 $O(n\log a)$ 的。

考虑到 bool 比较低效，我们可以压位 ($32$ 位压一个 unsigned int) ，那么 $a$ 就可以拆成两个加上去。

再考虑如何处理减法。

如果我以上述方式维护 $x = x_0 - x_1$ ，其中 $x_0, x_1$ 分别是只考虑加和只考虑减（取绝对值）的值，那么查询时相当于查询 $x_0 - x_1$ 的第 $k$ 位的值。

考虑 $x_0$ 的后 $k$ 位 ($0$ 到 $k-1$ 位) 与 $x_1$ 的后 $k$ 位的大小关系。如果前者比较小那么在第 $k$ 位上需要退位；否则不需要。比较方式是找到后 $k$ 位中的两个数不同的最高位比较。

那么我们只需要开一个 set 维护“两个数不同的位置”，那么“后 $k$ 位中两个数不同的最高位”就相当于一个 lower\_bound 。

时间复杂度 $O(n\log n)$ （因为至多改变 $O(n)$ 位，所以 set 的大小也是 $O(n)$ 的）。

空间复杂度 $O(n + b)$ 。

目前在 LOJ 和 Luogu 榜首， BZOJ 第三。

Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <set>
const int L = 10000000;
char buf[L], *p = buf, *end = buf;
inline int getChar() {
  if (p == buf && feof(stdin)) return EOF;
  if (p == end) end = buf + fread(p = buf, sizeof(char), L, stdin);
  return *(p++);
}
inline int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getChar()) && c != '-');
  if (c == '-') f = -1, c = getChar();
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getChar()));
  return ans * f;
}
const int N = 4002000;
const int B = 1000500;
typedef unsigned int U;
typedef unsigned long long ULL;
U v[2][N];
std::set<int> S;
void modify(int x) {
  bool y = S.count(x);
  if (v[0][x] == v[1][x] && y) S.erase(x);
  else if (v[0][x] != v[1][x] && !y) S.insert(x);
}
int queryS(int x) {
  std::set<int>::iterator it = S.lower_bound(x);
  if (it == S.begin()) return 0;
  x = *(--it);
  return v[1][x] > v[0][x] ? -1 : 1;
}
inline bool check(U a, U b) { return (ULL)a + (ULL)b >= (1ULL << 32); }
void add(int x, int b) {
  int f = x < 0; x = f ? -x : x;
  int b1 = b >> 5, b2 = b & 31;
  U x1 = (U)x << b2;
  U t = check(v[f][b1], x1);
  U x2 = ((U)(x >> (31 - b2)) / 2) + t;
  v[f][b1] += x1;
  modify(b1);
  t = check(v[f][++b1], x2);
  v[f][b1] += x2;
  modify(b1);
  while (t) {
    t = check(v[f][++b1], 1U);
    v[f][b1] += 1U;
    modify(b1);
  }
}
inline int query(int x) {
  int x1 = x >> 5, x2 = x & 31;
  return (((2ULL << 32) + v[0][x1] - v[1][x1] - (queryS(x1) < 0)) >> x2) & 1;
}
int main() {
  int n = readInt();
  readInt(); readInt(); readInt();
  while (n--)
    if (readInt() == 1) {
      int x = readInt();
      add(x, readInt());
    } else
      printf("%d\n", query(readInt()));
  return 0;
}