发现题解里没有这个做法，过来写一篇题解。
简要题意
完成支持在 \(O(n \sqrt n)\) 时间复杂度内的数组 \(a\) 的单点插入和单点查询。
思路
要维护一个单点插入，并且要按照当前下标查找，我们考虑对于一个新加入的值，插入到数组里，所有的下标都是依次向后增加的。那如果我们维护一个数组的下标，在每次插入后动态修改每一个下标是不现实的，考虑让数组的下标映射为我们给数的编号。
具体来说，对于每个新加入的值，我们在序列中给他一个新的编号，我们维护多个块，每个块里面存储当前下标对应序列中此时这里是哪个编号，查询块的下标对应的编号就可以了。
那考虑此时的块，如果我们暴力地交换每一个数，时间复杂度是不优的，仍是 \(O(n)\)。
所以我们要思考一下插入在块中有什么性质。
对于一个满块，如果在块内插入一个数，那么块的末尾值一定到了下一个块，对于下一个块，就相当于在头上插入了一个值，那如果它是满块，就一定也会传递，直到传递到最后一个块或者空块。
考虑一下，如果我们把插入的那个块视为散块，那我们只需要暴力遍历那个块，把所有编号向后移，对于后面的整块，就是逐个推动。
这很像什么？队列！我们使用队列去维护这个操作，队列的队头是块的末尾值，队尾是块的开始值，即对于一个统领 \([l,r]\) 区间的块，队头是 \(r\) 对应的值，队尾是 \(l\) 对应的值。
当我们插入时，有以下两种情况：
- 当我们插入散块时，暴力找到应插入的位置，放入队列。
- 当我们插入整块时，肯定是从块的开始插入的，将这个值插入队尾，并且将队头弹出，让它去和下一个块判断，直到最后一个块或到一个空块。
图示如下：
然后因为我们块的下标对应的就是数组 \(a\) 此时的下标，而我们块内存储的编号对应的就是数组 \(a\) 当前下标对应的我们给那个数的编号。所以我们直接暴力在要查询的下标所对应块内的队列里查询那个点存储的下标即可。
实现细节
- 因为我们要维护队列，所以在暴力查询和更改时我们要用另一个队列先存储，后面再赋值回去。
- 注意边界条件，否则你会 RE，常见的边界条件错误是在最后一个块插入时不用最后一个块的边界，而用 \(a\) 的编号边界，并且要减一。
- 因为我们要新建节点，所以你的 \(N\) 需要大一点，至少比题目大两倍。
时间复杂度
可见，对于更改操作，我们暴力更改了一个块，又“聪明”地用 \(O(1)\) 更改了后面的块，时间复杂度 \(O(\sqrt n)\)，而查询操作我们只暴力查找一个块，对应的时间复杂度也是 \(O(\sqrt n)\)。故总时间复杂度 \(O(n \sqrt n)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 6e5 + 66, KA = 1500 + 66;
int a[N], n, m;
struct Block{int id[N], len, tot = 0;//id 来维护块的下标，为了查询每个插入完的位置所在的块//len 块长 tot 块个数queue<int> q[KA];//队列维护真实编号void build(){len = sqrtl(n);tot = 0;for(int i = 1;i <= n;i ++){if((i - 1) % len) id[i] = tot;else tot ++, id[i] = tot;}for(int i = n;i >= 1;i --) q[id[i]].push(i);//从后往前构造队列，这样我们才能保证末尾数在队头}int calc(int p){return min(len * p, n);}//计算边界值的函数void update(int l, int x){int lb = id[l], lz = calc(id[l]);//lb l所在的块的编号 lz l块的右边界int p = x;queue<int> Q;//p 存储需要更改的值if(lb == tot)//如果时最后一个块{id[n] = lb;//我们每一次新建了一个节点，所以要把这个下标对应的块划好，先默认是最后一个块for(int i = n - 1;i > calc(lb - 1);i --)//从后往前遍历，后面就不说了{Q.push(q[lb].front());q[lb].pop();if(i == l) Q.push(p);//因为我们是从后往前遍历，和队列一样，直接找就可以//然后因为我们的 p 在插入的 l 之前，所以其在队列里要在 l 后面}q[lb] = Q;if(q[lb].size() > len)//判断是否要新建块（是否到了空块）{tot ++;//新建块q[tot].push(q[lb].front());q[lb].pop();//插入id[n] = tot;//此时的下标就在新块里}return ;}for(int i = lz;i > calc(lb - 1);i --){Q.push(q[lb].front());q[lb].pop();if(i == l) Q.push(p);}p = Q.front();Q.pop();q[lb] = Q;//同上，只不过要用 p 记录一下现在的队头了int s = tot;id[n] = tot;//因为我们更改了 tot，所以为了循环可以正常进行，我们先赋原值给一个变量//仍然默认下标对应最后一个块for(int i = lb + 1;i <= s;i ++){q[i].push(p);p = q[i].front();if(i != s) q[i].pop();//这里不能先弹出，我们要用这个判断是否建新块if(i == s && q[i].size() > len){tot ++;q[tot].push(p);q[i].pop();//这里再弹出id[n] = tot;}}}ll query(int x){int xd = id[x], xz = calc(id[x]), ans = 0;//xd x在哪个块 sz 块的右边界 ans 编号queue<int> Q;for(int i = xz;i > calc(xd - 1);i --){if(i == x) ans = q[xd].front();Q.push(q[xd].front());q[xd].pop();}//暴力查找q[xd] = Q;//赋值回去return ans;}
}b;
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;m = n;//因为我更改的 n，所以要用 m 来记一下for(int i = 1;i <= n;i ++) cin >> a[i];b.build();for(int i = 1;i <= m;i ++){ll op, l, r, x;cin >> op;if(!op) cin >> l >> r, a[++ n] = r, b.update(l, n);//更改对应对应位置else cin >> r, cout << a[b.query(r)] << '\n';//因为我们维护的是下标所对应 a 的真实编号，所以外面还得套个 a[]}return 0;
}