线段树练习题二【线段树】

线段树练习题二【线段树】"/>

线段树练习题二【线段树】

>Description
桌子上零散地放着若干个不同颜色的盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远(输入时,由底向上,从左到右)。

>Input
第一行输入一个整数n，表示桌面总宽度
第二行输入一个整数m，表示盒子数量
接下来m行，每行输入两个数x,y，表示第i个盒子的起始位置和终止位置

>Output
阴影宽度

>Sample Input
16
5
4 7
12 14
1 5
6 10
11 16

>Sample Output
4

>解题思路

看了一个晚上都没A，早上手动模拟的时候发现我的储存方式跟题目的不太一样，在a上+1就A了，我（巨爷们不准我爆粗 ）

也算模板题，插入时直接插入，就是树的数据要修改一点，-1表示此区间有多种颜色，需要继续搜下去。
查找：用布尔数组y记录第i种颜色有无出现。

>代码

#include <iostream>
#include <cstdio>using namespace std;int n, m, a, b, ans, t[400005];
bool c[100005];void insert (int d, int l, int r, int lf, int rf, int s) //我不想解释了你们应该都知道吧，s是颜色
{if (t[d] == s) return; //如果此格颜色已经是s的话就不用处理了if (l == lf && r == rf){t[d] = s; //覆盖return;}if (t[d] > 0){t[d * 2] = t[d * 2 + 1] = t[d]; //往下传递t[d] = -1; //标记有多种颜色}int mid = (l + r) >> 1;if (lf <= mid) insert (d * 2, l, mid, lf, min (mid, rf), s);if (rf > mid) insert (d * 2 + 1, mid + 1, r, max (mid + 1, lf), rf, s);t[d] = -1; //标记有多种颜色
}
void find (int d, int l, int r)
{if (t[d] == 0) return; //如果此区间的都没有颜色就不用往下搜了if (t[d] > 0){c[t[d]] = 1;return;}if (l == r) return; //没有子节点了就returnint mid = (l + r) >> 1;find (d * 2, l, mid);find (d * 2 + 1, mid + 1, r);
}
int main()
{scanf ("%d%d", &n, &m);for (int i = 1; i <= m; i++){scanf ("%d%d", &a, &b);insert (1, 1, n, a + 1, b, i); //用我的储存方法会发现，如果颜色只有一格，然后两边都有其它颜色的话，那一格会被覆盖，所以要a+1，这样格数是不会变的}find (1, 1, n);for (int i = 1; i <= m; i++)if (c[i]) ans++;printf ("%d", ans);return 0;
}