1 /**************************************************************  2     Problem: 3236  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:79318 ms  7     Memory:66252 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 #define lowbit(x) x & -x 15 using namespace std; 16 const int N = 100005; 17 const int M = 1000005; 18 const int Maxlen = 37000005; 19   20 int n, size, Q; 21 int BIT[2][N], cnt[N], pos[N], a[N]; 22 int ans1[M], ans2[M]; 23 int Len, Left; 24 char buf[Maxlen]; 25   26 struct Query { 27     int l, r, a, b, w; 28 } q[M]; 29 inline bool operator < (const Query &a, const Query &b) { 30     return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l]; 31 } 32 inline bool cmp_id (const Query &a, const Query &b) { 33     return a.w < b.w; 34 } 35   36 inline int read() { 37     int x = 0; 38     while (buf[Left] < ‘0‘ || ‘9‘ < buf[Left]) 39         ++Left; 40     while (‘0‘ <= buf[Left] && buf[Left] <= ‘9‘) 41         x = x * 10 + buf[Left++] - ‘0‘; 42     return x; 43 } 44   45 int len = 0, pr[15]; 46 inline void print(int x) { 47     while (x) 48         pr[++len] = x % 10, x /= 10; 49     if (!len) putchar(‘0‘); 50     while (len) 51         putchar(pr[len--] + ‘0‘); 52 } 53   54 inline void update(int x, int del, int T) { 55     while (x <= n) 56         BIT[T][x] += del, x += lowbit(x); 57 } 58   59 inline int query(int x, int T) { 60     int res = 0; 61     while (x) 62         res += BIT[T][x], x -= lowbit(x); 63     return res; 64 } 65   66 inline void update(int x, int del) { 67     if (!cnt[x]) 68         update(x, 1, 1); 69     cnt[x] += del; 70     if (!cnt[x]) 71         update(x, -1, 1); 72     update(x, del, 0); 73 } 74   75 int main() { 76     int i, l, r; 77     Len = fread(buf, 1, Maxlen, stdin); 78     buf[Len] = ‘ ‘; 79     n = read(), Q = read(); 80     size = (int) sqrt(n); 81     for (i = 1; i <= n; ++i) 82         a[i] = read(), pos[i] = i / size; 83     for (i = 1; i <= Q; ++i) { 84         q[i].l = read(), q[i].r = read(); 85         q[i].a = read(), q[i].b = read(); 86         q[i].w = i; 87     } 88       89     sort(q + 1, q + Q + 1); 90     for (i = l = 1, r = 0; i <= Q; ++i) { 91         for (; r < q[i].r; ) update(a[++r], 1); 92         for (; r > q[i].r; ) update(a[r--], -1); 93         for (; l < q[i].l; ) update(a[l++], -1); 94         for (; l > q[i].l; ) update(a[--l], 1); 95         ans1[q[i].w] = query(q[i].b, 0) - query(q[i].a - 1, 0); 96         ans2[q[i].w] = query(q[i].b, 1) - query(q[i].a - 1, 1); 97     } 98     for (i = 1; i <= Q; ++i) { 99         print(ans1[i]), putchar(‘ ‘);100         print(ans2[i]), putchar(‘\r‘), putchar(‘\n‘);101     }102     return 0;103 }