P1972 HH 的项链

HH 的项链：把不同数转化为位置贡献

问题

P1972 HH 的项链
给定一个序列，多次询问区间 $[l,r]$ 中不同数的个数。

数据规模：$n,m,a_i\le 10^6$。

最开始我考虑开一个权值树状数组，维护当前区间内每个权值的出现次数是否大于 $0$。这个信息确实能够表示答案，但不同询问之间需要同时移动左右端点，本质上就是莫队；而且既然每次只查询整个权值域中有多少种数出现，树状数组也可以直接用一个 tot 变量代替。

普通莫队可以作为一种正确实现，但复杂度约为 $O((n+m)\sqrt n)$，在本题 $10^6$ 的范围下就 T 了。考虑优化得到更好的复杂度，发现需要优化维护的信息，而不是继续优化权值树状数组了。

首先会想到把所有询问都按右端点 $r$ 升序排序，并从左向右扫描数组，由于一段区间中出现重复的数字，我们只需要考虑记录它靠近两端点的那一次出现就行了。

所以这里我们向右扩展空间，可以记录每个数字最后一次出现的位置，并且保留一个 $1$，接着一遍扫描一遍输出即可。

扫描到位置 $i$，记 $x = a_{i}$，若 $x$ 之前出现过，那就删去上一次出现的位置 lst[x] ，然后加入当前的位置 i，更新 lst[x] = i。

对于询问 $[l,r]$ 中的任意权值 $x$，它在区间内出现，当且仅当它截至 $r$ 的最后出现位置满足 $last_r(x)\ge l$。又因为 $last_r(x)\le r$，所以这等价于 $last_r(x)\in[l,r]$。

每种数恰好留下一个标记，于是区间不同数个数就转化为 $\displaystyle \sum_{i=l}^{r}b_i$，这个问题就可以简单用树状数组求一个前缀和解决了。

当然这题也可以按照 $l$ 排序，然后记录每个数第一次出现的位置，与 $r$ 并无本质区别。

时间复杂度为 $O((n+m)\log n)$，空间复杂度为 $O(n+\max a_i+m)$。

▶

P1972

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;

int a[maxn];
int lst[maxn];
int ans[maxn];

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

bool cmp( Query x, Query y ) {
    return x.r < y.r;
}

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; i++ ) a[i] = read( );
    
    int m = read( );
    for( int i = 1; i <= m; i++ ) {
        qs[i].l = read( );
        qs[i].r = read( );
        qs[i].id = i;
    }

    sort( qs + 1, qs + m + 1, cmp );

    bit.init( n );

    int cur = 1;
    for( int i = 1; i <= m; ++ i ) {
        auto [l, r, id] = qs[i];
        for( int j = cur; j <= r; ++ j ) {
            if( lst[a[j]] ) bit.add( lst[a[j]], -1 );
            bit.add( j, 1 );
            lst[a[j]] = j;
        }
        cur = r + 1;
        ans[id] = bit.query( l, r );
    }

    for( int i = 1; i <= m; i++ ) {
        cout << ans[i] << '\n';
    }
}

莫队版本

这份实现直接维护当前区间内每种权值的出现次数，是前期思路对应的 AC 代码。它与标准离线树状数组版本解决的是同一问题，但复杂度更高。

▶

P1972-1

int a[maxn];
int cnt[maxn];
int ans[maxn];
int block;
int tot;

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

int get_block( int pos ) { return (pos - 1) / block; }

bool cmp( Query x, Query y ) {
    int bx = get_block( x.l );
    int by = get_block( y.l );
    if( bx != by ) return bx < by;
    if( bx & 1 ) return x.r > y.r;
    return x.r < y.r;
}

void add( int pos ) {
    int x = a[pos];
    if( cnt[x] == 0 ) tot ++;
    cnt[x]++;
}

void del( int pos ) {
    int x = a[pos];
    cnt[x]--;
    if( cnt[x] == 0 ) tot --;
}

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; i++ ) a[i] = read( );
    
    int m = read( );
    for( int i = 1; i <= m; i++ ) {
        qs[i].l = read( );
        qs[i].r = read( );
        qs[i].id = i;
    }

    block = max( 1, (int)( n / sqrt( m ) ) );

    sort( qs + 1, qs + m + 1, cmp );

    int L = 1, R = 0;
    for( int i = 1; i <= m; ++ i ) {
        auto [l, r, id] = qs[i];
        while( L > l ) add( -- L );
        while( R < r ) add( ++ R );
        while( L < l ) del( L ++ );
        while( R > r ) del( R -- );
        ans[id] = tot;
    }

    for( int i = 1; i <= m; i++ ) {
        cout << ans[i] << '\n';
    }
}

记录

• 归属：[[区间频次统计模型]]、树状数组

• 新增：离线时应围绕单调变化的一端设计状态；通过“撤销旧位置、激活最后出现位置”，把不可直接相减的区间去重转化为可加的位置贡献。

• 分类：C