Little Elephant and Array CodeForces - 220B（莫队）

62 阅读 0 评论 41 点赞

我是靠谱客的博主炙热墨镜，最近开发中收集的这篇文章主要介绍Little Elephant and Array CodeForces - 220B（莫队），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给一段长为n的序列和m个关于区间的询问，求出每个询问的区间中有多少种数字是该种数字出现的次数等于该数字的。

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 200010, INF = 0x7fffffff;
LL n, m;
LL pos[maxn], c[maxn], s[maxn], ans;
LL pre[maxn], t[maxn];
struct node
{
    LL l, r, res;
    int id;
}Node[maxn];

bool cmp(node x, node y)
{
    if(pos[x.l] == pos[y.l]) return x.r < y.r;
    return x.l < y.l;
}

bool cmp_id(node x, node y)
{
    return x.id < y.id;
}

void update(int p, int add)
{
    if(add == 1)
    {
        s[c[p]]++;
        if(s[c[p]] == pre[p])
            ans++;
        else if(s[c[p]] == pre[p] + 1)
            ans--;

    }
    else
    {
        s[c[p]]--;
        if(s[c[p]] == pre[p])
            ans++;
        else if(s[c[p]] + 1 == pre[p])
            ans--;
    }
}


int main()
{
    ans = 0;
    scanf("%lld%lld", &n, &m);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld", &c[i]);
        pre[i] = t[i] = c[i];
    }
    sort(t+1, t+n+1);
    int len = unique(t+1, t+n+1) - (t+1);
    for(int i=1; i<=n; i++)
        c[i] = lower_bound(t+1, t+len+1, c[i]) - t;
    int block = sqrt(n);
    for(int i=1; i<=n; i++)
        pos[i] = (i-1)/block + 1;
    for(int i=1; i<=m; i++)
    {
        scanf("%lld%lld", &Node[i].l, &Node[i].r);
        Node[i].id = i;
    }
    sort(Node+1, Node+m+1, cmp);
    for(int i=1, l=1, r=0; i<=m; i++)
    {
        for(; r < Node[i].r; r++)
            update(r+1, 1);
        for(; r > Node[i].r; r--)
            update(r, -1);
        for(; l < Node[i].l; l++)
            update(l, -1);
        for(; l > Node[i].l; l--)
            update(l-1, 1);

        Node[i].res = ans;
    }
    sort(Node+1, Node+m+1, cmp_id);
    for(int i=1; i<=m; i++)
        cout<< Node[i].res <<endl;


    return 0;
}