hdu4325(线段树）

http://acm.hdu.edu.cn/showproblem.php?pid=4325

多校联合3上的题对线段树还不是太了解只知道这道题是线段树打的代码那叫一个纠结啊。。交上还TLE

昨天晚上仔细想了想明白是怎么回事了就是建一个线段树找到指定的区间加1 询问的时候看在哪些区间里把这些区间都加起来

w定义的int类型的一直出错后来一想存不了改了就对了

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 100001
 4 __int64 s[4*N],re;
 5 void build(int l,int r,__int64 w)
 6 {
 7     if(l==r)
 8     {
 9         s[w] = 0;
10         return ;
11     }
12     int m = (l+r)/2;
13     build(l,m,2*w);
14     build(m+1,r,2*w+1);
15 }
16 void add(int a,int b,int l,int r,__int64 w)
17 {
18     if(a<=l&&b>=r)
19     {
20         s[w]++;
21         //printf("%I64d %d]",w,s[w]);
22         return ;
23     }
24     if(l==r)
25         return ;
26     int m = (l+r)/2;
27     if(a<=m)
28         add(a,b,l,m,2*w);
29     if(b>m)
30         add(a,b,m+1,r,2*w+1);
31 }
32 void getsum(int p,int l,int r,__int64 w)
33 {
34     if(p>=l&&p<=r)
35     {
36         re+=s[w];
37        // printf("%I64d %d]",w,s[w]);
38     }
39     if(l==r)
40         return ;
41     int m = (l+r)/2;
42     if(p>m)
43         getsum(p,m+1,r,2*w+1);
44     else
45         getsum(p,l,m,2*w);
46 }
47 int main()
48 {
49     int i,k = 0,n,m,t,a,b;
50     scanf("%d",&t);
51     while(t--)
52     {
53         k++;
54         memset(s,0,sizeof(s));
55         scanf("%d%d", &n,&m);
56         build(1,N,1);
57         for(i = 1 ; i <= n ; i++)
58         {
59             scanf("%d%d", &a,&b);
60             add(a,b,1,N,1);
61         }
62         printf("Case #%d:\n",k);
63         for(i = 1 ;i <= m ; i++)
64         {
65             scanf("%d",&a);
66             re = 0;
67             getsum(a,1,N,1);
68             printf("%I64d\n",re);
69         }
70     }
71     return 0;
72 }