莫队算法（优雅的暴力）

小B的询问

题目描述

小B 有一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。
他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$，求：
$$\sum _{i=1}^k{c}_i^2$$

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。
小B请你帮助他回答询问。

输入格式

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数，表示 小B 的序列。

接下来的 $m$ 行，每行两个整数 $l,r$。

输出格式

输出 $m$ 行，每行一个整数，对应一个询问的答案。

样例 #1

样例输入 #1

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

样例输出 #1

6
9
5
2

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n,m,k\le 5\times 10^4$。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N = 1e6 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e9 + 7;

//莫队算法板子（优雅的暴力）

ll res;
ll pos[N];
ll a[N];
ll cnt[N];//记录出现的次数
ll ans[N];//记录答案
struct que
{
int l, r, k;
    bool operator < (const que&w) const
{
    return pos[l] == pos[w.l] ? r < w.r : l < w.l;   
};
}q[N];

void add(int x)
{
cnt[a[x]] ++;
res += (cnt[a[x]]) * (cnt[a[x]]) - (cnt[a[x]] - 1) * (cnt[a[x]] - 1);
}

void sub(int x)
{
cnt[a[x]] --;
res -= (cnt[a[x]] + 1) * (cnt[a[x]] + 1) - (cnt[a[x]]) * (cnt[a[x]]);
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
int siz = sqrt(n);
for(int i = 1; i <= n; i ++) 
{
cin >> a[i];
pos[i] = i / siz;
}
for(int i = 1; i <= m; i ++)
{
cin >> q[i].l >> q[i].r;
q[i].k = i;
}
sort(q + 1, q + 1 + m);
int l = 1, r = 0;
for(int i = 1; i <= m; i ++)
{
while(q[i].l < l) add(-- l);
while(q[i].r > r) add(++ r);
while(q[i].l > l) sub(l ++);
while(q[i].r < r) sub(r --);
ans[q[i].k] = res;
}
for(int i = 1; i <= m; i ++) cout << ans[i] << endl;
return 0;
}

莫队（发现了nmd，map得时间复杂度都是log，莫队又是暴力直接就超时了呜呜呜）

Little Elephant and Array

题面翻译

小象喜欢和数组玩。现在有一个数组 $a$，含有 $n$ 个正整数，记第 $i$ 个数为 $a_i$。

现在有 $m$ 个询问，每个询问包含两个正整数 $l_j$ 和 $r_j(1⩽l_j⩽r_j⩽n)$，小象想知道在 $A_{l_j}$ 到 $A_{r_j}$ 之中有多少个数 $x$，其出现次数也为 $x$。

输入格式

第一行 $n$ 和 $m$， $n$ 表示数组大小， $m$ 表示询问个数；

第二行共 $n$ 个数，第 $i$ 个数为 $a_i$ 的值；

接下来 $m$ 行，每行两个数 $l_j$ 和 $r_j$，意义如题面。

输出格式

共 $m$ 行，每行一个数，表示每一次询问的答案。

样例输入 #1

7 2
3 1 2 2 3 3 7
1 7
3 4

样例输出 #1

3
1

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N = 1e6 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e9 + 7;

//莫队算法板子（优雅的暴力）
//nmd map得时间复杂度
ll res;
ll pos[N];
ll a[N];
ll cnt[N];//记录出现的次数
ll ans[N];//记录答案
ll n, m;
struct que
{
ll l, r, k;
}q[N];

bool cmp(que a, que b)
{
return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
}
void add(ll x)
{
if(a[x] > n) return ;
if(cnt[a[x]] == a[x]) res --;
cnt[a[x]] ++;
if(cnt[a[x]] == a[x]) res ++;
}

void sub(ll x)
{
if(a[x] > n)  return ;
    if(cnt[a[x]] == a[x]) res --;
cnt[a[x]] --;
if(cnt[a[x]] == a[x]) res ++;
}
int main()
{
cin >> n >> m;
ll siz = sqrt(n);
for(ll i = 1; i <= n; i ++) 
{
scanf("%lld", &a[i]);
pos[i] = i / siz;
}
for(ll i = 1; i <= m; i ++)
{
scanf("%lld%lld", &q[i].l, &q[i].r);
q[i].k = i;
}
sort(q + 1, q + 1 + m, cmp);
ll l = 1, r = 0; 
for(ll i = 1; i <= m; i ++)
{
while(q[i].l < l) add(-- l);
while(q[i].r > r) add(++ r);
while(q[i].l > l) sub(l ++);
while(q[i].r < r) sub(r --);
ans[q[i].k] = res;
}
for(ll i = 1; i <= m; i ++) cout << ans[i] << '\n';
return 0;
}

原文地址：https://blog.csdn.net/2301_80882026/article/details/144329060

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！