P4113 采花

采花：把至少出现两次转化为倒数第二次出现的位置

问题

P4113 [HEOI2012] 采花
给定一个颜色序列，多次询问区间 $[l,r]$ 中出现次数不少于两次的颜色数。

数据规模：$n,c,m\le 2\times 10^6$。

本题与 P1972 HH 的项链 非常像，上一题统计区间出现过的颜色，本题则统计出现过两次的颜色。

所以类似的迁移一下，我们多记录一个倒数第二次出现的位置即可。

记 lst1[x]、lst2[x] 分别为颜色 $x$ 最近一次和倒数第二次出现的位置。扫描到新位置 $i$，颜色为 $x$ 时：若原本存在 lst2[x] 则将该位置删除，若存在 lst1[x] 则将其加入，最后更新即可。

使用树状数组来维护前缀和和位置上的标记。

▶

P4113

struct BIT {
/* ======================================== */
ll tr[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr, tr + sz + 2, 0 );
}
void add( int idx, ll val ) {
    for( int i = idx; i <= sz; i += i & -i ) tr[i] += val;
}
ll ask( int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) res += tr[i];
    return res;
}
ll query( int l, int r ) { return ask( r ) - ask( l - 1 ); }
/* ======================================== */
} bit;

struct Query {
    int l, r, idx;
} qs[maxn];

int a[maxn];
int lst1[maxn], lst2[maxn];
int ans[maxn];

void solve( ) {
    int n = read( ), c = read( ), m = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );

    for( int i = 1; i <= m; ++ i ) {
        qs[i].l = read( ), qs[i].r = read( ), qs[i].idx = i;
    }

    sort( qs + 1, qs + m + 1, []( Query a, Query b ) {
        return a.r < b.r;
    });

    bit.init( n );

    int cur = 0;
    for( int i = 1; i <= m; ++ i ) {
        auto [l, r, idx] = qs[i];
        while( cur < r ) {
            ++ cur;
            int x = a[cur];
            if( lst2[x] ) bit.add( lst2[x], -1 );
            if( lst1[x] ) bit.add( lst1[x], 1 );
            lst2[x] = lst1[x];
            lst1[x] = cur;
        }
        ans[idx] = bit.query( l, r );
    }
    for( int i = 1; i <= m; ++ i ) {
        cout << ans[i] << '\n';
    }
}

记录

• 归属：[[区间频次统计模型]]、树状数组
• 新增：当区间查询要求同一权值至少出现 $k$ 次时，可以在固定右端点的扫描过程中维护其倒数第 $k$ 次出现位置；本题是 $k=2$，是“最后出现位置”离线模型的直接变式。
• 分类：待定