洛谷 P2709 小B的询问(分块莫队)

莫队算法

首先，这是一个离线算法

何为“离线”？

是指主方独自运转，主方与外界没有任何交互，也就是说运转时不接受外界的信号(自然没有一一对应的反馈)——非即时反馈。

步骤：

①.输入元素并分块(注意下标从1开始)

②.输入查询区间，记下id，并排序(cmp)

③.移动指针更新所查询区间

④.排回原序并输出答案(cmp_id)

关键

推导出区间中增减一个元素后答案的变化

算法标志

四个while

Description

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

题目链接： https://www.luogu.org/problemnew/show/P2709

关于update函数

莫队算法解决的多为累加和问题，区间更新步骤：

1.减去原来的答案

2.更新

3.加上更新后的答案

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 50010;

int n, m, k;///n个元素,m个询问;
int num, bel[N];///分块个数，每块标号
int a[N], sum[N];///元素值与其在相应区间上出现次数
ll ans;///当前区间查询所得答案

struct edge
{
    int l, r, id;
    ll val;
}e[N];

bool cmp(edge a, edge b)
{
    return bel[a.l] == bel[b.l] ? a.r < b.r : a.l < b.l;
}

bool cmp_id(edge a, edge b)
{
    return a.id < b.id;
}

void update(int x, int change)
{
    ans -= sum[ a[x] ] * sum[ a[x] ];///减去原来的答案
    sum[ a[x] ] += change;           ///更新
    ans += sum[ a[x] ] * sum[ a[x] ];///加上更新后的答案
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    ///1.输入元素并分块
    num = sqrt(n);
    for(int i = 1; i <= n; ++i)///下标需从1开始
    {
        scanf("%d", &a[i]);
        bel[i] = i / num + 1;
    }

    ///2.输入查询区间并记下id并排序
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d", &e[i].l, &e[i].r);
        e[i].id = i;
    }
    sort(e, e + m, cmp);

    ///3.移动指针更新所查询区间
    int l = 1, r = 0;
    for(int i = 0; i < m; ++i)
    {
        while(l < e[i].l)
            update(l, -1), ++l;
        while(l > e[i].l)
            update(l - 1, 1), --l;
        while(r < e[i].r)
            update(r + 1, 1), ++r;
        while(r > e[i].r)
            update(r, -1), --r;
        e[i].val = ans;
    }

    ///4.排回原序输出答案
    sort(e, e + m, cmp_id);
    for(int i = 0; i < m; ++i)
        cout << e[i].val << '\n';
    return 0;
}