莫队算法/二分查找 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;

}