【题解】Hackerrank Range Modular Queries

Problem

给定长度为 $n$ 的序列, $m$ 次询问,每次询问 $[l,r]$ 中模 $x$ 等于 $y$ 的数的个数

Thought

根号算法好题

若 $x\leq 200​$ ,显然可以直接存下来
将序列分为 $\sqrt n​$ 块,用 $f[i][j][k]​$ 表示第 $i​$ 块模 $j​$ 等于 $k​$ 的个数
每次加入一个数,需要更新 $200​$ 次,总复杂度 $O(n\sqrt n+m\sqrt n)​$

若 $x>200​$ ,保存每个数就不现实了
但是我们发现满足 $a_i\equiv y \pmod x​$ 的数很少,不超过 $200​$ 个
那么直接维护一个桶,每次在桶里查有多少个满足 $a_i\equiv y \pmod x​$ 的数
莫队维护区间,转移复杂度 $O(1)​$ ,查询复杂度 $O(200)​$

所以总复杂度为 $O(n\sqrt n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 40010;
const int M = 210;
int n, m, a[N];
int bel[N];
int Ans[N], cnt;
int f[M][M][M];
int t[N];
struct Query {
    int l, r, x, y, id;
    bool operator < (const Query a) const {
        if(bel[l] == bel[a.l])
            return r < a.r;
        return l < a.l;
    }
}q[N];
int siz;
void query(int l, int r, int x, int y, int id) {
    for(int i = l; i <= min(r, bel[l] * siz); ++ i)
        if(a[i] % x == y)
            ++ Ans[id];
    if(bel[l] != bel[r])
        for(int i = siz * (bel[r] - 1) + 1; i <= r; ++ i)
            if(a[i] % x == y)
                ++ Ans[id];
    for(int i = bel[l] + 1; i < bel[r]; ++ i)
        Ans[id] += f[i][x][y];
}
void solve() {
    sort(q + 1, q + cnt + 1);
    int head = 0, tail = 1;
    for(int i = 1; i <= cnt; ++ i) {
        while(q[i].l < tail) ++ t[a[-- tail]];
        while(q[i].r > head) ++ t[a[++ head]];
        while(q[i].l > tail) -- t[a[tail ++]];
        while(q[i].r < head) -- t[a[head --]];
        int now = q[i].y;
        while(now <= 40000) {
            Ans[q[i].id] += t[now];
            now += q[i].x;
        }
    }
} 
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    siz = sqrt(n);
    for(int i = 1; i <= n; ++ i) {
        bel[i] = (i - 1) / siz + 1;
        for(int j = 1; j <= 200; ++ j)
            ++ f[bel[i]][j][a[i] % j];
    }
    for(int i = 1; i <= m; ++ i) {
        int l = read() + 1, r = read() + 1, x = read(), y = read();
        if(x > 200) q[++ cnt] = {l, r, x, y, i};
        else query(l, r, x, y, i);
    }
    solve();
    for(int i = 1; i <= m; ++ i)
        printf("%d\n", Ans[i]);
    return 0;
}
Comments

添加新评论