nyoj----522 Interval （简单树状数组）
Interval
时间限制：2000 ms | 内存限制：65535 KB
难度：4
描述
There are n(1 <= n <= 100000) intervals [ai, bi] and m(1 <= m <= 100000) queries, -100000 <= ai <= bi <= 100000 are integers.
Each query contains an integer xi(-100000 <= x <= 100000). For each query, you should answer how many intervals convers xi.
输入The first line of input is the number of test case.
For each test case,
two integers n m on the first line,
then n lines, each line contains two integers ai, bi;
then m lines, each line contains an integer xi.输出m lines, each line an integer, the number of intervals that covers xi.样例输入
2
3 4
1 3
1 2
2 3
0
1
2
3
1 3
0 0
-1
0
1样例输出
0
2
3
2
0
1
0上传者ACM_赵铭浩代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define maxn 200005 //整体平移100001个单位
5 #define lowbit(x) ((x)&(-x))
6 int aa[maxn+5];
7 void ope(int x,int val)
8 {
9 x+=100001;
10 while(x<=maxn)
11 {
12 aa[x]+=val;
13 x+=lowbit(x);
14 }
15 }
16 long long getsum(int x)
17 {
18 long long ans=0;
19 while(x>0)
20 {
21 ans+=aa[x];
22 x-=lowbit(x);
23 }
24 return ans;
25 }
26 int main()
27 {
28 int test,nn,m,i,a,b;
29 scanf("%d",&test);
30 while(test--)
31 {
32 scanf("%d%d",&nn,&m);
33 memset(aa,0,sizeof(aa));
34 for(i=0;i<nn;i++)
35 {
36 scanf("%d%d",&a,&b);
37 ope(a,1);
38 ope(b+1,-1);
39 }
40 for(i=0;i<m;i++)
41 {
42 scanf("%d",&a);
43 a+=100001;
44 printf("%I64d\n",getsum(a));
45 }
46 }
47 return 0;
48 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-04-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录