Introduction to KMP

Background

在字符串理论中,经常要求一个字符串$T$在另一个字符串$S$中所有出现的位置。这个过程就是字符串匹配。我们称$S$为文本,$T$为模式。下面介绍一种时间复杂度为线性的算法KMP,可以解决此类问题。

Introduction

令$S_i$表示字符串$S$的第$i$个字符,$S_{i, j}$表示字符串$S$的第$i$到第$j$个字符构成的字符串。为了方便讲解,字符串下标从$1$开始。
在KMP中有一个重要的数组,我们称它为$nxt$。对于一个字符串$S$,$nxt_i=\max(x \mid x \lt i \land S_{1, x}=S_{i-x+1, i})$。特别的,令$nxt_1=0$。
考虑如何求出模式$T$的$nxt$数组。最暴力的暴力时间复杂度为$O(n^2)$,但这实际上浪费了很多有用的信息。其实可以从$nxt_{i-1}$推到$nxt_i$。
我们来形象化这个过程

    v
acbacabacbacb
           ^

假设我们已经求出$nxt_{12}=5, \; nxt_5=2$,当前两个指针分别指向$S_{12}$和$S_{nxt_{12}}=S_5$,求$nxt_{13}$。在这里,两个指向$S_p, S_q$的指针表示$S_{p-q+1, p}=S_{1, q}$。
比较两个指针的后一位。易知,若$S_{13}=S_6$,则$nxt_{13}=nxt_{12}+1=6$,可以将两个指针都向后移一位。
否则,我们已经知道$nxt_{12}=5$,即$S_{1, 5}=S_{8, 12}$,而$nxt_5=2$,即$S_{1, 2}=S_{4, 5}=S_{11, 12}$。这意味着我们可以把指向$S_{nxt_{12}}$的指针重新指向$S_{nxt_{nxt_{12}}}=S_2$,如下

 v
acbacbaacbacb
           ^

此时仍然满足$S_{12-2+1, 12}=S_{1, 2}$。再次比较两个指针的后一位,发现$S_{13}=S_3$,于是$nxt_{13}=nxt_{2}+1=3$,将两个指针向后移一位。当然,若$S_{13} \neq S_3$则需要将指向$S_{nxt_5}$的指针再指向$S_{nxt_{nxt_5}}$,重复上述过程,直到指针指向$S_0$,那么$nxt_{13}=0$。
代码并不复杂(该代码中的字符串下标从$0$开始)

void kmp(char c[], int len) {
  nxt[0] = -1;
  for (int i = 1; i < len; ++i) {
    for (nxt[i] = nxt[i - 1]; ~nxt[i] && c[nxt[i] + 1] != c[i];
         nxt[i] = nxt[nxt[i]])
      ;
    if (c[nxt[i] + 1] == c[i])
      ++nxt[i];
  }
}

在得到模式$T$的$nxt$数组后,我们就可以用类似的方法求出$T$在文本$S$中所有出现的位置了。思路也是维护两个指针,一个在$S$上,指向$S_p$,另一个在$T$上,指向$T_q$,同样要满足$S_{p-q+1, p}=T_{1, q}$。显然,当$q=|T|$时,就找到了一个出现的位置。

Application

KMP算法除了可以用于字符串匹配,还能求出一个循环串的最小循环节。循环串是由至少两个相同的字符串拼接起来得到的字符串。
具体来讲,设$i=|S|$,$nxt_i \gt 0 \land i-nxt_i \mid i \Rightarrow S_{1, i}$是循环串,它的最小循环节是$S_{1, i-nxt_i}$。
要证明以上结论,只需要证明:

  • 引理1 所有非循环串均不满足上述条件。
    证明 显然,在满足上述条件的情况下,$S$的确是循环串,$S_{1, i-nxt_i}$就是$S$的一个循环节。

  • 引理2 对于两个字符串$A, B$,若$AB=BA$,则$AB$是循环串,$A_{1, (|A|, |B|)}=B_{1, (|A|, |B|)}$是一个循环节。其中$(a, b)$表示$a, b$的最大公约数。
    证明 设$|A| \le |B|$,由$AB=BA$可知,$A=B_{1, |A|}=B_{|A|+1, 2|A|}=\cdots$,那么当$(|A|) \mid (|B|)$时,$A$是$B$的一个循环节(或$A=B$),因此$AB$是循环串。
    当$(|A|) \nmid (|B|)$时,令$k=\left\lfloor {|B| \over |A|} \right\rfloor$。
    考虑字符串$S=AB, \; T=S_{(k-1)|A|+1, |S|}$,可知$T_{1, |A|}=T_{|T|-|A|+1, |T|}=A, \; T_{1, |T|-|A|}=T_{|A|+1, |T|}=B_{(k-1)|A|+1, |B|}$。令$A’=B_{(k-1)|A|+1, |B|}, \; B’=A$,那么我们又得到了$A’B’=B’A’$的形式,此时$|A’|=|B| \bmod |A|, \; |B’|=|A|$。因此,最后一定能得到长为$(|A|, |B|)$的字符串,它是$A, B$的一个循环节,也是$AB$的一个循环节。

  • 引理3 若字符串$S$是循环串,则$S$的最小循环节是$S_{1, i-nxt_i}$。
    证明 令$x$为最小循环节的长度,只要证明不存在$y$满足$y \lt x$且$S_{1, i-y}=S_{y+1, i}$。
    假设存在这样的$y$,那么$S_{y+1, y+x}=S_{1, x}=S_{x+1, 2x}$。令$A=S_{y+1, x}, \; B=S_{x+1, y+x}$,可以发现$A$是$S_{1, x}$的后缀、$S_{y+1, y+x}$的前缀,$B$是$S_{x+1, 2x}$的前缀、$S_{y+1, y+x}$的后缀,即$S_{1, x}=AB=BA$,根据引理2,$S_{1, x}$是循环串,这与$x$是最小循环节的长度矛盾。因此这样的$y$不存在,而因为$S_{1, x}$是一个循环节,所以$S_{1, i-x}=S_{x+1, i}$,根据KMP的原理,$nxt_i=i-x$,即$S$的最小循环节是$S_{1, i-nxt_i}$。

由此命题得证。

Matching Names

题目描述

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the “Hobbit” movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.
There are $n$ students in a summer school. Teachers chose exactly $n$ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $b$ to a student with name $a$ as the length of the largest common prefix $a$ and $b$. We will represent such value as $LCP(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.
Find the matching between students and pseudonyms with the maximum quality.

题意概述

给定$2n$个字符串$s_i$,前$n$个为一组,后$n$个为一组。要求将它们建立匹配(不能匹配同一组的字符串),使得两两匹配的字符串的$LCP$的长度之和最大。求最大值及方案。
数据范围:$1 \le n \le 10^5, \; 1 \le \sum |s_i| \le 8 \times 10^5$。

算法分析

首先对所有串建立Trie树,并记录下每个节点是哪些串的前缀。
考虑贪心——在Trie树上DFS(后序遍历),若在一个节点上有未匹配的不同组的串,则直接将它们匹配。这样做的正确性是显而易见的:若它们在之后匹配或与其他串匹配,则一定没有直接匹配更优。
具体实现时可以用vector启发式合并来维护每个节点上的值。

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int N = 800005;
int numn = 1, tot;
char s[N];
struct Trie {
  int child[26];
  std :: vector <int> rec[2];
} node[N];
std :: vector <std :: pair <int, int> > ans;

void insert(char s[], int id, int val) {
  int len = strlen(s), root = 0;
  for (int i = 0; i < len; ++ i) {
    if (! node[root].child[s[i] - 'a']) node[root].child[s[i] - 'a'] = numn ++;
    root = node[root].child[s[i] - 'a'];
  }
  node[root].rec[val].push_back(id);
}

void merge(std :: vector <int> &a, std :: vector <int> &b) {
  if (a.size() < b.size()) swap(a, b);
  a.insert(a.end(), b.begin(), b.end());
}

void dfs(int t, int dep) {
  for (int i = 0; i < 26; ++ i)
    if (node[t].child[i]) {
      dfs(node[t].child[i], dep + 1);
      merge(node[t].rec[0], node[node[t].child[i]].rec[0]);
      merge(node[t].rec[1], node[node[t].child[i]].rec[1]);
    }
  while (! node[t].rec[0].empty() && ! node[t].rec[1].empty()) {
    tot += dep;
    ans.push_back(std :: make_pair(node[t].rec[0][node[t].rec[0].size() - 1], node[t].rec[1][node[t].rec[1].size() - 1]));
    node[t].rec[0].pop_back(), node[t].rec[1].pop_back();
  }
}

int main() {
  int n; scanf("%d", &n);
  for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 0);
  for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 1);
  dfs(0, 0);
  printf("%d\n", tot);
  for (int i = 0; i < n; ++ i) printf("%d %d\n", ans[i].first, ans[i].second);
  return 0;
}

DNA Sequence

题目描述

It’s well known that DNA Sequence is a sequence only contains A, C, T and G, and it’s very useful to analyze a segment of DNA Sequence,For example, if a animal’s DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don’t contain those segments.
Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G, and the length of sequences is a given integer $n$.

题意概述

给定$m$个长度不超过$10$的DNA片段,问所有长度为$n$的DNA序列中有几个不包含所有给定的DNA片段。
数据范围:$0 \le m \le 10, \; 1 \le n \le 2 \times 10^9$。

算法分析

对$m$个DNA片段建立AC自动机。令$f_{i, j}$表示长度为$i$的DNA序列在自动机上跑到节点$j$的方案数。转移可以用一个矩阵来表示,因此可以用矩阵快速幂来加速转移。

代码

#include <cstdio>
#include <cstring>

static const int N = 11;
static const int POOL = 105;
char s[N];

int get_id(char c) {
  return c == 'A' ? 0 : c == 'C' ? 1 : c == 'T' ? 2 : 3;
}

typedef int Array[POOL][POOL];

int numn = 1, que[POOL];
Array mp, a, tmp;
struct ACAutomaton {
  int nxt[4], fail;
  bool match;
} node[POOL];

void insert(char s[]) {
  int root = 1, len = strlen(s);
  for (int i = 0; i < len; ++ i) {
    int p = get_id(s[i]);
    if (! node[root].nxt[p]) node[root].nxt[p] = ++ numn;
    root = node[root].nxt[p];
  }
  node[root].match = true;
}

void build() {
  int qb = 0, qe = 1; que[0] = 1;
  while (qb < qe) {
    int u = que[qb ++];
    for (int i = 0; i < 4; ++ i)
      if (node[u].nxt[i]) {
        node[node[u].nxt[i]].fail = 1;
        if (u > 1) {
          int root = node[u].fail;
          while (root > 1 && ! node[root].nxt[i]) root = node[root].fail;
          if (node[root].nxt[i]) {
            node[node[u].nxt[i]].fail = node[root].nxt[i];
            if (node[node[root].nxt[i]].match) node[node[u].nxt[i]].match = true;
          }
        }
        que[qe ++] = node[u].nxt[i];
      }
  }
}

void mul(Array a, Array b) {
  memset(tmp, 0, sizeof tmp);
  for (int i = 1; i <= numn; ++ i)
    for (int j = 1; j <= numn; ++ j)
      if (a[i][j]) for (int k = 1; k <= numn; ++ k) (tmp[i][k] += 1ll * a[i][j] * b[j][k] % 100000) %= 100000;
  memcpy(a, tmp, sizeof tmp);
}

void power(Array a, int b) {
  while (b) {
    if (b & 1) mul(a, mp);
    mul(mp, mp), b >>= 1;
  }
}

int main() {
  int m, n; scanf("%d%d", &m, &n);
  for (int i = 0; i < m; ++ i) scanf(" %s", s), insert(s);
  build();
  for (int i = 1; i <= numn; ++ i) if (! node[i].match)
    for (int j = 0; j < 4; ++ j) {
      int root = i;
      while (root > 1 && ! node[root].nxt[j]) root = node[root].fail;
      if (node[root].nxt[j]) ++ mp[i][node[root].nxt[j]]; else ++ mp[i][root];
    }
  for (int i = 1; i <= numn; ++ i) a[i][i] = 1;
  power(a, n);
  int ans = 0;
  for (int i = 1; i <= numn; ++ i) if (! node[i].match) (ans += a[1][i]) %= 100000;
  printf("%d\n", ans);
  return 0;
}

Pishty and Tree

题目描述

A little boy Pishty lives in Khust – an ancient town in Uzhlyandia with their medieval castles and smart bears.
The gem of Khust is a very valuable castle because it protects the citizens of Uhzlyandia from the Durdom kingdom’s army. Pishty also like this castle because it hides old secrets in long halls and high towers…
The castle can be described as an undirected tree with $N$ vertices and $N-1$ edges. Each edge has a magic number $C$.
When a group of tourists visit the castle, they are interested in a path between vertices $U$ and $V$. They think that an edge is interesting if its magic number is less than or equal to $K$. The total attractivity of the path is the xor of all interesting edges on it.
The emperor of Uzhlyandia is interested in tourism development, and so he wants to find the total attractivity of the paths for each group. Because Pishty wants to become the emperor’s knight, he wants to know all of this information too. But he can’t do it on his own because there are a large number of groups. Please help Pishty to solve this unthinkable problem.
Given $M$ groups of tourists, find the total attractivity of the path for each group.

题意概述

给定一棵有$N$个节点的树,每条边都有一个权值$C$。有$M$组询问,每组询问给定$U, V$和$K$,求$U$到$V$路径上权值不超过$K$的边的权值的异或和。
数据范围:$1 \le N, M \le 10^5, \; 1 \le C, K \le 10^9$。

算法分析1

由于要求的是异或和,且$x \oplus y \oplus y=x$,因此可以分别求出$U, V$到根节点路径上权值不超过$K$的边的权值的异或和,将两个结果异或一下便得到了答案。
考虑采用树链剖分。定义重边为一个节点连向它最大子树的边,由重边构成的链称为重链;其他边均为轻边。令$size_x$表示以节点$x$为根的子树大小。对于一条轻边$(u, v)$,有$2size_v \lt size_u$。对于树中的任一节点,从根节点到它的路径上不超过$O(\log n)$条重链,不超过$O(\log n)$条轻边。在重链上用树状数组维护前缀和,即可在$O(\log^2n)$的时间内给出一组询问的答案。
因为有$K$这个限制,所以我们考虑离线做法:将边按$C$从小到大排序,将询问按$K$从小到大排序,在加入边的同时处理询问。

代码1

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
  long long u, v, c, nxt;
  bool operator < (const edge &a) const { return c < a.c; }
} e[200001], r[100001];
struct ask {
  long long u, v, k, id, ans;
  bool operator < (const ask &a) const { return k < a.k; }
} a[100001];
bool cmp(ask a, ask b) { return a.id < b.id; }
struct binary_indexed_tree {
  long long n;
  vector<long long> a;
  void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
  void add(long long p, long long t) {
    for (long long i = p; i < n; i += i & -i) a[i] ^= t;
  }
  long long sum(long long p) {
    long long ret = 0;
    for (long long i = p; i; i -= i & -i) ret ^= a[i];
    return ret;
  }
} tree[100001];
long long T, n, m, nume, tot, pnt, h[100001], size[100001];
long long up[100001], down[100001], father[100001], dist[100001];
long long id[100001], len[100001], cnt[100001];
void add_edge(long long u, long long v, long long c) {
  e[++nume].u = u, e[nume].v = v, e[nume].c = c;
  e[nume].nxt = h[u], h[u] = nume;
  e[++nume].u = v, e[nume].v = u, e[nume].c = c;
  e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa, long long depth) {
  long long ma = 0;
  size[t] = 1, father[t] = fa, dist[t] = depth;
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      dfs(e[i].v, t, e[i].c);
      ma = max(ma, size[e[i].v]);
      size[t] += size[e[i].v];
    }
  }
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa && ma == size[e[i].v]) { down[t] = e[i].v; break; }
  }
}
void init(long long t, long long fa, long long rt) {
  if (!up[t]) id[up[t] = t] = ++tot, ++cnt[t], len[t] = 1;
  else ++cnt[up[t] = rt], len[t] = len[fa] + 1;
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      if (!up[e[i].v]) init(e[i].v, t, e[i].v);
      else init(e[i].v, t, rt);
    }
  }
  if (t == up[t]) tree[id[t]].init(cnt[t]);
}
void insert_line(edge e) {
  if (up[e.u] == up[e.v] && len[e.u] < len[e.v]) {
    tree[id[up[e.u]]].add(len[e.u], e.c);
  }
}
long long query(long long u, long long k) {
  long long ret = 0;
  while (u != 1) {
    ret ^= tree[id[up[u]]].sum(len[u] - 1);
    u = up[u];
    if (u != 1) {
      if (dist[u] <= k) ret ^= dist[u];
      u = father[u];
    }
  }
  return ret;
}
int main()
{
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    nume = tot = 0, pnt = 1;
    memset(h, 0, sizeof(h));
    memset(up, 0, sizeof(up));
    memset(down, 0, sizeof(down));
    memset(cnt, 0, sizeof(cnt));
    for (long long i = 1; i < n; ++i) {
      r[i].nxt = 0;
      scanf("%lld%lld%lld", &r[i].u, &r[i].v, &r[i].c);
    }
    sort(r + 1, r + n);
    for (long long i = 1; i < n; ++i) add_edge(r[i].u, r[i].v, r[i].c);
    dfs(1, 0, 0);
    for (long long i = 1; i <= n; ++i) if (down[i]) up[down[i]] = i;
    init(1, 0, 1);
    scanf("%lld", &m);
    for (long long i = 1; i <= m; ++i) {
      a[i].id = i, a[i].ans = 0;
      scanf("%lld%lld%lld", &a[i].u, &a[i].v, &a[i].k);
    }
    sort(a + 1, a + m + 1);
    for (long long i = 1; i <= m; ++i) {
      while (pnt <= nume && e[pnt].c <= a[i].k) insert_line(e[pnt++]);
      a[i].ans = query(a[i].u, a[i].k) ^ query(a[i].v, a[i].k);
    }
    sort(a + 1, a + m + 1, cmp);
    for (long long i = 1; i <= m; ++i) printf("%lld\n", a[i].ans);
  }
  return 0;
}

算法分析2

由于要求的是异或和,因此可以对整棵树建可持久化Trie树,每次询问直接查询$U, V$到根节点的路径上边权不超过$K$的边的权值的异或和,将两结果异或起来。

代码2

#include <cstdio>
#include <cstring>
using namespace std;
struct node_type {
  long long val, child[2];
} node[4000001];
struct edge {
  long long v, c, nxt;
} e[200001];
long long T, n, m, tot, nume, h[100001], root[100001];
void add_edge(long long u, long long v, long long c) {
  e[++nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].nxt = h[v], h[v] = nume;
}
long long insert_node(long long root, long long val, long long depth) {
  if (depth < 0) {
    node[++tot].val = node[root].val ^ val, node[tot].child[0] = node[tot].child[1] = 0;
    return tot;
  }
  long long t = (val >> depth) & 1;
  long long ch = insert_node(node[root].child[t], val, depth - 1);
  node[++tot].child[t] = ch, node[tot].child[!t] = node[root].child[!t];
  node[tot].val = node[node[tot].child[t]].val ^ node[node[tot].child[!t]].val;
  return tot;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      root[e[i].v] = insert_node(root[t], e[i].c, 30);
      dfs(e[i].v, t);
    }
  }
}
long long get_dist(long long root, long long k, long long depth) {
  if (depth < 0) return node[root].val;
  long long t = (k >> depth) & 1;
  if (t) return node[node[root].child[0]].val ^ get_dist(node[root].child[1], k, depth - 1);
  else return get_dist(node[root].child[0], k, depth - 1);
}
int main()
{
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    nume = tot = 0;
    memset(h, 0, sizeof(h));
    for (int i = 1; i < n; ++i) {
      long long u, v, c;
      scanf("%lld%lld%lld", &u, &v, &c);
      add_edge(u, v, c);
    }
    root[1] = insert_node(0, 0, 30);
    dfs(1, 0);
    scanf("%lld", &m);
    for (int i = 1; i <= m; ++i) {
      long long u, v, k;
      scanf("%lld%lld%lld", &u, &v, &k);
      printf("%lld\n", get_dist(root[u], k, 30) ^ get_dist(root[v], k, 30));
    }
  }
  return 0;
}

Choosing the Commander

题目描述

As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.
Vova managed to build a large army, but forgot about the main person in the army – the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality – an integer number $p_i$. Each commander has two characteristics — his personality $p_j$ and leadership $l_j$ (both are integer numbers). Warrior $i$ respects commander $j$ only if $p_i \oplus p_j \lt l_j$ ($x \oplus y$ is the bitwise excluding OR of $x$ and $y$).
Initially Vova’s army is empty. There are three different types of events that can happen with the army:

  • 1 $p_i$ – one warrior with personality $p_i$ joins Vova’s army;
  • 2 $p_i$ – one warrior with personality $p_i$ leaves Vova’s army;
  • 3 $p_i$ $l_i$ – Vova tries to hire a commander with personality $p_i$ and leadership $l_i$.

For each event of the third type Vova wants to know how many warriors (counting only those who joined the army and haven’t left yet) respect the commander he tries to hire.

题意概述

有一个初始为空的数字集合。有三种操作:①向集合中加入一个数$p$;②从集合中删除一个数$p$;③询问集合中与$p$的异或值小于$l$的数的个数。总共进行了$q$次操作。
数据范围:$1 \le q \le 10^5, \; 1 \le p_i, l_i \le 10^8$。

算法分析

根据集合中数的二进制建立Trie树,记录下每个节点子树的大小。对于每次询问,从高到低枚举$p, l$二进制的第$k$位,用$p_k, l_k$表示。设当前走到的节点为$t$,下一位为$s$则走到节点$t_s$。若$l_k=1$,则节点$t_{p_k}$所表示的数一定小于$l$;若$l_k=0$,则节点$t_{1-p_k}$所表示的数一定大于$l$。

代码

#include <iostream>
using namespace std;
int q, o, p, l;
struct trie_tree {
    int tot = 1;
    struct node_type {
        int sum, child[2];
    } a[2000001];
    void insert(int t) {
        int r = 1; ++a[r].sum;
        for (int i = 26; i >= 0; --i) {
            if (!a[r].child[(t >> i) & 1]) a[r].child[(t >> i) & 1] = ++tot;
            r = a[r].child[(t >> i) & 1], ++a[r].sum;
        }
    }
    void remove(int t) {
        int r = 1; --a[r].sum;
        for (int i = 26; i >= 0; --i) {
            r = a[r].child[(t >> i) & 1], --a[r].sum;
        }
    }
    int find(int p, int l) {
        int r = 1, ret = 0;
        for (int i = 26; i >= 0; --i) {
            int s = (p >> i) & 1, t = (l >> i) & 1;
            if (t && a[r].child[s]) ret += a[a[r].child[s]].sum;
            if (t && a[r].child[!s]) r = a[r].child[!s];
            else if (!t && a[r].child[s]) r = a[r].child[s];
            else break;
        }
        return ret;
    }
} tree;
int main()
{
    cin >> q;
    while (q--) {
        cin >> o;
        switch (o) {
            case 1: {
                cin >> p, tree.insert(p);
                break;
            }
            case 2: {
                cin >> p, tree.remove(p);
                break;
            }
            default: {
                cin >> p >> l;
                cout << tree.find(p, l) << endl;
            }
        }
    }
    return 0;
}