「采花」公主采花问题题解

问题分析

公主采花有一个特殊要求：某种颜色的花要么不采，要么至少采两朵。换句话说，对于某种颜色，只有当它在区间中出现至少两次时，公主才会采这种颜色的花。

因此，问题转化为：对于每个查询区间 $[l, r]$，统计有多少种颜色在该区间内至少出现两次。

核心思路

使用离线查询 + 树状数组的解法，关键思想是维护每种颜色最近两次出现的位置。

关键观察

对于某种颜色，如果它在区间 $[l, r]$ 内至少出现两次，那么它第二次出现的位置必须在区间内。

算法详解

1. 数据结构和变量定义

int last[MAXN];     // last[i]: 颜色i最近一次出现的位置
int last2[MAXN];    // last2[i]: 颜色i倒数第二次出现的位置  
int st[MAXN];       // 树状数组

2. 离线处理查询

// 按右端点排序查询
sort(a + 1, a + m + 1);

for (int i = 1, j = 1; i <= m; i++) {
    // 处理到当前查询的右端点
    for (; j <= a[i].r; j++) {
        // 处理第j朵花
        if (!last2[x[j]])          // 第一次出现这种颜色
            last2[x[j]] = j;
        else if (!last[x[j]]) {    // 第二次出现这种颜色
            add(last2[x[j]], 1);   // 在第二次出现位置+1
            last[x[j]] = j;
        } else {                   // 第三次或更多次出现
            add(last2[x[j]], -1);  // 移除旧的第二次位置
            add(last[x[j]], 1);    // 在最新的第二次位置+1
            last2[x[j]] = last[x[j]];
            last[x[j]] = j;
        }
    }
    // 计算答案：区间[l, r]内标记的数量
    ans[a[i].pos] = sum(a[i].r) - sum(a[i].l - 1);
}

3. 树状数组操作

inline void add(int x, int k) {
    while (x <= n) {
        st[x] += k;
        x += lowbit(x);
    }
}

inline int sum(int x) {
    int res = 0;
    while (x != 0) {
        res += st[x];
        x -= lowbit(x);
    }
    return res;
}

算法正确性分析

标记策略

• 对于每种颜色，我们始终在它倒数第二次出现的位置标记 +1
• 当颜色第三次出现时，更新标记位置到新的倒数第二次位置
• 这样，对于查询 $[l, r]$，统计的就是所有满足条件的颜色

为什么这样正确？

对于颜色 $c$：

• 如果在 $[l, r]$ 内出现次数 $\geq 2$，那么它的倒数第二次出现位置一定在 $[l, r]$ 内
• 如果在 $[l, r]$ 内出现次数 $< 2$，那么它的倒数第二次出现位置要么不存在，要么不在 $[l, r]$ 内

复杂度分析

• 排序查询：$O(m \log m)$
• 扫描处理：$O(n \log n)$
• 树状数组操作：每次 $O(\log n)$
• 总复杂度：$O((n+m) \log n)$，满足数据范围要求

样例验证

样例：1 2 2 3 1

处理过程：

• 位置1（颜色1）：第一次出现，last2[1]=1
• 位置2（颜色2）：第一次出现，last2[2]=2
• 位置3（颜色2）：第二次出现，在位置2标记+1
• 位置4（颜色3）：第一次出现，last2[3]=4
• 位置5（颜色1）：第二次出现，在位置1标记+1

查询 $[1,5]$：位置2和位置1有标记，答案为2

总结

本题的巧妙之处在于：

1. 问题转化：将"至少出现两次"转化为标记倒数第二次位置
2. 离线处理：按右端点排序，避免重复计算
3. 动态维护：使用树状数组高效维护和查询
4. 标记策略：始终在倒数第二次位置标记，确保正确性

这种"离线查询 + 扫描线 + 数据结构"的方法在解决区间计数问题时非常有效。