Range Modular Queries

题意

给出一个数列，q个查询，问查询区间内有几个数 a[i] % x == y。

分析

其实裸的分块就能过了，跑的还特别快。

这里分块的作用就是排序。

在x较小时可以暴力打表，x较大时枚举显得更加高效。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 4e4 + 10;

const int BLOCK = 200;

int n, q, L, R;

int a[MAXN];

int ans[MAXN];

int mp[4 * MAXN];

struct block

{

    int l, r, x, y;

    int id, bid;

    bool operator < (const block& other) const

    {

        if(bid == other.bid) return r < other.r;

        return bid < other.bid;

    }

}b[MAXN];

void query(int l, int r, int id, int x, int y)

{

    if(id)

    {

        for(int i = l; i < L; i++) mp[a[i]]++;

        for(int i = R + 1; i <= r; i++) mp[a[i]]++;

        for(int i = L; i < l; i++) mp[a[i]]--;

        for(int i = r + 1; i <= R; i++) mp[a[i]]--;

    }

    else

    {

        for(int i = l; i <= r; i++)

            mp[a[i]]++;

    }

    for(int i = 0; i < MAXN; i += x)

        ans[b[id].id] += mp[i + y];

    L = l; R = r;

}

int main()

{

    scanf("%d%d", &n, &q);

    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    for(int i = 0; i < q; i++)

    {

        scanf("%d%d%d%d", &b[i].l, &b[i].r, &b[i].x, &b[i].y);

        b[i].id = i;

        b[i].bid = b[i].l / BLOCK;

    }

    sort(b, b + q);

    for(int i = 0; i < q; i++) query(b[i].l, b[i].r, i, b[i].x, b[i].y);

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

    return 0;

}

code

#include<bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;

const int MAXN = 4e4 + 10;

const int MAXK = 205;

int a[MAXN], b[MAXN];

vector<int> pos[MAXK][MAXK];

vector<int> poss[MAXN];

int main()

{

    int n, q;

    scanf("%d%d", &n, &q);

    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    for(int i = 1; i < MAXK; i++)

        for(int j = 0; j < n; j++)

            pos[i][a[j] % i].push_back(j);

    for(int i = 0; i < n; i++)

    {

        poss[a[i]].push_back(i);

    }

    while(q--)

    {

        int l, r, x, y;

        scanf("%d%d%d%d", &l, &r, &x, &y);

        if(x < MAXK) // 打表

        {

            int ans = upper_bound(all(pos[x][y]), r) - lower_bound(all(pos[x][y]), l);

            printf("%d\n", ans);

        }

        else // x >= MAXK ，下面的循环会非常高效

        {

            int ans = 0;

            for(int i = y; i < MAXN; i += x)

            {

                ans += upper_bound(all(poss[i]), r) - lower_bound(all(poss[i]), l);

            }

            printf("%d\n", ans);

        }

    }

    return 0;

}

巴特西

Range Modular Queries

Range Modular Queries

题意

分析

code

code

最新文章

热门文章