1. 题目

传送门=￣ω￣=

2. 题解

我做这题的历程：

1. 普通线段树套平衡树（map），70 分
2. 半递归式（修改变为递推）线段树套平衡树（map），80 分
3. 树状数组套平衡树（map），90 分
4. 树状数组套哈希表（pbds,cc_hash_table），90 分
5. 树状数组套哈希表（pbds,gp_hash_table），AC

心累啊。

具体做法很暴力，就是对于树状数组的每个节点搞个哈希表存某种编码出现的次数。

查询和修改就和普通的树状数组一模一样。

代码很短。

代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define lowbit(a) (a&-a)
using namespace std;
using namespace __gnu_pbds;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
int n,m,data[100005];
char opt[5];
gp_hash_table<int,int> mp[100005];
void update(int pos,int k,int d){while(pos<=n)mp[pos][k]+=d,pos+=lowbit(pos);}
int query(int pos,int k)
{
    int sum=0;
    while(pos)sum+=mp[pos][k],pos-=lowbit(pos);
    return sum;
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)IN(data[i]),update(i,data[i],1);
    int a,b,c;
    while(m--)
    {
        scanf("%s",opt),IN(a),IN(b);
        if(opt[0]=='Q')IN(c),printf("%d\n",query(b,c)-query(a-1,c));
        else update(a,b,1),update(a,data[a],-1),data[a]=b;
    }
    return 0;
}