题解 P6587 【超超的序列 加强】

· · 题解

【0/1 Trie】【P6587】 超超的序列

Analysis

把下标看作一堆二进制串，建立一颗 01 Trie，在叶结点处维护以当前二进制串（以根节点到孩子的边为最低位，连接叶节点的边为最高位）的为下标的序列值，非叶节点维护子树和。不难发现对于一个在第 m 层（根为第 0 层），代表 x 的节点，其信息就是所有对 2^m 取模后值为 x 的下标对应的序列值之和。查询时直接查询子树和，修改时在 Trie 上打标记即可。

啥，你说这和官方题解的 std 没啥区别？因为 01 Trie 和线段树本质上是相同的，显而易见这里把这个结构描述成 01 Trie 更加的自然。

Code

namespace Fusu {

const int maxn = 2100005;

int n, m;
int a[maxn];

struct Node {
  int sz;
  ll sum, tag;
  Node *trans[2];

  inline void maketag(const ll x) {
    sum += sz * x;
    tag += x;
  }
  inline void pushup() {
    sum = 0;
    for (auto u : trans) if (u) {
      sum += u->sum;
    }
  }
  inline void pushdown() {
    if (tag) {
      for (auto u : trans) if (u) u->maketag(tag);
      tag = 0;
    }
  }
};
Node Mem[maxn << 1], *pool = Mem;
Node *New(const int p, const int d) {
  int t = 1 << d;
  auto x = pool++;
  if (d == 21) {
    if (p <= n) {
      x->sum = a[p];
      if (p != 0) x->sz = 1;
    }
    return x;
  }
  x->trans[0] = New(p, d + 1);
  x->trans[1] = New(p | t, d + 1);
  x->pushup();
  x->sz = x->trans[0]->sz + x->trans[1]->sz;
  return x;
}

Node *stk[maxn];
int top = 0;
void Main() {
  qr(n); qr(m);
  qra(a + 1, n);
  auto rot = New(0, 0);
  for (ll op, x, y, z, ans = 0; m; --m) {
    qr(op);
    op = (op + ans) % 2 + 1;
    qr(x); qr(y);
    y &= (1 << x) - 1;
    if (op == 1) {
      qr(z);
      auto u = rot;
      for (int i = 0, t = 1 << i; i < x; t = 1 << ++i) {
        stk[++top] = u;
        int k = (y & t) ? 1 : 0;
        u->pushdown();
        u = u->trans[k];
      }
      u->maketag(z);
      while (top) stk[top--]->pushup();
    } else {
      auto u = rot;
      for (int i = 0, t = 1 << i; i < x; t = 1 << ++i) {
        int k = (y & t) ? 1 : 0;
        u->pushdown();
        u = u->trans[k];
      }
      qw(ans = u->sum, '\n');
    }
  }
}

} // namespace Fusu