H. 排名

看起来好复杂好复杂，其实很暴力。
考虑这样一个tot序列，tot[x]表示cnt[y]=x的y的个数，很容易发现我们只要遍历一遍tot序列中不为0的部分就可以很容易求出答案。
而tot序列中不为0的部分不会超过$O(\sqrt{n})O(\backslash sqrt\; n)$，所以只要维护一个链表，每个节点表示一个tot上不为x的元素即可。
这样的话无论是修改还是查询复杂度都不超过$O(\sqrt{n})O(\backslash sqrt\; n)$，总复杂度$O(n\sqrt{n})O(n\backslash sqrt\; n)$，且$O(\sqrt{n})O(\backslash sqrt\; n)$的情况比较极限，实际跑的时候非常快。

int cnt[N], nt[N], pre[N], fir, a[N], tot[N];
void _remove(int x) {
    if (x == fir)fir = nt[x];
    if (pre[x])nt[pre[x]] = nt[x];
    if (nt[x])pre[nt[x]] = pre[x];
    pre[x] = nt[x] = 0;
}
void update(int x) {
    if (!fir) {
        fir = x;
        nt[x] = pre[x] = 0;
        return;
    }
    if (x < fir) {
        pre[fir] = x, nt[x] = fir, fir = x;
        return;
    }
    int i, tail = fir;
    for (i = fir; nt[i] && nt[i] < x; i = nt[i])
        tail = i;
    if (i) {
        nt[x] = nt[i], pre[x] = i;
        if (nt[i])pre[nt[i]] = x;
        nt[i] = x;
    }
    else {
        pre[x] = tail;
        nt[tail] = x;
    }
}
void add(int x) {
    if (cnt[x])
        if (!--tot[cnt[x]])
            _remove(cnt[x]);
    ++cnt[x];
    if (++tot[cnt[x]] == 1)
        update(cnt[x]);
}
void del(int x) {
    if (!--tot[cnt[x]])
        _remove(cnt[x]);
    if (--cnt[x])
        if (++tot[cnt[x]] == 1)
            update(cnt[x]);
}
ll query() {
    ll ans = 0;
    for (int i = fir, rk = 1; i; rk += tot[i], i = nt[i])
        ans += (ll)tot[i] * (i ^ rk);
    return ans;
}
 
int main() {
    int n = fast_IO::read();
    for (int i = 1; i <= n; ++i) {
        a[i] = fast_IO::read();
        add(a[i]);
    }
    int q = fast_IO::read();
    while (q--) {
        int opt = fast_IO::read();
        if (opt == 1) {
            int x = fast_IO::read(), y = fast_IO::read();
            del(a[x]);
            a[x] = y;
            add(a[x]);
        }
        else
            printf("%lld\n", query());
    }
    return 0;
}