这题我很久之前用分块写过，没写出来。。
今天又看到了，于是下决心把这题做出来。
这次我用线段树写的，直接对每本书的编号Hash一下然后离散化然后各建一棵线段树，维护当前编号在某个位置有没有书，就行了。
为了卡空间，我用了
\(vector\)，同时指针建树，结构体里不保存当前节点维护的区间，区间作为参数递归，这样就能过了，空间复杂度应该是
\(O(N+M\ log\ N)\)。
另外Hash的边界搞大一点，第一次只弄了10W 80分，改成100W就A了。
#include #include #include #define re registerusing namespace std;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}const int MAXN = 100010;int num; struct Seg_Tree{ int sum; Seg_Tree *l, *r; Seg_Tree() { l = NULL; r = NULL; sum = 0; } void pushup(){ sum = 0; if(l != NULL) sum += l->sum; if(r != NULL) sum += r->sum; } void Add(int c, int p, int L, int R){ if(L == R){ sum += c; return; } int mid = (L + R) >> 1; if(p > mid){ if(r == NULL) r = new Seg_Tree; r->Add(c, p, mid + 1, R); } else{ if(l == NULL) l = new Seg_Tree; l->Add(c, p, L, mid); } pushup(); } int Ask(int L, int R, int wl, int wr){ int ans = 0; if(L >= wl && R <= wr) return sum; if(L > wr || R < wl) return 0; int mid = (L + R) >> 1; if(l != NULL) ans += l->Ask(L, mid, wl, wr); if(r != NULL) ans += r->Ask(mid + 1, R, wl, wr); return ans; }};vector tree;int n, m, v[MAXN * 10], id[MAXN * 10];int getHash(int x){ int hash = x % 1000000; if(!v[hash]) v[hash] = x; else while(v[hash] != x && v[hash]) hash = (hash + 233) % 10000; return hash;}int a, b, c;int w[MAXN];char ch;int main(){ tree.push_back(Seg_Tree()); n = read(); m = read(); for(re int i = 1; i <= n; ++i){ w[i] = read(); re int hash = getHash(w[i]); if(!id[hash]) id[hash] = ++num, tree.push_back(Seg_Tree()); tree[id[hash]].Add(1, i, 1, n); } for(re int i = 1; i <= m; ++i){ do{ ch = getchar(); }while(ch != 'C' && ch != 'Q'); if(ch == 'C'){ a = read(); b = read(); re int hash = getHash(w[a]); tree[id[hash]].Add(-1, a, 1, n); hash = getHash(b); if(!id[hash]) id[hash] = ++num, tree.push_back(Seg_Tree()); tree[id[hash]].Add(1, a, 1, n); w[a] = b; } else{ a = read(); b = read(); c = read(); re int hash = getHash(c); if(!id[hash]) id[hash] = ++num, tree.push_back(Seg_Tree()); printf("%d\n", tree[id[hash]].Ask(1, n, a, b)); } } return 0;}