G. 零一奇迹

其实就是个模拟题,怎么过的人这么少啊?

首先可以将整数看成60位2进制数,然后一个位置至多被 个长度小于等于60的区间包含.

由此,一次更新顶多修改360个数,直接暴力枚举所有的区间修改就完事了.

初始化类似直接暴力.

一开始为了统计区间内的数的个数还写了平衡树,然后喜提TLE.

其实只需要考虑所给区间内的数的个数就行了,具体可以看代码.

AC代码

#include <bits/stdc++.h>
using namespace std;
#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5;

int n, q;
char s[N];

struct Counter {
  int64_t l, r;
  int cnt;
  void ins(int64_t v) {
    if (l <= v && v <= r) ++cnt;
  }
  void del(int64_t v) {
    if (l <= v && v <= r) --cnt;
  }
  int qry() { return cnt; }
} T;

void init() {
  for (int i = 1; i <= n; ++i) {
    if (s[i] == '0') continue;
    int64_t v = 0;
    int len = 0;
    for (int j = i; j <= n && len <= 60; ++j) {
      ++len;
      v = ((v << 1) | (s[j] == '1'));
      T.ins(v);
    }
  }
}
void add(int p) {
  int st = max(1, p - 60);
  for (int i = st; i <= p - 1; ++i) {
    if (s[i] == '0') continue;
    int64_t v = 0;
    int len = 0;
    for (int j = i; j <= p - 1 && len <= 60; ++j) {
      ++len;
      v = ((v << 1) | (s[j] == '1'));
    }
    int64_t u = 1;
    for (int j = p; j <= n && len <= 60; ++j) {
      ++len;
      v = ((v << 1) | (s[j] == '1'));
      T.del(v);
      T.ins(v + u);
      u <<= 1;
    }
  }
  int64_t u = 1, v = 0;
  int len = 0;
  for (int j = p; j <= n && len <= 60; ++j) {
    ++len;
    v = ((v << 1) | (s[j] == '1'));
    T.ins(v + u);
    u <<= 1;
  }
}
void del(int p) {
  int st = max(1, p - 60);
  for (int i = st; i <= p - 1; ++i) {
    if (s[i] == '0') continue;
    int64_t v = 0;
    int len = 0;
    for (int j = i; j <= p - 1 && len <= 60; ++j) {
      ++len;
      v = v << 1 | (s[j] == '1');
    }
    int64_t u = 1;
    for (int j = p; j <= n && len <= 60; ++j) {
      ++len;
      v = v << 1 | (s[j] == '1');
      T.del(v);
      T.ins(v - u);
      u <<= 1;
    }
  }
  int64_t u = 1, v = 0;
  int len = 0;
  for (int j = p; j <= n && len <= 60; ++j) {
    ++len;
    v = ((v << 1) | (s[j] == '1'));
    T.del(v);
    u <<= 1;
  }
}
void solve(int Case) {
  int64_t l, r;
  scanf("%d %lld %lld", &n, &l, &r);
  T.l = l;
  T.r = r;
  scanf("%s", s + 1);
  init();
  scanf("%d", &q);
  int x;
  for (int i = 1; i <= q; ++i) {
    scanf("%d", &x);
    if (s[x] == '0') {
      add(x);
      s[x] = '1';
    } else {
      del(x);
      s[x] = '0';
    }
    printf("%d\n", T.qry());
  }
}

int main() {
#ifdef BACKLIGHT
  freopen("a.in", "r", stdin);
#endif
  int T = 1;
  // scanf("%d", &T);
  for (int t = 1; t <= T; ++t) solve(t);
  return 0;
}