hud -5124-lines(线段树)

题目的意思是求重合层数最多的段（把点也看成段）。

给的数据范围为N<1e5;

ai<1e9;

有于N只有1e5;那么离散化一下可以将ai的范围映射到1e5,而不改变原端点的相对大小。

接下来用线段树来做就行了，要用lazy操作，到最后再把所有的值放下，然后比较每个点的大小，最大的就为重合最多的。

线段树复杂度为N*log(N);

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<string.h>

 5 #include<stdlib.h>

 6 #include<math.h>

 7 #include<map>

 8 void local(int l,int r,int k);

 9 void add(int l,int r,int k,int uu,int ww);

10 typedef long long ll;

11 typedef struct pp

12 {

13     int x;

14     int y;

15 } ss;

16 int tree[4*100005];//线段树数组

17 int su[100005*2];

18 ss dd[100005];//结构体存段

19 int N;

20 using namespace std;

21 int main(void)

22 {

23     int i,j,k,num;

24     scanf("%d",&k);

25     while(k--)

26     {

27         N=0;

28         fill(tree, tree+4*100005,0);

29         scanf("%d",&num);

30         int z=0;

31         map<int,int>my;//映射

32         for(i=0; i<num; i++)

33         {

34             scanf("%d %d",&dd[i].x,&dd[i].y);

35             su[z]=dd[i].x;

36             z++;

37             su[z]=dd[i].y;

38             z++;

39         }

40         sort(su,su+z);

41         j=1;

42         for(i=0; i<z; i++)

43         {

44             if(my[su[i]]==0)

45             {

46                 my[su[i]]=j;

47                 j++;

48             }

49

50         }//离散化

51         for(i=0; i<num; i++)

52         {

53             int x=dd[i].x=my[dd[i].x];

54             int y=dd[i].y=my[dd[i].y];

55             add(x,y,0,1,j-1);//线段树加段更新

56         }

57         local(1,j-1,0);//最后下放查询

58         printf("%d\n",N);

59     }

60     return 0;

61

62 }

63 void add(int l,int r,int k,int uu,int ww)//建树更新

64 {

65     if(l>ww||r<uu)

66     {

67         return ;

68     }

69     else if(l<=uu&&r>=ww)

70     {

71         tree[k]+=1;

72     }

73     else

74     {

75         add(l,r,2*k+1,uu,(uu+ww)/2);

76         add(l,r,2*k+2,(uu+ww)/2+1,ww);

77     }

78 }

79 void local(int l,int r,int k)//下放查询

80 {

81     if(l==r)

82     {

83         if(N<tree[k])

84         {

85             N=tree[k];

86         }

87         return ;

88     }

89     else

90     {

91         tree[2*k+1]+=tree[k];

92         tree[2*k+2]+=tree[k];

93         local(l,(l+r)/2,2*k+1);

94         local((l+r)/2+1,r,2*k+2);

95

96     }

97 }

[title]1002 lines[/title] 我们可以将一条线段[x_i,y_i][xi,yi]分为两个端点x_ixi和(yi)+1(yi)+1，在x_ixi时该点会新加入一条线段，同样的，在(y_i)+1(yi)+1时该点会减少一条线段，因此对于2n个端点进行排序，

令x_ixi为价值1，y_iyi为价值-1，问题转化成了最大区间和，因为1一定在-1之前，因此问题变成最大前缀和，我们寻找最大值就是答案

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<string.h>

 6 #include<math.h>

 7 #include<map>

 8 int f(const void*p,const void*q);

 9 typedef long long ll;

10 typedef struct pp

11 {

12     int x;

13     int y;

14 } ss;

15 using namespace std;

16 ss a[100005*2];

17 int main(void)

18 {

19     int i,j,k,p,q,s,l;

20     scanf("%d",&k);

21     while(k--)

22     {

23         scanf("%d",&p);

24         int uu=0;

25         for(i=0; i<p; i++)

26         {

27             scanf("%d",&s);

28             a[uu].x=s;

29             a[uu].y=1;

30             uu++;

31             scanf("%d",&l);

32             a[uu].x=l;

33             a[uu].y=0;

34             uu++;

35         }

36         qsort(a,uu,sizeof(ss),f);

37         ll sum=0;

38         ll dd=0;

39         for(i=0; i<uu; i++)

40         {

41             if(a[i].y==1)

42             {

43                 sum++;

44                 if(sum>dd)

45                 {

46                     dd=sum;

47                 }

48             }

49             else sum--;

50         }

51         printf("%lld\n",dd);

52

53     }

54     return 0;

55 }

56 int f(const void*p,const void*q)

57 {

58     ss*w=(ss*)p;

59     ss*r=(ss*)q;

60     if(w->x==r->x)

61     {

62         return r->y-w->y;

63     }

64     return w->x-r->x;

65 }

下面map映射改为二分查找

  1 #include<stdio.h>

  2 #include<algorithm>

  3 #include<iostream>

  4 #include<string.h>

  5 #include<stdlib.h>

  6 #include<math.h>

  7 #include<map>

  8 void local(int l,int r,int k);

  9 int er(int n,int m,int k);

 10 void add(int l,int r,int k,int uu,int ww);

 11 typedef long long ll;

 12 typedef struct pp

 13 {

 14     int x;

 15     int y;

 16 } ss;

 17 int tree[4*100005];

 18 int su[100005*2];

 19 int mapp[100005*2];

 20 ss dd[100005];

 21 int N=0;

 22 using namespace std;

 23 int main(void)

 24 {

 25     int i,j,k,p,q,num;

 26     scanf("%d",&k);

 27     while(k--)

 28     {

 29         N=0;

 30         fill(tree, tree+4*100005,0);

 31         scanf("%d",&num);

 32         int z=0;

 33         map<int,int>my;

 34         for(i=0; i<num; i++)

 35         {

 36             scanf("%d %d",&dd[i].x,&dd[i].y);

 37             su[z]=dd[i].x;

 38             z++;

 39             su[z]=dd[i].y;

 40             z++;

 41         }

 42         sort(su,su+z);

 43         j=1;

 44         mapp[0]=1;

 45         for(i=1; i<z; i++)

 46         {

 47             if(su[i]!=su[i-1])

 48             {

 49                 j++;

 50                 mapp[i]=j;

 51             }

 52             else mapp[i]=j;

 53

 54         }

 55         for(i=0; i<num; i++)

 56         {

 57             int x=dd[i].x=er(0,z-1,dd[i].x);

 58             int y=dd[i].y=er(0,z-1,dd[i].y);

 59             add(x,y,0,1,j);

 60         }

 61         local(1,j,0);

 62         printf("%d\n",N);

 63     }

 64     return 0;

 65

 66 }

 67

 68

 69 void add(int l,int r,int k,int uu,int ww)

 70 {

 71     if(l>ww||r<uu)

 72     {

 73         return ;

 74     }

 75     else if(l<=uu&&r>=ww)

 76     {

 77         tree[k]+=1;

 78     }

 79     else

 80     {

 81         add(l,r,2*k+1,uu,(uu+ww)/2);

 82         add(l,r,2*k+2,(uu+ww)/2+1,ww);

 83     }

 84 }

 85 void local(int l,int r,int k)

 86 {

 87     if(l==r)

 88     {

 89         if(N<tree[k])

 90         {

 91             N=tree[k];

 92         }

 93         return ;

 94     }

 95     else

 96     {

 97         tree[2*k+1]+=tree[k];

 98         tree[2*k+2]+=tree[k];

 99         local(l,(l+r)/2,2*k+1);

100         local((l+r)/2+1,r,2*k+2);

101

102     }

103 }

104 int er(int n,int m,int k)

105 {

106     int zz=(n+m)/2;

107     if(m<n)

108     {

109         return -1;

110     }

111     if(su[zz]==k)

112     {

113         return mapp[zz];

114     }

115     else if(su[zz]>k)

116     {

117         return er(n,zz-1,k);

118     }

119     else return er(zz+1,m,k);

120 }

巴特西

hud -5124-lines(线段树)

最新文章

热门文章