题目解析

问题重述

维护一个长度为 $n$ 的数组 $a$，支持两种操作：

1. 单点修改：将 $a[p]$ 改为 $x$
2. 区间查询：统计区间 $[l, r]$ 内值不同的有序对 $(i, j)$ 的数量，其中 $l \le i < j \le r$

查询是在线的，因为每个查询需要上一个第二类查询的答案来解码。

核心思路

1. 问题转化

区间 $[l, r]$ 内，总共有 $\binom{len}{2}$ 个有序对，其中 $len = r - l + 1$。

设区间内每个值 $v$ 的出现次数为 $cnt_v$，则值相同的对数为 $\sum_v \binom{cnt_v}{2}$。

因此，值不同的对数 = 总对数 - 值相同的对数：

$$ans = \binom{len}{2} - \sum_{v} \binom{cnt_v}{2}$$

其中 $\binom{len}{2} = \frac{len \cdot (len - 1)}{2}$。

2. 维护信息

我们需要维护区间内每个值的出现次数，以便快速计算 $\sum \binom{cnt_v}{2}$。

当某个值的出现次数从 $c$ 变为 $c'$ 时，$\binom{c}{2}$ 的变化量为：

$$\Delta = \binom{c'}{2} - \binom{c}{2} = \frac{c'(c'-1) - c(c-1)}{2} $$

特别地：

• 增加一个元素：$c' = c + 1$，$\Delta = \frac{(c+1)c - c(c-1)}{2} = c$
• 减少一个元素：$c' = c - 1$，$\Delta = \frac{(c-1)(c-2) - c(c-1)}{2} = -(c-1)$

3. 数据结构选择

• 单点修改 + 区间查询 → 使用树状数组或线段树
• 需要维护每个值的出现次数，并且支持快速修改和查询 $\sum \binom{cnt_v}{2}$
• 由于 $a_i \le n$，值域大小为 $n$，可以按值维护出现次数

方法一：CDQ 分治 + 离线（但本题在线，不适用）

方法二：树状数组套平衡树（复杂度过高）

方法三：莫队算法（本题 $q$ 较大，$n$ 较大，莫队 $O((n+q)\sqrt{n})$ 可能超时，且需要在线）

方法四：分块 + 维护每个块内信息（可行，但需要处理修改）

方法五：使用带修莫队（支持修改的莫队，复杂度 $O(n^{2/3} \cdot q)$，本题 $q=3\times10^5$ 可能较大）

实际上，本题正解是使用分块 + 维护每个值在每个块内的出现次数，并用树状数组维护每个值的全局出现次数，但修改时需要更新所有块。

4. 更简洁的思路

注意到 $\binom{cnt_v}{2} = \frac{cnt_v^2 - cnt_v}{2}$，所以：

$$\sum_v \binom{cnt_v}{2} = \frac{\sum_v cnt_v^2 - \sum_v cnt_v}{2} = \frac{\sum_v cnt_v^2 - len}{2} $$

因此，答案可以改写为：

$$ans = \frac{len(len-1)}{2} - \frac{\sum_v cnt_v^2 - len}{2} = \frac{len^2 - \sum_v cnt_v^2}{2} $$

即：

$$ans = \frac{len^2 - \sum_{v} cnt_v^2}{2}$$

这个公式非常优美：

• $len^2$ 很容易计算
• $\sum cnt_v^2$ 可以通过维护平方和来快速更新

当某个值的出现次数从 $c$ 变为 $c'$ 时，$\sum cnt_v^2$ 的变化量为 $c'^2 - c^2$。

5. 使用 BIT 维护 $\sum cnt_v^2$

我们可以对每个值 $v$ 维护一个 BIT，表示该值在数组中的出现位置。但这样空间复杂度 $O(n^2)$ 不可行。

更好的方法：使用 Fenwick Tree 套哈希表，但实现复杂。

实际上，由于 $n, q \le 10^5$，我们可以使用分块：

• 将数组分成 $\sqrt{n}$ 块，每块大小约 $\sqrt{n}$
• 维护每块内每个值的出现次数
• 维护全局每个值的出现次数
• 查询时，整块直接使用块的统计，散块暴力统计
• 修改时，更新所在块的统计和全局统计

6. 最终算法

数据结构：

• block_size = sqrt(n)
• block_cnt[block_id][value]：每个块内每个值的出现次数（值域 $[1, n]$，但 $\sqrt{n}$ 块，每块 $n$ 种值，总空间 $O(n^{1.5})$，约 $10^{7.5} \approx 3 \times 10^7$，可以接受）
• global_cnt[value]：全局每个值的出现次数
• sum_sq：全局 $\sum cnt_v^2$

查询 $[l, r]$：

1. 计算 $len = r - l + 1$
2. 初始化 $sum\_sq = 0$
3. 处理整块：对每个整块的每个值，$sum\_sq += block\_cnt[b][v]^2$
4. 处理散块：暴力统计散块内每个值的出现次数，累加平方
5. 答案 = $(len^2 - sum\_sq) / 2$

但每次查询都遍历所有值（$O(n)$）会超时。需要优化：维护每块的平方和，查询时整块直接取块的平方和。

优化后：

• 每块维护块内 $\sum cnt_v^2$（记为 block_sum_sq[block_id]）
• 查询时：
  • 整块的贡献直接取 block_sum_sq
  • 散块暴力统计，计算贡献后加到 total_sum_sq
  • 注意散块中出现的值可能在整块中也出现过，需要合并统计

7. 合并统计的方法

对于区间 $[l, r]$，我们需要的是区间内每个值的出现次数的平方和，而不是块内独立统计。

因此，我们需要：

• 遍历所有整块，记录每个值在整块中出现的次数（可以用临时数组或哈希表，但值域 $n$，可以直接用数组）
• 遍历散块，累加出现次数
• 最后计算 $\sum cnt^2$

由于 $len$ 可能很大，但每次查询涉及的散块元素只有 $O(\sqrt{n})$，整块数量也是 $O(\sqrt{n})$，所以每次查询的复杂度约为 $O(\sqrt{n} + \text{值域})$，但值域 $n$ 会很大（$10^5$），遍历所有值不可取。

更好的方法：

• 整块的贡献直接用块内统计的平方和，但这样不同块之间的相同值会被重复计算平方，而不是先合并再平方

实际上，块内平方和不能直接相加，因为 $(a+b)^2 \neq a^2 + b^2$。

所以我们需要在查询时动态合并统计。

由于 $\sqrt{n} \approx 316$，整块数量不超过 $\sqrt{n}$，散块元素不超过 $2\sqrt{n}$，所以总涉及的不同值数量是 $O(\sqrt{n})$（因为在散块中出现的值最多 $2\sqrt{n}$ 个，整块中出现的值可能很多，但我们可以只记录整块中那些也在散块中出现的值）。

解决方案：

1. 用哈希表或数组记录区间内每个值的出现次数（数组需要 $O(n)$ 清零，不可行）
2. 用 unordered_map 记录出现过的值（均摊 $O(1)$）

由于每次查询涉及的整块和散块元素总数是 $O(\sqrt{n})$，因此 unordered_map 的大小也是 $O(\sqrt{n})$。

算法步骤

1. 预处理分块：block_size = sqrt(n)
2. 初始化全局数组 a 和每块的统计
3. 对于每个查询：
   • 解码（使用 last）
   • 如果是修改操作：
     • 找到 $p$ 所在的块
     • 更新该块的统计和全局统计
   • 如果是查询操作：
     • 用 unordered_map 统计区间 $[l, r]$ 内每个值的出现次数
     • 遍历整块（值出现次数直接取块统计）
     • 遍历散块（逐个元素统计）
     • 计算 $\sum cnt^2$
     • 答案 = $(len^2 - \sum cnt^2) / 2$
     • 更新 last

时间复杂度

• 每次修改：$O(1)$（更新块统计和全局统计）
• 每次查询：$O(\sqrt{n})$（遍历块和散块）
• 总复杂度：$O(q\sqrt{n})$，约 $3\times10^5 \times 316 \approx 10^8$，勉强可过

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXV = 100005;

int n, q;
int a[MAXN];
int block_size, block_num;
vector<int> block_id;
vector<unordered_map<int, int>> block_cnt;
vector<long long> block_sum_sq;

void init() {
    block_size = sqrt(n);
    block_num = (n + block_size - 1) / block_size;
    block_id.resize(n);
    block_cnt.resize(block_num);
    block_sum_sq.resize(block_num, 0);
    
    for (int i = 0; i < n; i++) {
        block_id[i] = i / block_size;
        int val = a[i];
        int b = block_id[i];
        block_cnt[b][val]++;
        block_sum_sq[b] += 2LL * block_cnt[b][val] - 1;
        // 当 cnt 从 c-1 变为 c 时，c^2 - (c-1)^2 = 2c - 1
    }
}

void update(int pos, int new_val) {
    int b = block_id[pos];
    int old_val = a[pos];
    
    // 更新旧值的统计
    int old_cnt = block_cnt[b][old_val];
    block_sum_sq[b] -= 2LL * old_cnt - 1;
    if (--block_cnt[b][old_val] == 0) {
        block_cnt[b].erase(old_val);
    }
    
    // 更新新值的统计
    int new_cnt = block_cnt[b][new_val];
    block_sum_sq[b] += 2LL * new_cnt + 1;
    block_cnt[b][new_val] = new_cnt + 1;
    
    a[pos] = new_val;
}

long long query(int l, int r) {
    l--; r--;
    int len = r - l + 1;
    unordered_map<int, int> freq;
    
    int bl = block_id[l];
    int br = block_id[r];
    
    if (bl == br) {
        // 同一块内，暴力统计
        for (int i = l; i <= r; i++) {
            freq[a[i]]++;
        }
    } else {
        // 左侧散块
        for (int i = l; i < (bl + 1) * block_size; i++) {
            freq[a[i]]++;
        }
        // 右侧散块
        for (int i = br * block_size; i <= r; i++) {
            freq[a[i]]++;
        }
        // 中间整块
        for (int b = bl + 1; b < br; b++) {
            for (auto& [val, cnt] : block_cnt[b]) {
                freq[val] += cnt;
            }
        }
    }
    
    long long sum_sq = 0;
    for (auto& [val, cnt] : freq) {
        sum_sq += 1LL * cnt * cnt;
    }
    
    return (1LL * len * len - sum_sq) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    init();
    
    cin >> q;
    long long last = 0;
    
    for (int i = 0; i < q; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        
        if (type == 1) {
            int p = ((x + last) % n);
            int val = ((y + last) % n) + 1;
            update(p, val);
        } else {
            int l = ((x + last) % n) + 1;
            int r = ((y + last) % n) + 1;
            if (l > r) swap(l, r);
            long long ans = query(l, r);
            cout << ans << " \n"[i == q - 1];
            last = ans;
        }
    }
    
    return 0;
}

关键点总结

1. 公式转化：不同对数量 = 总对数 - 相同对数量 = $(len^2 - \sum cnt_v^2)/2$
2. 分块策略：$O(\sqrt{n})$ 查询，$O(1)$ 修改
3. 在线解码：使用 last 变量逐次解码查询参数
4. 值域压缩：$a_i \le n$，可以用数组或哈希表统计
5. 空间优化：每个块用 unordered_map 存储非零值，避免 $O(n^2)$ 空间

注意事项

• 使用 long long 存储平方和，避免溢出
• 修改时更新块内统计和平方和的公式：$c^2 - (c-1)^2 = 2c - 1$
• 查询时整块和散块的统计需要合并
• 输出格式：每个查询答案后跟一个空格，最后一个查询后换行