laekov

看到取模瞬间想到了昨天的bc。

应该这是取模然后求啥玩意的时候的比较通用的解法吧。p<=sqrt(maxv)的预处理，剩下的直接暴力。结果预处理又写丑了一回。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 100009;

const int maxv = 10000;

const int bsz = 100;

const int maxb = 103;

int n, m;

int a[maxn], vb[maxb][maxb], ve[maxb][maxb];

int xb[maxn], xe[maxn];

int i_buf[maxn * maxb * 2], tib;

void pre() {

memset(ve, 0, sizeof(ve));

memset(xe, 0, sizeof(xe));

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

++ xe[a[i]];

for (int i = 0; i <= maxv; ++ i) {

xb[i] = tib;

tib += xe[i];

xe[i] = xb[i];

}

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

i_buf[xe[a[i]] ++] = i;

for (int m = 1; m <= bsz; ++ m) {

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

++ ve[m][a[i] % m];

for (int i = 0; i < m; ++ i) {

vb[m][i] = tib;

tib += ve[m][i];

ve[m][i] = vb[m][i];

}

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

i_buf[ve[m][a[i] % m] ++] = i;

}

}

int queryb(int l0, int r0, int p, int k) {

if (vb[p][k] == ve[p][k])

return 0;

int *x1 = lower_bound(i_buf + vb[p][k], i_buf + ve[p][k], l0);

int *x2 = upper_bound(i_buf + vb[p][k], i_buf + ve[p][k], r0);

return x2 - x1;

}

int querys(int v, int l0, int r0) {

if (xb[v] == xe[v])

return 0;

int *x1 = lower_bound(i_buf + xb[v], i_buf + xe[v], l0);

int *x2 = upper_bound(i_buf + xb[v], i_buf + xe[v], r0);

return x2 - x1;

}

int querya(int l0, int r0, int p, int k) {

int ans = 0;

for (int i = k; i <= maxv; i += p)

ans += querys(i, l0, r0);

return ans;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

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

tib = 0;

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

scanf("%d", a + i);

pre();

while (m --) {

int l, r, p, k;

scanf("%d%d%d%d", &l, &r, &p, &k);

if (p <= bsz)

printf("%d\n", queryb(l, r, p, k));

else

printf("%d\n", querya(l, r, p, k));

}

}