Boring Counting Time Limit: 3000ms Memory limit: 65536K 有疑问？点这里^_^ 题目描述 In this problem you are given a number sequence P consisting of N integer and Pi is the ith element in the sequence. Now you task is to answer a list of queries, for each query, please tell us among [L, R], how many Pi is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of Pi (L <= i <= R, A <= Pi <= B). 输入 In the first line there is an integer T (1 < T <= 50), indicates the number of test cases. For each case, the first line contains two numbers N and M (1 <= N, M <= 50000), the size of sequence P, the number of queries. The second line contains N numbers Pi(1 <= Pi <= 10^9), the number sequence P. Then there are M lines, each line contains four number L, R, A, B(1 <= L, R <= n, 1 <= A, B <= 10^9) 输出 For each case, at first output a line ‘Case #c:’, c is the case number start from 1. Then for each query output a line contains the answer. 示例输入
1 13 5 6 9 5 2 3 6 8 7 3 2 5 1 4 1 13 1 10 1 13 3 6 3 6 3 6 2 8 2 8 1 9 1 9
示例输出
Case #1: 13 7 3 6 9
提示
来源 2013年山东省第四届ACM大学生程序设计竞赛
先把数据离散化，然后离线，，树状数组处理
/*************************************************************************> File Name: H.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年04月06日 星期一 16时35分42秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const int N = 50010;int arr[N];int ans[N];struct QUE{int a, b;int Id;int flag;QUE(int _a = 0, int _b = 0, int _Id = 0, int _flag = 0){a = _a; b = _b; Id = _Id; flag = _flag;}};vector <QUE> que[N];int xis[N];int tree[N];int cnt, n;int search(int val){int mid;int l = 1, r = cnt;while (l <= r){mid = (l + r) >> 1;if (xis[mid] > val){r = mid – 1;}else if (xis[mid] < val){l = mid + 1;}else{break;}}return mid;}int lowbit(int x){return x & (-x);}void add(int x){for (int i = x; i < N; i += lowbit(i)){++tree[i];}}int sum(int x){int ans = 0;for (int i = x; i; i -= lowbit(i)){ans += tree[i];}return ans;}int main(){int t;scanf(“%d”, &t);int icase = 1;while (t–){int m;scanf(“%d%d”, &n, &m);memset(tree, 0, sizeof(tree));cnt = 0;for (int i = 1; i <= n; ++i){que[i].clear();scanf(“%d”, &arr[i]);xis[++cnt] = arr[i];}int l, r, a, b;for (int i = 1; i <= m; ++i){scanf(“%d%d%d%d”, &l, &r, &a, &b);que[r].push_back(QUE(a, b, i, 1));que[l – 1].push_back(QUE(a, b, i, -1));}memset(ans, 0, sizeof(ans));sort(xis + 1, xis + 1 + cnt);cnt = unique (xis + 1, xis + 1 + cnt) – xis – 1;for (int i = 1; i <= n; ++i){int val = search(arr[i]);add(val);int size = que[i].size();for (int j = 0; j < size; ++j){int a = lower_bound(xis + 1, xis + 1 + cnt, que[i][j].a) – xis;int b = lower_bound(xis + 1, xis + 1 + cnt, que[i][j].b) – xis;if (a > cnt){continue;}–a;if (b > cnt){b = cnt;}else if (xis[b] > que[i][j].b){–b;}int flag = que[i][j].flag;int Id = que[i][j].Id;ans[Id] += flag * (sum(b) – sum(a));}}printf(“Case #%d:\n”, icase++);for (int i = 1; i <= m; ++i){printf(“%d\n”, ans[i]);}}return 0;}
宁愿停歇在你门前的那棵树上，看着你，守护你。
