一、题意核心（根据代码反向推导）

给定一个长度为 $n$ 的数组 $a$，要求构造一个数组 $b$，满足规则：

1. 对于数值等于 $i$ 的所有元素，它们在 $b$ 中的颜色编号必须恰好每 $i$ 个连续分为一组；
2. 同一组内的元素颜色相同；
3. 如果数值 $i$ 出现的总次数无法被 $i$ 整除，则无解，输出 $-1$；
4. 若有解，输出构造的染色数组 $b$。

一句话总结： 数值为 $i$ 的元素，必须每 $i$ 个染成同一种颜色。

---

二、核心数学条件

对于每个 $i \in [1,n]$，设 $cnt[i]$ 表示 $i$ 在数组 $a$ 中出现的次数，必须满足：

$$cnt[i] \bmod i = 0$$

只要有一个 $i$ 不满足，直接输出 $-1$。

---

三、算法流程（标程逻辑）

1. 统计位置

遍历数组 $a$，用 FRQ[i] 存储所有数值等于 $i$ 的下标位置。

$$FRQ[i] = \{\text{所有满足 } a[pos]=i \text{ 的下标 } pos\} $$

2. 合法性检查

遍历 $i=1\dots n$，检查：

$$|FRQ[i]| \mod i = 0$$

不满足则标记无解。

3. 构造答案数组

• 按顺序给元素分组染色
• 每 $i$ 个元素染成同一个颜色 $cnt$
• 染完一组，颜色编号 $cnt+1$

---

四、标程代码逐行详解

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;          // 测试用例数
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];      // 输入数组 a
        }
        
        // FRQ[i]：存储所有数值 = i 的位置下标
        vector<vector<int>> FRQ(n + 1);
        for (int i = 0; i < n; ++i) {
            FRQ[a[i]].push_back(i);
        }
        
        vector<int> b(n);   // 答案数组
        int cnt = 1;       // 颜色编号，从 1 开始
        bool ok = true;    // 是否有解
        
        // 遍历每个数值 i
        for (int i = 1; i <= n; ++i) {
            // 核心条件：出现次数必须能被 i 整除
            if (FRQ[i].size() % i != 0) {
                ok = false;
                break;
            }
            
            int c = 0;
            int sz = FRQ[i].size();
            // 每 i 个元素分一组，染同色
            while (c < sz) {
                // 一组染 i 个元素
                for (int v = 0; v < i; ++v) {
                    b[FRQ[i][c]] = cnt;
                    c++;
                }
                cnt++;   // 下一组颜色+1
            }
        }
        
        // 输出结果
        if (!ok) {
            cout << -1 << '\n';
        } else {
            for (int x : b) {
                cout << x << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

---

五、复杂度分析

• 统计位置：$O(n)$
• 检查 + 构造：$O(n)$
• 总复杂度：$O(n)$ 每组测试用例
• 完美支持 $n \le 2\times 10^5$

---

六、样例演示（直观理解）

示例： $n=3$ $a = [1,1,2]$

• $FRQ[1] = [0,1]$，长度 $2$，$2 \bmod 1=0$ ✔️ 每 1 个一组 → 颜色 [1,2]
• $FRQ[2] = [2]$，长度 $1$，$1 \bmod 2=1$ ❌ 输出 $-1$

---

七、总结

核心思想

1. 统计位置：记录每个数值出现的位置
2. 合法性判断：$|FRQ[i]| \bmod i = 0$
3. 分组染色：每 $i$ 个元素染同一种颜色
4. 输出构造结果