自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:11:40，当前版本为作者最后更新于2019-08-25 19:20:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

感谢

帮助进行题解的校对工作