sdutoj 2610 Boring Counting

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2610

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大学生程序设计竞赛

示例程序

分析：

题意是说给你一串数字，求在动态区间[L , R]内的在[A , B]范围内的数的个数。

数据很大，一般的方法会超。

官方标程：

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define lson l, m, rt->left
  9 #define rson m + 1, r, rt->right
 10 
 11 const int maxn = 55555;
 12 
 13 struct Node {
 14     int sum;
 15     Node *left, *right;
 16 }*root[maxn], tree[2000000], *idx;
 17 
 18 int num[maxn], p[maxn], mp[maxn];
 19 int n, m;
 20 int tol;
 21 
 22 
 23 inline Node* nextNode() {
 24     idx->sum = 0;
 25     idx->left = idx->right = NULL;
 26     return idx++;
 27 }
 28 
 29 inline Node* copyNode(Node* temp) {
 30     idx->sum = temp->sum;
 31     idx->left = temp->left;
 32     idx->right = temp->right;
 33     return idx++;
 34 }
 35 
 36 inline bool cmp(int a, int b) {
 37     return num[a] < num[b];
 38 }
 39 
 40 void input() {
 41     scanf("%d%d", &n, &m);
 42     for(int i = 1; i <= n; i++) {
 43         scanf("%d", &num[i]);
 44         p[i] = i;
 45     }
 46     sort(p + 1, p + n + 1, cmp);
 47     int pre = -0x7f7f7f7f;
 48     tol = 0;
 49     for(int i = 1; i <= n; i++) {
 50         if(num[ p[i] ] == pre) {
 51             num[ p[i] ] = tol;
 52         }
 53         else {
 54             pre = num[ p[i] ];
 55             mp[ ++tol ] = num[ p[i] ];
 56             num[ p[i] ] = tol;
 57         }
 58     }
 59 }
 60 
 61 void build(int l, int r, Node* rt) {
 62     if(l == r) return;
 63     int m = (l + r) >> 1;
 64     rt->left = nextNode();
 65     rt->right = nextNode();
 66     build(lson);
 67     build(rson);
 68 }
 69 
 70 int query(int ll, int rr, int l, int r, Node* rtl, Node* rtr) {
 71     if(ll <= l && r <= rr) {
 72         return rtr->sum - rtl->sum;
 73     }
 74     int m = (l + r) >> 1;
 75     int ret = 0;
 76     if(ll <= m) ret += query(ll, rr, l, m, rtl->left, rtr->left);
 77     if(rr > m) ret += query(ll, rr, m + 1, r, rtl->right, rtr->right);
 78     return ret;
 79 }
 80 
 81 Node* add(int x, int l, int r, Node* rt) {
 82     Node* temp = copyNode(rt);
 83     if(l == r) {
 84         temp->sum++;
 85         return temp;
 86     }
 87     int m = (l + r) >> 1;
 88     if(x <= m) temp->left = add(x, lson);
 89     else temp->right = add(x, rson);
 90     temp->sum = temp->left->sum + temp->right->sum;
 91     return temp;
 92 }
 93 
 94 void build() {
 95     idx = tree;
 96     root[0] = nextNode();
 97     build(1, tol, root[0]);
 98     for(int i = 1; i <= n; i++) {
 99         root[i] = add(num[i], 1, tol, root[i - 1]);
100     }
101 }
102 
103 inline int bin1(int x) { //find the left-most number that is >= x
104     int left = 1, right = tol;
105     int ans = -1;
106     while(left <= right) {
107         int mid = (left + right) >> 1;
108         if(mp[mid] >= x) {
109             ans = mid;
110             right = mid - 1;
111         }
112         else left = mid + 1;
113     }
114     return ans;
115 }
116 
117 inline int bin2(int x) { // find the right-most number that is <= x
118     int left = 1, right = tol;
119     int ans = -1;
120     while(left <= right) {
121         int mid = (left + right) >> 1;
122         if(mp[mid] <= x) {
123             ans = mid;
124             left = mid + 1;
125         }
126         else right = mid - 1;
127     }
128     return ans;
129 }
130 
131 void solve() {
132     static int cas = 1;
133     printf("Case #%d:
", cas++);
134     while(m--) {
135         int l, r, a, b;
136         scanf("%d%d%d%d", &l, &r, &a, &b);
137         a = bin1(a);
138         b = bin2(b);
139         if(a == -1 || b == -1) {
140             puts("0");
141             continue;
142         }
143         printf("%d
", query(a, b, 1, tol, root[l - 1], root[r]));
144     }
145 }
146 
147 int main() {
148     //freopen("input.in", "r", stdin);
149     //freopen("output.out", "w", stdout);
150 
151     int __t;
152     scanf("%d", &__t);
153     while(__t--) {
154         input();
155         build();
156         solve();
157     }
158     return 0;
159 }

View Code