首页 > 代码库 > HDU 1556

HDU 1556

2024-07-05 23:23:00   224人阅读

这道题可以用线段树或者树状数组，我在网上看有些大神竟然没用线段树和树状数组就把这道题搞出来了。。汗。。。

 

线段树：

线段树不能更新到叶子，否则超时。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iostream>
 5 #define N 100005
 6 using namespace std;
 7 int ans;
 8 struct mem{
 9     int l,r;
10     int num;
11 }a[4*N];
12 
13 void build(int left,int right,int root)
14 {
15     a[root].l=left;
16     a[root].r=right;
17     a[root].num=0;
18     if(left==right) return;
19     int mid=(left+right)/2;
20     build(left,mid,root*2);
21     build(mid+1,right,root*2+1);
22 }
23 
24 void update(int left,int right,int root)
25 {
26     if(a[root].l==left&&a[root].r==right)
27     {
28         a[root].num++;
29         return;
30     }
31     if(left>=a[root*2+1].l) update(left,right,root*2+1);
32     else if(right<=a[root*2].r) update(left,right,root*2);
33     else{
34         int mid=(a[root].l+a[root].r)/2;
35         update(left,mid,root*2);
36         update(mid+1,right,root*2+1);
37     }
38 }
39 
40 void pre(int x,int root)
41 {
42     ans+=a[root].num;
43     if(a[root].l==a[root].r) return ;
44     if(x<=a[root*2].r) pre(x,root*2);
45     else pre(x,root*2+1);
46 }
47 
48 main()
49 {
50     int n, a, b, i;
51     while(scanf("%d",&n)==1&&n)
52     {
53         build(1,n,1);
54         for(i=1;i<=n;i++)
55         {
56             scanf("%d %d",&a,&b);
57             update(a,b,1);
58         }
59         for(i=1;i<n;i++)
60         {
61             ans=0;
62             pre(i,1);
63             printf("%d ",ans);
64         }
65         ans=0;
66             pre(n,1);
67             printf("%d\n",ans);
68     }
69 }

 

树状数组：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define MAXH 100005
 5 #include <iostream>
 6 using namespace std;
 7 
 8 int c[MAXH];
 9 int n;
10 
11 int lowbit(int x)
12 {
13     return x&(-x);
14 }
15 
16 void add(int x,int y)
17 {
18     while(x<=n)
19     {
20         c[x]+=y;
21         x+=lowbit(x);
22     }
23 }
24 
25 int sum(int x)
26 {
27     int ans=0;
28     while(x>0)
29     {
30         ans+=c[x];
31         x-=lowbit(x);
32     }
33     return ans;
34 }
35 
36 main()
37 {
38     int a, b;
39     while(scanf("%d",&n)==1&&n)
40     {
41         memset(c,0,sizeof(c));
42         for(int i=1;i<=n;i++)
43         {
44             scanf("%d %d",&a,&b);
45             add(a,1);
46             add(b+1,-1);
47         }
48         printf("%d",sum(1));
49         for(int i=2;i<=n;i++)
50         printf(" %d",sum(i));
51         cout<<endl;
52     }
53 }

 

大神的代码：

 1 #include"stdio.h"  
 2 int main()  
 3 {  
 4     int j,n,i,a,m,b;  
 5     while(scanf("%d",&n),n)  
 6     {  
 7         int c[100001]={0};  
 8         j=n,m=0;  
 9         while(j--)  
10         {  
11             scanf("%d %d",&a,&b);  
12             c[a]++,c[b+1]--;  
13         }  
14         for(i=1;i<n;i++)  
15         {  
16             m+=c[i];  
17             printf("%d ",m);  
18         }  
19         printf("%d\n",m+c[n]);  
20     }  
21     return 0；  
22 }

 

 


联系
我们