莫队算法/二分查找 FZU 2072 Count

 

题目传送门

题意：问区间内x的出现的次数
分析：莫队算法：用一个cnt记录x的次数就可以了。还有二分查找的方法

 

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Data
{
    int b, l, r, x;
    int id;
}data[MAXN];
int a[MAXN];
int cnt[MAXN];
int ans[MAXN];
int n, q;

bool cmp(Data x, Data y)
{
    if (x.b == y.b)    return x.r < y.r;
    return x.b < y.b;
}

void Modui(void)
{
    memset (cnt, 0, sizeof (cnt));

    int l = 1, r = 0;
    for (int i=1; i<=q; ++i)
    {
        while (data[i].l < l)    cnt[a[--l]]++;
        while (data[i].l > l)    cnt[a[l]]--, l++;
        while (data[i].r > r)    cnt[a[++r]]++;
        while (data[i].r < r)    cnt[a[r]]--, r--;

        ans[data[i].id] = cnt[data[i].x];
    }

    for (int i=1; i<=q; ++i)
    {
        printf ("%d\n", ans[i]);
    }
}

int main(void)        //FZU 2072 Count
{
    while (scanf ("%d%d", &n, &q) == 2)
    {
        int block = (int) sqrt (n * 1.0);
        for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);
        for     (int i=1; i<=q; ++i)
        {
            scanf ("%d%d%d", &data[i].l, &data[i].r, &data[i].x);
            data[i].b = data[i].l / block;    data[i].id = i;
        }

        sort (data+1, data+1+q, cmp);

        Modui ();
    }

    return 0;
}

 

代码(二分查找)：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[MAXN];
int n, q;
vector<int> cnt[MAXN];

int cal(int x, int r)
{
    if (!cnt[x].size ())    return 0;
    int pos = upper_bound (cnt[x].begin (), cnt[x].end (), r) - cnt[x].begin () - 1;
    return pos;
}

int main(void)        //FZU 2072 Count
{
//    freopen ("A.in", "r", stdin);

    while (scanf ("%d%d", &n, &q) == 2)
    {
        for (int i=1; i<=n; ++i)
        {
            scanf ("%d", &a[i]);
        }
        for (int i=1; i<=n; ++i)    cnt[a[i]].clear ();
        for (int i=1; i<=n; ++i)    cnt[a[i]].push_back (i);

        for (int i=1; i<=q; ++i)
        {
            int l, r, x;    scanf ("%d%d%d", &l, &r, &x);
            printf ("%d\n", cal (x, r) - cal (x, l - 1));
        }
    }

    return 0;
}