D [yLOI2019] 珍珠

· · 题解

D [yLOI2019] 珍珠

Background

别叹息太多告别，至少相遇很真切。

摇曳着盛放枯竭，时间从未停歇。

天涯浪迹的白雪，念念不忘山川蝴蝶。

听说有人孤负黑夜，偏要点亮人间的月。

——银临《珍珠》

Description

给定一个 deque，要求支持 push_back 和 push_front 操作，并且查询前缀与非和以及后缀与非和。

deque中只会有 0 或 1，一共有 n 次操作，其中有 m 次操作给定，剩下的操作随机。

Limitations

Solution

这是一道通过输入格式来防AK的题目

下面的做法只考虑前缀与非和，因为后缀的做法与前缀完全相同。

子任务 0：

没有操作，输出四个 0 即可。期望得分 5~pts

子任务 1：

暴力模拟，每次从前面插入的时候后面的元素暴力移位，暴力查询与非和即可。时间复杂度 O(n^2)，期望得分 15~pts

子任务 2：

考虑用线段树来维护每个区间的与非和，但是这样产生了一个问题，两个区间的与非和是无法合并的，因为与非运算没有交换律和结合律。

但是我们注意到事实上对于某个区间，序列的首部到区间左端点之前所有元素的与非和只可能是 0 或 1，因此线段树每个节点维护两个信息：当该区间之前所有元素的与非和是 0 时与非上该区间的值，以及当该区间之前元素与非和是 1 时与非上该区间的值，然后即可 O(1) 转移。

时间复杂度 O(n \log n)，期望得分 15 ~pts

子任务 3：

插入的元素全部是 1。

考虑一堆连续 1 的前缀与非和序列，一定形如 101010101\dots

证明上，考虑第一个位置一定是 1，然后 1~\text{nand}~1~=~0 ，0~\text{nand}~1~=~1，因此序列中 0 和 1 一定是循环出现的。

因此一个询问的答案一定是 y~\&~1。时间复杂度 O(n)，期望得分 10~pts

子任务 4：

插入的元素全部是 0。

考虑一堆 0 的前缀与非和序列，一定形如 011111111111 \dots

用与子任务 3 类似的办法即可解决。时间复杂度 O(n)，期望得分 10~pts

子任务 5：

考虑一个显而易见的事实，0 与非任何数都得 1。

因此考虑一次查询如果与非和的最后一项是 0，则直接返回 1 即可。

同时对于最后一项是 1 的操作，只需要看这一项向前一共有连续的几个 1，由于前面那一项是 0，所以一段 011111 的序列的与非和一定是 1010101010\dots，而与 0 前面的项完全无关。

当然需要特判查询的 0 是序列第一个元素，以及查询的 1 前面没有 0 的情况。

那么问题就变成了对于每个位置维护它前面第一个 0 的位置。

由于 m = 0 ，序列中的元素是完全随机的，因此连续 0/1 段的长度期望都是常数级的，因此暴力找即可，期望时间复杂度 O(n)，期望得分 15~pts

子任务 6：

考虑在序列不随机时怎么对每个数维护它前面第一个 0 的位置。

事实上，在每插入一个 0 时，都暴力修改这个 0 的有元素的一侧的连续 1 的信息即可。

例如，在序列左侧插入一个 0，则暴力修改 0 右侧连续 1 的左侧最近的 0 的位置为该位置即可。在序列右侧插入同理。

考虑时间复杂度：每个为 1 的元素都只会在左侧最近和右侧最近的 0 插入的时候被修改信息，因此每个元素都只会被修改 O(1) 次信息，即每次均摊修改 O(1) 个信息，总的修改次数为 O(n)，因此总时间复杂度 O(n)，期望得分 30~pts。

#include <cstdio>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif

typedef long long int ll;

namespace OPT {
  char buf[120];
}

template <typename T>
inline void qw(T x, const char aft, const bool pt) {
  if (x < 0) {x = -x, putchar('-');}
  int top=0;
  do {OPT::buf[++top] = static_cast<char>(x % 10 + '0');} while (x /= 10);
  while (top) putchar(OPT::buf[top--]);
  if (pt) putchar(aft);
}

namespace Maker {

typedef unsigned int uit;

bool __sp;
uit __x, __y, __z;
int __type, __k, __m;

const int L = 1 << 21;
char buf[L], *front=buf, *end=buf;
char GetChar() {
  if (front == end) {
    end = buf + fread(front = buf, 1, L, stdin);
    if (front == end) return -1;
  }
  return *(front++);
}

template <typename T>
inline void qr(T &x) {
  char ch = GetChar(), lst = ' ';
  while ((ch > '9') || (ch < '0')) lst = ch, ch = GetChar();
  while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = GetChar();
  if (lst == '-') x = -x;
}

template <typename T>
inline void Begin(const T &x) {
  __type = x % 10;
  qr(__x); qr(__y); qr(__z); qr(__m);
  __sp = (__type == 3) || (__type == 4); __type &= 1;
}

inline uit __Next_Integer() {
  __x ^= __y << (__z & 31);
  __y ^= __z >> (__x & 31);
  __z ^= __x << (__y & 31);
  __x ^= __x >> 5; __y ^= __y << 13; __z ^= __z >> 6;
  return __x;
}

inline uit Rand() { return __Next_Integer(); }

template <typename Tx, typename Ty, typename Tz>
inline void Get_Nextline(Tx &x, Ty &y, Tz &z) {
  if (__m) {
    --__m;
    x = 0; y = 0; z = 0;
    qr(x); qr(y); qr(z);
    if (x == 0) ++__k;
  } else {
    x = Rand() & 1; y = Rand() & 1;
    if (__k == 0) { x = 0; }
    if (x == 0) {
      ++__k;
      if (__sp) {
        z = __type;
      } else {
        z = Rand() & 1;
      }
    } else {
      int dk = __k >> 1;
      if (dk == 0) {
        z = 1;
      } else {
        z = Rand() % dk + dk;
      }
    }
  }
}

}

const int maxn = 10000009;

struct Ask {
  int x, y, z;

  inline void init() { Maker::Get_Nextline(x, y, z); ++x; ++y;}
};
Ask ask[maxn];

struct M {
  int v, lp, rp;
};
M MU[maxn];

int n, lpos = 1, ans, answ, answe, answer;

int main() {
  scanf("%d", &n);
  fprintf(stderr, "QAQIN\n") ;
  Maker::Begin(n);
  for (int i = 1; i <= n; ++i) {
    ask[i].init();
    if ((ask[i].x == 1) && (ask[i].y == 1)) ++lpos;
  }
  int rpos = lpos - 1;
  for (int i = 1; i <= n; ++i) {
    if (ask[i].x == 1) {
      if (ask[i].y == 1) {
        M &m = MU[--lpos];
        if ((m.v = ask[i].z) == 1) {
          m.rp = MU[lpos + 1].rp;
        } else {
          m.rp = m.lp = lpos;
          for (int j = lpos + 1; MU[j].v == 1; ++j) {
            MU[j].lp = lpos;
          }
        }
      } else {
        M &m = MU[++rpos];
        if ((m.v = ask[i].z) == 1) {
          m.lp = MU[rpos - 1].lp;
        } else {
          m.rp = m.lp = rpos;
          for (int j = rpos - 1; MU[j].v == 1; --j) {
            MU[j].rp = rpos;
          }
        }
      }
    } else {
      int _ans = 0;
      int p = ask[i].y == 1 ? lpos + ask[i].z - 1 : rpos - ask[i].z + 1;
      if (MU[p].v == 0) {
        _ans = ask[i].z != 1;
      } else {
        if (ask[i].y == 1) {
          int k = MU[p].lp;
          if (k == 0) {
            _ans = ask[i].z & 1;
          } else if (k == lpos) {
            _ans = (ask[i].z - 1) & 1;
          } else {
            _ans = (p - k + 1) & 1;
          }
        } else {
          int k = MU[p].rp;
          if (k == 0) {
            _ans = (ask[i].z) & 1;
          } else if (k == rpos) {
            _ans = (ask[i].z - 1) & 1;
          } else {
            _ans = (k - p + 1) & 1;
          }
        }
      }
      if (_ans) {
        ++ans;
        if (!(i & 1)) {
          ++answe;
        }
      } else {
        if (i & 1) {
          ++answ;
        }
        if (!(i & 1023)) {
          ++answer;
        }
      }
    }
  }
  printf("%d %d %d %d\n", ans, answ, answe, answer);
  return 0;
}

appreciation

感谢@Burnside 神仙帮助进行题解的校对工作