P2709 【模板】莫队 / 小 B 的询问

小 B 的询问：从答案表达式写出莫队增删

问题

P2709 【模板】莫队 / 小 B 的询问
多次询问区间 $[l,r]$，求 $\sum_{x=1}^{k}cnt_x^2$，其中 $cnt_x$ 是数值 $x$ 在区间内的出现次数。

数据规模：$n,m,k\le 10^5$。

这是一个静态区间询问，但答案不能由普通前缀和直接相减，也没有容易直接合并的简单节点信息。

只要已经知道当前区间内每个数的出现次数，加入或删除一个位置时，答案就能从当前状态快速更新，因此可以使用莫队离线处理。

莫队算法适合处理的问题通常满足四个条件：

1. 离线
2. 区间
3. 已知当前区间答案，加入一个元素可以用较低复杂度更新答案；
4. 已知当前区间答案，删除一个元素可以用较低复杂度更新答案。

所以本题就非常适合使用这个做法，记当前答案为 $S = \sum_{x} cnt_{x}^{2}$，加入一个值为 $x$ 的位置时，只有 $cnt_{x}^{2}$ 这一项发生变化，所以可以 $\mathcal{O}(1)$ 更新答案。这两个 add 和 del 函数就是莫队的主体了。

然后我们分析为什么重新排序后能加速求解。莫队采用分块的思路，把左端点按照大小约为 $\sqrt{n}$ 的块分类，先按 $l$ 所在的块排序，同一个块内按 $r$ 排序，通常让相邻块的 $r$ 一升一降，减少折返路程。

下图是没有奇偶优化的移动：

下图是奇偶优化后的移动：

时间复杂度约为 $O((n+m)\sqrt n)$，空间复杂度为 $O(n+m+k)$。

▶

P2709

int a[maxn];
ll ans[maxn];
ll cnt[maxn];

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

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

bool cmp( Query x, Query y ) {
    int bx = get_block( x.l ), 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];
    nowans -= cnt[x] * cnt[x];
    ++ cnt[x];
    nowans += cnt[x] * cnt[x];
}

void del( int pos ) {
    int x = a[pos];
    nowans -= cnt[x] * cnt[x];
    -- cnt[x];
    nowans += cnt[x] * cnt[x];
}

void solve( ) {
    int n = read( ), m = read( ), k = read( );

    block = sqrt( n );
    nowans = 0;

    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, cmp );

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

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

记录

• 归属：[[区间频次统计模型]]、[[莫队]]

• 新增：判断莫队是否适用时，关键不是“区间询问”本身，而是端点移动后能否只修改少量状态并在 $O(1)$ 内恢复答案。

• 分类：待定