题意：有一个无限行$n$列的数表$a_{i,j}$，对于第$i\geq2$行，$a_{i,j}$为$a_{i-1,j}$在$a_{i-1,1\cdots j}$中出现的次数，要维护这个数表，支持修改第一行，查询任意位置
这题挺神的...首先随机一些数据，打个表可以发现这个数表的第$2,4,6,\cdots$行都是一样的，并且$3,5,7,\cdots$行也是一样的，下面写一个来自zjt的证明（%%%）
假设对数列$a_{1\cdots n}$有变换$f(a)$：将每一个$a_i$替换成它在$a_{1\cdots i}$中出现的次数，要证$f(a)=f(f(f(a)))$
先考虑$f(a)$，因为是统计出现次数，所以它肯定是由一堆$1,2,3,\cdots$穿插而成，我们可以每次贪心地从前往后取出最长的$1,2,3,\cdots$，把每次取出来的数字分为一组
再考虑$f(f(a))$，可以看出$f(a)$的第$i$组在$f(f(a))$中全部变成了$i$
最后考虑$f(f(f(a)))$，对于所有数字$i$，它们变成了$1,2,3,\cdots$，刚好和$f(a)$一一对应
所以对于本题，我们只需要知道第$1,2,3$行分别是什么就可以了
考虑分块，$f_{i,j}$表示在$a_{1}$的前$i$块中，$j$出现的次数，$g_{i,j}$表示在$a_2$的前$i$块中，$j$出现的次数
先预处理，$f_{i,\cdots}$可以由$f_{i-1,\cdots}$和$a_{1,1\cdots n}$得到，$g_{i,\cdots}$可以由$g_{i-1,\cdots}$和$f_{i-1,\cdots}$得到
修改$a_{1,p}=v$就先在对应块中减去$a_{1,p}$，再加回$v$即可
询问$a_{x,y}$就找到最靠近$y$的块，把零散的信息加进去即可
然后就做完了，出题人真是太神啦orz
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
const int S=1000;
int a[100010],f[110][200010],g[110][200010],val[200010],M;
map<int,int>mp;
int num(int x){
if(mp.find(x)==mp.end()){
M++;
mp[x]=M;
val[M]=x;
}
return mp[x];
}
int main(){
int n,m,i,j,x,y,z;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);
a[i]=num(x);
}
x=0;
for(i=1;i<=n;i+=S){
z=min(i+S-1,n);
memcpy(f[(i-1)/S+1],f[(i-1)/S],sizeof(f[(i-1)/S]));
memcpy(g[(i-1)/S+1],g[(i-1)/S],sizeof(f[(i-1)/S]));
for(j=i;j<=z;j++){
f[(i-1)/S+1][a[j]]++;
g[(i-1)/S+1][f[(i-1)/S+1][a[j]]]++;
}
}
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&i,&x,&y);
if(i==1){
for(i=(y-1)/S+1;(i-1)*S+1<=n;i++){
g[i][f[i][a[y]]]--;
f[i][a[y]]--;
}
a[y]=num(x);
for(i=(y-1)/S+1;(i-1)*S+1<=n;i++){
f[i][a[y]]++;
g[i][f[i][a[y]]]++;
}
}else{
if(x==1){
printf("%d\n",val[a[y]]);
continue;
}
for(i=(y-1)/S*S+1;i<=y;i++){
f[(y-1)/S][a[i]]++;
g[(y-1)/S][f[(y-1)/S][a[i]]]++;
}
printf("%d\n",(x&1)?g[(y-1)/S][f[(y-1)/S][a[y]]]:f[(y-1)/S][a[y]]);
for(i=(y-1)/S*S+1;i<=y;i++){
g[(y-1)/S][f[(y-1)/S][a[i]]]--;
f[(y-1)/S][a[i]]--;
}
}
}
}