Orz

竟然要分块。。。本来以为离线就好了。。。

 

1 /************************************************************** 2     Problem: 2506 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:920 ms 7     Memory:6320 kb 8 ****************************************************************/ 9  10 #include 
      
       11 #include 
       
        12  13 using namespace std;14 const int N = 100005;15 const int M = 105;16  17 struct data {18     int x, p, k, w, f;19     data() {}20     data(int _x, int _p, int _k, int _w, int _f) : x(_x), p(_p), k(_k), w(_w), f(_f) {}21 }q[N << 1];22 inline bool operator < (const data &a, const data &b) {23     return a.x < b.x;24 }25  26 int n, m, tot, Max;27 int a[N], f1[M][M], f2[N];28 int ans[2][N];29  30 inline int read() {31     int x = 0;32     char ch = getchar();33     while (ch < '0' || '9' < ch)34         ch = getchar();35     while ('0' <= ch && ch <= '9') {36         x = x * 10 + ch - '0';37         ch = getchar();38     }39     return x;40 }41  42 void add(int x) {43     for (int i = 1; i <= 100; ++i)44         ++f1[i][x % i];45     ++f2[x];46 }47  48 int main() {49     int i, j;50     int l, r, p, k;51     n = read(), m = read();52     for (i = 1; i <= n; ++i)53         a[i] = read(), Max = max(Max, a[i]);54     for (i = 1; i <= m; ++i) {55         l = read(), r = read(), p = read(), k = read();56         q[++tot] = data(l - 1, p, k, i, 0);57         q[++tot] = data(r, p, k, i, 1);58     }59     sort(q + 1, q + tot + 1);60     int now = 0;61     for (i = 1; i <= tot; ++i) {62         while (now < q[i].x)63             ++now, add(a[now]);64         p = q[i].p, k = q[i].k;65         if (p <= 100)66             ans[q[i].f][q[i].w] = f1[p][k];67         else68             for (j = k; j <= Max; j += p)69                 ans[q[i].f][q[i].w] += f2[j];70     }71     for (i = 1; i <= m; ++i)72         printf("%d\n", ans[1][i] - ans[0][i]);73 }