N=100000,M=1000000

By wangyisong1996加强数据

  1 #include <cmath>  2 #include <cstdio>  3 #include <cstdlib>  4 #include <cstring>  5 #include <iostream>  6 #include <algorithm>  7   8 using namespace std;  9  10 /* SCANNER */ 11  12 #define siz 10000000 13  14 inline char get_a(void) { 15     static char buf[siz], *bit = buf; 16  17     if (bit == buf + siz) 18         fread(bit = buf, 1, siz, stdin); 19  20     return *bit++; 21 } 22  23 inline int get_i(void) { 24     register int ret = 0; 25     register int neg = false; 26     register int bit = get_a(); 27  28     for (; bit < ‘0‘; bit = get_a()) 29         if (bit == ‘-‘)neg ^= true; 30  31     for (; bit >= ‘0‘; bit = get_a()) 32         ret = ret * 10 + bit - ‘0‘; 33  34     return neg ? -ret : ret; 35 } 36  37 #define maxn 400005 38 #define maxm 1000005 39  40 int s; 41 int tot; 42 int n, m; 43 int num[maxn]; 44 int cnt[maxn]; 45 int tmp[maxn]; 46 int ans1[maxm]; 47 int ans2[maxm]; 48 int tree1[maxn]; 49 int tree2[maxn]; 50  51 struct query { 52     int l, r, a, b, id; 53 }qry[maxm]; 54  55 inline int cmp(const void *a, const void *b) { 56     query *A = (query *)a; 57     query *B = (query *)b; 58     if (A->l / s != B->l / s) 59         return A->l - B->l; 60     else 61         return A->r - B->r; 62 } 63  64 inline void add(int *t, int p, int k) { 65     for (; p <= tot; p += p&-p) 66         t[p] += k; 67 } 68  69 inline int ask(int *t, int p) { 70     int ret = 0; 71     for (; p; p -= p&-p) 72         ret += t[p]; 73     return ret; 74 } 75  76 inline void remove(int t) { 77     add(tree1, t, -1); 78     if (--cnt[t] == 0) 79         add(tree2, t, -1); 80 } 81  82 inline void insert(int t) { 83     add(tree1, t, 1); 84     if (++cnt[t] == 1) 85         add(tree2, t, 1); 86 } 87  88 signed main(void) { 89     n = get_i(); 90     m = get_i(); 91     s = sqrt(n); 92  93     for (int i = 1; i <= n; ++i) 94         num[i] = get_i(), tmp[++tot] = num[i]; 95  96     for (int i = 1; i <= m; ++i) { 97         qry[i].id = i; 98         qry[i].l = get_i(); 99         qry[i].r = get_i();100         qry[i].a = get_i();101         qry[i].b = get_i();102     }103 104     for (int i = 1; i <= m; ++i)105         tmp[++tot] = qry[i].a,106         tmp[++tot] = qry[i].b;107 108     sort(tmp + 1, tmp + 1 + tot);109 110     tot = unique(tmp + 1, tmp + 1 + tot) - tmp;111 112     for (int i = 1; i <= n; ++i)113         num[i] = lower_bound(tmp + 1, tmp + tot, num[i]) - tmp;114 115     for (int i = 1; i <= m; ++i) {116         qry[i].a = lower_bound(tmp + 1, tmp + tot, qry[i].a) - tmp;117         qry[i].b = lower_bound(tmp + 1, tmp + tot, qry[i].b) - tmp;118     }119 120     /*121     for (int i = 1; i <= n; ++i)122         printf("%d ", num[i]);123 124     puts("");125 126     for (int i = 1; i <= m; ++i)127         printf("%d %d\n", qry[i].a, qry[i].b);128     */129 130     qsort(qry + 1, m, sizeof(query), cmp);131 132     int l = 1, r = 0;133 134     for (int i = 1; i <= m; ++i) {135         while (l < qry[i].l)remove(num[l++]);136         while (l > qry[i].l)insert(num[--l]);137         while (r < qry[i].r)insert(num[++r]);138         while (r > qry[i].r)remove(num[r--]);139         ans1[qry[i].id] = ask(tree1, qry[i].b) - ask(tree1, qry[i].a - 1);140         ans2[qry[i].id] = ask(tree2, qry[i].b) - ask(tree2, qry[i].a - 1);141     }142 143     for (int i = 1; i <= m; ++i)144         printf("%d %d\n", ans1[i], ans2[i]);145 146     //system("pause");147 }