题意
给出若干盒子,从前面看,求它们不重复的总宽度。
思路
可以用离散化也可以用线段树,线段树会比离散化快。
代码
#include<cstdio>
struct pfa
{
int b
,e
,v
;
}tree
[400001];
int n
,m
,x
,y
;
void creat(int p
,int l
,int r
)
{
tree
[p
].b
=l
;tree
[p
].e
=r
;
if (r
-l
>1)
{
creat(2*p
,l
,(l
+r
)/2);
creat(2*p
+1,(l
+r
)/2,r
);
}
}
void insert(int p
,int l
,int r
)
{
if (tree
[p
].v
==0)
{
int m
=(tree
[p
].e
+tree
[p
].b
)/2;
if (tree
[p
].b
==l
&&tree
[p
].e
==r
) tree
[p
].v
=1;
else if (r
<=m
) insert(2*p
,l
,r
);
else if (l
>=m
) insert(2*p
+1,l
,r
);
else
{
insert(2*p
,l
,m
);
insert(2*p
+1,m
,r
);
}
}
}
void init()
{
scanf("%d",&n
);
creat(1,1,n
);
scanf("%d",&m
);
for (int i
=1;i
<=m
;i
++)
{
scanf("%d%d",&x
,&y
);
insert(1,x
,y
);
}
}
int count(int p
)
{
if (tree
[p
].v
==1) return tree
[p
].e
-tree
[p
].b
;
else if (tree
[p
].e
-tree
[p
].b
==1) return 0;
else return count(2*p
)+count(2*p
+1);
}
int main()
{
init();
printf("%d",count(1));
}
转载请注明原文地址: https://www.6miu.com/read-1600157.html