https://www.luogu.com.cn/problem/P7708
考虑莫队。
我们的操作等于维护一个排列 \(p\)。交换：\(\mathsf{swap}(p_i,p_j)\)，赋值 \(a_{p_i}=k\)，查询 \(a_{p_i}\)。
那么在右侧加入一个操作是好做的，在左侧加入一个操作考虑右侧有多少个查询是关于 \(a_{i}\) 初始值的，维护桶即可。
如果不想考虑删除操作那么回滚就好啦。
复杂度 \(O(n\sqrt n)\)。
https://www.luogu.com.cn/problem/P7708
考虑莫队。
我们的操作等于维护一个排列 \(p\)。交换：\(\mathsf{swap}(p_i,p_j)\)，赋值 \(a_{p_i}=k\)，查询 \(a_{p_i}\)。
那么在右侧加入一个操作是好做的，在左侧加入一个操作考虑右侧有多少个查询是关于 \(a_{i}\) 初始值的，维护桶即可。
如果不想考虑删除操作那么回滚就好啦。
复杂度 \(O(n\sqrt n)\)。