CF220B [Little Elephant and Array] 题解

前言

这道题目的做法大概有：树状数组，线段树，莫队，以及观察后用前缀和。

难度：3星

题目大意：

给定一个长度为 的整型数组， 个询问 , 每次询问一段区间 ， 问区间 中有多少个数出现的次数等于这个数的大小。

思路

这道题看上去就感觉是一道莫队好题！

考虑到莫队难写，线段树难以维护。于是想到的观察题目性质。

这道题未必需要什么莫队,树状数组,线段树,分块。

直接观察题目性质并且利用好256MB空间，然后用前缀和用 O()的时间 莽过去就行了。

这道题目有一个优秀的性质：

虽然给定的数的大小可能为 。但是，并非所有数都是有用的，更加确切的说，实际上有用的数不超过 种。

首先，如果一种数，（在整个区间中）其出现次数小于等于自己的大小，那么这个数铁定“没用”了，其无论如何也无法在答案中做出贡献，这样子的数，是肯定可以删掉的。

什么情况下被留下来的数最多？ 不难发现，当每个数的大小尽量小的时候才能留下来的数最多，倘若想留下尽可能多的数，其中的最优情况就是留下了 ， ， , ... , ，根据等差数列求和公式，那么

这样子，留下来的 个数最大就只能是 种了。这也是本人用的算法的最坏情况。

仔细计算，发现 最大不会超过 ， 然后 * 的空间消耗大概是 。直接开上 的前缀和数组。对于每一次查询，只需要枚举有多少种数被包含在这个区间内的数量恰好等于其大小即可。

于是我们就用空间复杂度: O() 时间复杂度: O() 的 优秀 乱搞做法过了这一题。

Code

#include <bits/stdc++.h>
using namespace std;
int sum[505][100005];//暴力开数组
const int MAXN = 100005;
int n,q;
int a[MAXN];
map <int ,int > book,vis;//这里是记录信息用的两个map
int New[MAXN],tot = 0;

inline int read()//这里是快读
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar());
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

signed main()
{
    n = read(), q = read();
    for(int i = 1 ; i <= n;  i ++) 
    a[i] = read(),book[a[i]] ++,vis[a[i]] = 1;//这里是在统计信息

    for(int i = 1 ; i <= n ; i ++)
        if(book[a[i]] < a[i])
        vis[a[i]] = 0,a[i] = 0;//这里是在删去无用的数

    for(int i = 1 ; i <= n ; i ++)
        if(vis[a[i]] == 1) 
        tot ++ , New[tot] = a[i] , vis[a[i]] ++;//这里是在统计有用的数

    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= tot ; j ++){
            sum[j][i] = sum[j][i - 1] ;
            if(New[j] == a[i])sum[j][i] ++;//统计前缀和
        }

    for(int i = 1 ; i <= q ; i ++){
        int l = read() , r = read();
        int Ans = 0;
        for(int j = 1 ; j <= tot ; j ++)
            if(sum[j][r] - sum[j][l - 1] == New[j])Ans ++;//暴力统计答案
        printf("%d\n",Ans);
    }
    return 0;
}

后话

还有更加优秀的树状数组做法！感兴趣的同学可以自行百度。