SSL-ZYC 2644 线段树练习题一

本文主要是介绍SSL-ZYC 2644 线段树练习题一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
以从左往右，从后往前的顺序给出一些线段。最后从前面可以看见多少条线段？

---

思路:
模拟？100%超时
离散？100%爆内存

所以，这道题的最优解是——
我也不知道

———下面进入正题———

正解：线段树

一道模板题吧。

对于tree[x]:
tree[x].l为它的左端点
tree[x].r为它的右端点
tree[x].cover表示它是否有线段
tree[x*2]为它的左儿子
tree[x*2+1]为它的右儿子

1.建树
2.输入，记录
3.计算总长度，输出，AC

---

代码：

#include <cstdio>
#include <iostream>
using namespace std;int n,sum,m,x,y;struct N
{int l,r,cover;
}tree[100001];void make(int x)  //建树
{if (tree[x].r-tree[x].l<=1) return;  //已经是一个点tree[x*2].l=tree[x].l;tree[x*2].r=(tree[x].l+tree[x].r)/2;tree[x*2+1].l=(tree[x].l+tree[x].r)/2;tree[x*2+1].r=tree[x].r;  //儿子的左右断点make(x*2);make(x*2+1);  //继续建
}void insert(int x,int l,int r)  //插入
{if (tree[x].cover!=0) return;  //已经有线段if (tree[x].l==l&&tree[x].r==r)  //找到线段{tree[x].cover=1;return;}int mid=(tree[x].l+tree[x].r)/2;if (mid>=r)  //完全在左边{insert(x*2,l,r);return;}if (mid<=l)  //完全在右边{insert(x*2+1,l,r);return;}insert(x*2,l,mid);insert(x*2+1,mid,r);  //左右都有
}int count(int x)  //计算
{if (tree[x].cover==1) return tree[x].r-tree[x].l;  //该区域有线段if (tree[x].r<=tree[x].l+1) return 0;  //为一个点，退出return count(x*2)+count(x*2+1);  //搜索儿子
}int main()
{scanf("%d%d",&m,&n);tree[1].l=1;tree[1].r=m;  //初始化make(1);  //建树for (int i=1;i<=n;i++){scanf("%d%d",&x,&y);insert(1,x,y);  //插入}printf("%d\n",count(1));  //输出return 0;
}

这篇关于SSL-ZYC 2644 线段树练习题一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---