题解

思路

查询只关心一种给定编码，因此可以按编码分别维护它当前出现在哪些位置。若能对某个编码的位置集合支持插入、删除，以及统计区间内位置数，就能完成全部操作。

所有将来可能出现的编码和位置都可以从输入操作中预先得知。对每个编码，收集初始时及所有修改中它可能占据的位置，排序去重后建立一个独立的 Fenwick 树。树中位置的权值为一表示当前该书位放着这种编码，否则为零。

做法

先读入并保存全部操作，同时离散化所有书编码。对每个编码收集它可能出现的位置，排序去重并初始化 Fenwick 树。

初始时，把每个书位在所属编码的 Fenwick 树中加一。执行修改时，在旧编码对应的树中把该位置减一，在新编码对应的树中把该位置加一，并更新该书位的当前编码。执行查询时，在编码 $K$ 对应的 Fenwick 树中分别求位置不超过 $B$ 与不超过 $A-1$ 的前缀和，两者之差就是答案。若编码从未可能出现在任何位置，其答案直接为零。

对于没有修改的子任务，可直接为每种编码保存有序位置数组，用两次二分回答。对于 $N,M\le5000$ 的子任务，也可以维护当前数组并对每次查询直接扫描区间。

复杂度

设全部操作数为 $M$。所有编码的位置表总长度不超过 $N+M$。预处理排序的总复杂度为 $O((N+M)\log(N+M))$；每次修改或查询的复杂度为 $O(\log(N+M))$。空间复杂度为 $O(N+M)$。

正确性证明

对任意编码 $x$，其 Fenwick 树只在 $x$ 可能出现的位置上建立坐标。初始化后，树中每个坐标的权值恰等于对应书位当前是否放着编码 $x$ 的书。

一次修改只改变一个书位：算法从旧编码的树中删除该位置，并向新编码的树加入该位置，因此上述不变量继续成立。查询时，编码 $K$ 的树在 $[A,B]$ 上的权值和，恰好等于该区间内当前编码为 $K$ 的书位数。Fenwick 前缀和之差正是这个区间和，所以每个查询答案都正确。