线段树之基本操作与模板例题
一、什么是线段树？
1.1、线段树解决什么样的问题？
线段树是针对区间问题进行操作的高级数据结构，有这么一类RMQ问题（区间最值查询），是线段树的典型代表。如下：
给你一个长度为 n 的数列：{a1, a2, a3, a4, a5, a6, …… , an}，需要进行一下操作： ①、区间最值：给定：1 <= i <= j <= n，要 q 次查询区间 ：[i, j]的最值 ②、单点修改：给定某单点：k 和 x，要求吧第 k 个元素：ak = x ③、区间求和：给定区间 [i, j] 同①，要q次查询这个区间的和是多少？ ④、区间修改：给定区间 [i, j[ 同①，以及 x，要求把这个区间的元素全都乘上或者加上x
1.2、没有线段树我解决不了它们吗？
其实没有线段树，上述的问题也是很容易解决的！比如第一个：查询一次区间最值是O(n)，然后 q 次查询就是：O(q * n)，这种复杂度最多支持10000次查询区间长度不超过10000的数列！但是一般算法竞赛中的问题数据规模都比较大，无法用这种暴力的办法解决它们！
1.3、说了这么多，什么样的数据结构算线段树呢？
举一个区间 [1, 10] 构成线段树的例子，先看图：
仔细观察上面这颗线段树，容易发现：
第一：
每个结点代表一个线段，叶子结点的线段区间长度为1，也就是一个数。所以规模为 n 的线段树叶子结点一定是有 n 个的！
第二：
线段树中，若父节点为 [a, b]，则它的子节点分别为： 左子节点：[a, (a + b) / 2] 右子节点：[(a + b) / 2 + 1, b]
如此便可以轻松得到递归建立线段树的代码：
void build(int rt
, int l
, int r
)
{
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
if(l
== r
)
{
scanf("%lld", &tree
[rt
].val
);
return ;
}
int mid
= (l
+ r
) >> 1;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
}
第三：
对于根节点区间规模为 n 的二叉树，由二叉树的性质可以得到：整颗线段树的结点个数不会超过 2 * n 这个结论（提示：叶子结点有 n 个，向上一层的父节点有 n / 2 个，一直向上求和，是等比数列，然后求极限易得上述结论！）
1.4、行，我看懂了线段树的结构了，但是怎么解决最开始提出的问题呢？
其实线段树最巧妙、最强大的地方就在于 两点 ：
第一点：
每个结点的值的含义！
第二点：
lazy_tag的灵活运用！
其实第二点暂时大家还看不出来，咱们先来看看第一点！假设我们是要求区间最值，咱就可以设结点的值是当前结点表示的区间的最值。回到之前的图，如下：
假设我们是要寻求区间：[3, 7]的最值，如果按照以往的 “暴力法” 求解的话，我们一共需要循环遍历至少 4 次！但是如果线段树上的每个结点都有一个值，它代表了其所在区间的最值，我们就会如何处理这个问题呢？？？
线段树求RMQ问题如下：
首先从根节点开始查询，根节点是 [1, 10]，很明显我们要的区间没有完全包括 [1, 10]，所以需要继续往下查询，往左一直找到 [1, 3]，然后发现它的左区间已经和目标区间没有交集了，但是右区间有，所以得到 [3, 3]的值，然后看右区间，往右查到[4, 5]，发现该区间全部包含在目标区间里面了，我们知道了 [4, 5] 这么整个区间的最值， 就无需继续查找了，然后继续看，根节点的右子树有区间 [6, 7]，发现也正好包含在目标区间里面，于是我们就只需要比较得到 Max{ [3, 3] , [4, 5] , [6, 7] } 就可以得到目标区间的最值了！
这样操作，查找出所有区间需要的时间是：O(log(n))的，比起先前的暴力的O(n)要好太多了！
二、线段树解决实际问题
2.1、求解区间和问题
举个例子：我要查询数列 {1， 4， 5， 8， 6， 2， 3， 9， 10， 7}这个序列的某区间和，我就建立如下线段树：
比如我要查询区间 [3, 9] 这个区间的区间和，首先从根节点往左、右递归，知道某区间完全包含在目标区间里，比如：[3, 3]， [4, 5]，[6, 8]， [9, 9]，然后把这四个区间的和加起来，也就是：5 + 14 + 14 + 10 = 43
2.2、例题1 ： qhuoj-1878
这道题虽然数据量不大，用前缀和完全可以搞定，但是咱们还是用线段树来做吧，首先分析这个问题！！
就上述问题，做出线段树，约定树上结点的值是当前区间的和
首先确定数据结构：
const int maxn
= 1e4 + 5;
typedef long long ll
;
struct Tree
{
int l
, r
;
ll val
;
}tree
[maxn
<< 2];
千万要注意的是，线段树的空间要开 4 倍！！！！
然后是建立线段树
void build(int rt
, int l
, int r
)
{
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
if(l
== r
)
{
scanf("%lld", &tree
[rt
].val
);
return ;
}
int mid
= (l
+ r
) >> 1;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
tree
[rt
].val
= tree
[rt
<< 1].val
+ tree
[rt
<< 1 | 1].val
;
}
这里有几点非常需要注意：
第一：利用位运算，比直接加、乘速度快
第二：每次递归到叶子结点，也就是 l == r ,的时候，给叶子节点赋值，因为叶子节点的区间长度为 1，于是它的值就是数组的值
第三：递归到叶子结点后 return ；会回到上次调用的语句的下一句，也就是到了叶子结点的上面一层父节点，此时相当于 回溯 ！咱们可以在此更新叶子节点以上的所有结点的值（其实就是它们的子树的值之和！）
然后就是做区间查询了
void query(int rt
, int l
, int r
, int x
, int y
)
{
if (x
<= l
&& r
<= y
)
{
ans
+= tree
[rt
].val
;
return;
}
int mid
= (l
+ r
) >> 1;
if (x
<= mid
)
query(rt
<< 1, l
, mid
, x
, y
);
if (y
> mid
)
query(rt
<< 1 | 1, mid
+ 1, r
, x
, y
);
}
这里特别需要注意的地方有：
第一：线段树的一大优势，就是查询某种特征的值（此处是区间和），只需要查询到当前区间完全被目标区间包含了，那就直接取当前区间的值即可，无需继续递归！！
第二：之前忘了说了： rt << 1 = 2rt rt << 1 | 1 = 2rt + 1
第三：因为分出的子区间是：[l, mid] 和 [mid + 1, r]，所以条件是 : 若 x <= mid 则左子树还有满足要求的区间 若 y > mid 则右子树还有满足要求的区间！
整个的AC代码如下：
#include <cstdio>
const int maxn
= 1e4 + 5;
typedef long long ll
;
struct Tree
{
int l
, r
;
ll val
;
}tree
[maxn
<< 2];
ll ans
;
int n
, q
;
void build(int rt
, int l
, int r
)
{
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
if(l
== r
)
{
scanf("%lld", &tree
[rt
].val
);
return ;
}
int mid
= (l
+ r
) >> 1;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
tree
[rt
].val
= tree
[rt
<< 1].val
+ tree
[rt
<< 1 | 1].val
;
}
void query(int rt
, int l
, int r
, int x
, int y
)
{
if(x
<= l
&& r
<= y
)
{
ans
+= tree
[rt
].val
;
return ;
}
int mid
= (l
+ r
) >> 1;
if(x
<= mid
)
query(rt
<< 1, l
, mid
, x
, y
);
if(y
> mid
)
query(rt
<< 1 | 1, mid
+ 1, r
, x
, y
);
}
int main()
{
scanf("%d %d", &n
, &q
);
build(1, 1, n
);
while (q
--)
{
int x
, y
;
scanf("%d %d", &x
, &y
);
++x
, ++y
;
query(1, 1, n
, x
, y
);
printf("%lld\n", ans
);
ans
= 0;
}
return 0;
}
2.3、求解区间修改问题
如果要对区间进行修改，一种方法就是反复利用单点修改，一次单点修改的时间复杂度是O(log(n))，对整个区间修改是O(n * log(n))，然后加上 q 次操作，凉了！！！复杂度比暴力的平方级别还要高！！！如何解决这个问题呢？？？
之前我们提到了，如果当前结点代表的区间完全被目标区间包含，则该结点的值可以代表其结点下的所有子节点的值！于是我们考虑增设一个lazy_tag来表示该区间的一个修改状态！如果我们不破坏整个区间的结点一致性的话（一致性就是所有的点的修改一致），这个lazy_tag也就不变！！当我们增设了这个lazy_tag之后，我们相当于对区间整体进行了修改，只是它的子节点还不改，当需要改了再改，这也就是 ”懒惰标记“ 的解释！
2.3、区间查询+区间修改例题2
区间查询+区间修改（加操作）模板题；洛谷3372
此题的AC代码：
#include <cstdio>
typedef long long ll
;
const int maxn
= 1e5 + 5;
struct Tree
{
int l
, r
;
ll val
, lazy_tag
;
}tree
[maxn
<< 2];
int n
, q
;
ll ans
;
void push_up(int rt
)
{
tree
[rt
].val
= tree
[rt
<< 1].val
+ tree
[rt
<< 1 | 1].val
;
}
void build(int rt
, int l
, int r
)
{
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
tree
[rt
].lazy_tag
= 0;
if(l
== r
)
{
scanf("%lld", &tree
[rt
].val
);
return ;
}
int mid
= (l
+ r
) >> 1;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
push_up(rt
);
}
void push_down(int rt
)
{
if(tree
[rt
].lazy_tag
)
{
tree
[rt
<< 1].lazy_tag
+= tree
[rt
].lazy_tag
;
tree
[rt
<< 1 | 1].lazy_tag
+= tree
[rt
].lazy_tag
;
tree
[rt
<< 1].val
+= (tree
[rt
<< 1].r
- tree
[rt
<< 1].l
+ 1) * tree
[rt
].lazy_tag
;
tree
[rt
<< 1 | 1].val
+= (tree
[rt
<< 1 | 1].r
- tree
[rt
<< 1 | 1].l
+ 1) * tree
[rt
].lazy_tag
;
tree
[rt
].lazy_tag
= 0;
}
}
void update(int rt
, int l
, int r
, int x
, int y
, int addVal
)
{
if(x
<= l
&& r
<= y
)
{
tree
[rt
].lazy_tag
+= addVal
;
tree
[rt
].val
+= (tree
[rt
].r
- tree
[rt
].l
+ 1) * addVal
;
return ;
}
push_down(rt
);
int mid
= (l
+ r
) >> 1;
if(x
<= mid
)
{
update(rt
<< 1, l
, mid
, x
, y
, addVal
);
}
if(y
> mid
)
{
update(rt
<< 1 | 1, mid
+ 1, r
, x
, y
, addVal
);
}
push_up(rt
);
}
void query(int rt
, int l
, int r
, int x
, int y
)
{
if(x
<= l
&& r
<= y
)
{
ans
+= tree
[rt
].val
;
return ;
}
push_down(rt
);
int mid
= (l
+ r
) >> 1;
if(x
<= mid
)
{
query(rt
<< 1, l
, mid
, x
, y
);
}
if(y
> mid
)
{
query(rt
<< 1 | 1, mid
+ 1, r
, x
, y
);
}
}
int main()
{
scanf("%d %d", &n
, &q
);
build(1, 1, n
);
while (q
--)
{
int cmd
, x
, y
;
scanf("%d %d %d", &cmd
, &x
, &y
);
if(1 == cmd
)
{
int k
;
scanf("%d", &k
);
update(1, 1, n
, x
, y
, k
);
}
else
{
query(1, 1, n
, x
, y
);
printf("%lld\n", ans
);
ans
= 0;
}
}
return 0;
}
算法解析：
当我们用区间修改（加法）的时候，增设一个add标记lazy_tag，表示当前区间都得加多少。于是，我们建树的时候就得初始化这个值为 0，因为在我们还没update的时候，各个区间要增加的值是 0 ！然后当我们update的时候，这个lazy值也是可能累计的！因为也许上次修改和下次修改都没破坏一致性，所以这个lazy要累积，等到破坏的时候再传给下面的子节点！
那么，什么算是破坏了一致性呢？？？
如果你给区间[4, 5]修改，它的lazy_tag增加了，然后你又修改[5, 7]，此时有交集了吧，你由于lazy的特性，只给[4, 5]加了lazy_tag，但是没有给[5, 5]增加，但是你此时给[5, 7]增加，你的线段树会一直递归到[5, 5]，然后给它改变lazy_tag！！！此时很危险的事情就发生了，因为此时你的[5, 5]没有计算先前 [4, 5]的改变量！！！
那么，如何解决这个问题呢？？？？
思考问题的本源，其实是因为此次的update没有考虑到上一次的update的影响！！！所以我们要在对某区间实施update之前，在父节点有lazy_tag的时候，给它的子节点传去lazy_tag的值！！！这就是push_down()函数的妙用！
2.4、区间修改的操作是乘法的时候，例题3
区间查询+区间修改（乘法）；洛谷3373
本题的AC代码：
#include <cstdio>
typedef long long ll
;
const int maxn
= 1e5 + 5;
struct Tree
{
int l
, r
;
ll val
, lazy_add
, lazy_mul
;
}tree
[maxn
<< 2];
int n
, q
, p
;
ll ans
;
void push_up(int rt
)
{
tree
[rt
].val
= (tree
[rt
<< 1].val
+ tree
[rt
<< 1 | 1].val
) % p
;
}
void push_down(int rt
)
{
int lc_l
= tree
[rt
<< 1].l
, lc_r
= tree
[rt
<< 1].r
;
int rc_l
= tree
[rt
<< 1 | 1].l
, rc_r
= tree
[rt
<< 1 | 1].r
;
ll pmul
= tree
[rt
].lazy_mul
;
ll padd
= tree
[rt
].lazy_add
;
tree
[rt
<< 1].val
= (tree
[rt
<< 1].val
* pmul
+ (lc_r
- lc_l
+ 1) * padd
) % p
;
tree
[rt
<< 1 | 1].val
= (tree
[rt
<< 1 | 1].val
* pmul
+ (rc_r
- rc_l
+ 1) * padd
) % p
;
tree
[rt
<< 1].lazy_add
= (tree
[rt
<< 1].lazy_add
* pmul
+ padd
) % p
;
tree
[rt
<< 1 | 1].lazy_add
= (tree
[rt
<< 1 | 1].lazy_add
* pmul
+ padd
) % p
;
tree
[rt
<< 1].lazy_mul
= (tree
[rt
<< 1].lazy_mul
* pmul
) % p
;
tree
[rt
<< 1 | 1].lazy_mul
= (tree
[rt
<< 1 | 1].lazy_mul
* pmul
) % p
;
tree
[rt
].lazy_add
= 0;
tree
[rt
].lazy_mul
= 1;
}
void build(int rt
, int l
, int r
)
{
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
tree
[rt
].lazy_add
= 0;
tree
[rt
].lazy_mul
= 1;
if(l
== r
)
{
scanf("%lld", &tree
[rt
].val
);
return ;
}
int mid
= (l
+ r
) >> 1;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
push_up(rt
);
}
void update_add(int rt
, int l
, int r
, int x
, int y
, ll addVal
)
{
if(x
<= l
&& r
<= y
)
{
tree
[rt
].lazy_add
= (tree
[rt
].lazy_add
+ addVal
) % p
;
tree
[rt
].val
= (tree
[rt
].val
+ (tree
[rt
].r
- tree
[rt
].l
+ 1) * addVal
) % p
;
return ;
}
push_down(rt
);
int mid
= (l
+ r
) >> 1;
if(x
<= mid
)
update_add(rt
<< 1, l
, mid
, x
, y
, addVal
);
if(y
> mid
)
update_add(rt
<< 1 | 1, mid
+ 1, r
, x
, y
, addVal
);
push_up(rt
);
}
void update_mul(int rt
, int l
, int r
, int x
, int y
, ll mulVal
)
{
if(x
<= l
&& r
<= y
)
{
tree
[rt
].lazy_mul
= tree
[rt
].lazy_mul
* mulVal
% p
;
tree
[rt
].lazy_add
= tree
[rt
].lazy_add
* mulVal
% p
;
tree
[rt
].val
= tree
[rt
].val
* mulVal
% p
;
return ;
}
push_down(rt
);
int mid
= (l
+ r
) >> 1;
if(x
<= mid
)
update_mul(rt
<< 1, l
, mid
, x
, y
, mulVal
);
if(y
> mid
)
update_mul(rt
<< 1 | 1, mid
+ 1, r
, x
, y
, mulVal
);
push_up(rt
);
}
void query(int rt
, int l
, int r
, int x
, int y
)
{
if(x
<= l
&& r
<= y
)
{
ans
= (ans
+ tree
[rt
].val
) % p
;
return ;
}
push_down(rt
);
int mid
= (l
+ r
) >> 1;
if(x
<= mid
)
query(rt
<< 1, l
, mid
, x
, y
);
if(y
> mid
)
query(rt
<< 1 | 1, mid
+ 1, r
, x
, y
);
}
int main()
{
scanf("%d %d %d", &n
, &q
, &p
);
build(1, 1, n
);
while (q
--)
{
int cmd
, x
, y
;
scanf("%d %d %d", &cmd
, &x
, &y
);
if(1 == cmd
)
{
ll k
;
scanf("%lld", &k
);
update_mul(1, 1, n
, x
, y
, k
);
}
else if(2 == cmd
)
{
ll k
;
scanf("%lld", &k
);
update_add(1, 1, n
, x
, y
, k
);
}
else if(3 == cmd
)
{
query(1, 1, n
, x
, y
);
printf("%lld\n", ans
% p
);
ans
= 0;
}
}
return 0;
}
算法解析：
此处重点讲解乘法！！
如果我们要对区间的元素做乘法，我们增设一个lazy_mul的标签，如果我当前递归到的区间完全被目标区间覆盖，那么当前区间就可以作为其子区间所有结点的代表！但是，我们不光要考虑乘法，乘法还会影响加法！！！
如果此时lazy_add标签有值，说明此前有过区间加法的操作，然后你再进行区间乘，你想想看，是不是这个加法标签也要乘以这个乘法的倍数！因为你是先加后乘的！
但是，如果你是区间加法操作，就不需要考虑先前有无乘法，因为，即便是先前有乘法，那也对你的加法没有影响！！！
而且在push_down()操作的时候也要注意！！！因为你的push_down是发生在破坏一致性之前的，如果此时加法、乘法标签都有值，是需要把这些值带给子区间的影响传递下去的！
需要注意的是，由于我们的加法已经是乘上了倍数的，所以在push_down()的时候，是对value进行乘法，然后再加，但是其实这个不是先乘后加，而是先加后乘，只是那个加法已经乘过了！！！
三、线段树的基本应用
例题4：
题目大意：
有一块h * w的宣传板，给你 n 个广告，这些广告高都是1，但是宽各有不同，但是在贴广告的时候，尽可能往高处贴，问你每个广告最后贴好的高度是多少？？如果贴不下就输出-1！
算法分析：
这题给 [1, h] 划分线段树，每个结点的值是当前区间的最宽长度。思路是尽可能访问左子树，如果左子树实在贴不下，再考虑右子树。然后动态、单点修改线段树，这个单点修改就是每次贴上之后，把当前结点的值减少，减去当前广告的宽度！然后要维护这个最值，说白了，这题就是一个线段树区间最值、单点修改、贪心（尽可能往左子树靠）
AC代码：
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
typedef long long ll
;
const int maxn
= 1e5 + 5;
ll h
, w
, perW
, ans
;
int n
;
struct Tree
{
ll tmax
, l
, r
;
}tree
[maxn
<< 2];
inline ll
Max(ll a
, ll b
) {
return a
> b
? a
: b
;
}
void build(ll rt
, ll l
, ll r
) {
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
tree
[rt
].tmax
= w
;
if (l
== r
)
return;
ll mid
= (r
- l
) / 2 + l
;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
}
void find(ll rt
, ll l
, ll r
, ll req
) {
if (l
== r
) {
if (tree
[rt
].tmax
>= req
) {
tree
[rt
].tmax
-= req
;
ans
= l
;
return;
}
}
ll mid
= (r
- l
) / 2 + l
;
if (tree
[rt
<< 1].tmax
>= req
)
find(rt
<< 1, l
, mid
, req
);
else
find(rt
<< 1 | 1, mid
+ 1, r
, req
);
tree
[rt
].tmax
= Max(tree
[rt
<< 1].tmax
, tree
[rt
<< 1 | 1].tmax
);
}
int main() {
while (~scanf("%lld %lld %d", &h
, &w
, &n
)) {
if (h
> n
)
h
= n
;
build(1, 1, h
);
for (int i
= 1; i
<= n
; ++i
) {
scanf("%lld", &perW
);
if (tree
[1].tmax
< perW
) {
printf("-1\n");
continue;
}
find(1, 1, h
, perW
);
printf("%lld\n", ans
);
ans
= 0;
}
}
return 0;
}
需要注意的点
这里需要注意一下，我们贴广告，必须要递归到叶子节点为止，因为广告的高度是1，你一个广告不可能占据一个区间，所以递归出口是 l == r
四、离散化算法
线段树的空间要开 4 倍，在很多问题中，会遇到空间不够的情况！
但是吧，线段树解决的往往是区间问题，区间问题一般是离散的，不会每个区间都紧挨着，所以我们往往需要进行离散化，再建立线段树！！！
4.1、什么是离散化？
当我们只关心数据之间的大小关系，而不关心实际大小的时候，可以用排名代替其具体值的一种预处理方法！
其实离散化的本质是一种哈希算法，我们把一些难以作为数组下标的数，比如很大的数、小数、负数等数映射成大小关系不变的，规模较小的整数。比如在线段树中，如果区间的长度过长，那么tree数组必然是放不下去的！！！那么就需要离散化了！
4.2、举一个离散化的小例子
比如我们有数组： {-1008, 1, 2, 180000000000, 20, 30, 5}， 给他们排序后是： {-1008，1，2，5，20，30，180000000000} 它们的下标是： {1， 2， 3， 4， 5， 6， 7} 于是我们可以让原数组变成： {1，2，7，5，6，4} 这样这些数据就能增大空间的利用率，比如把它们变成下标之类的！
4.3、离散化的一般步骤
第一步：
排序
第二步：
去重
第三步：
索引（我比较喜欢二分，空间复杂度O(1)，时间复杂度O(n*log(n))）
4.4、代码描述数组离散化、区间离散化
数组离散化：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std
;
int main()
{
int a
[] = { -108, 1, 2, 3845, 6, 10, 4, 4, 6 };
int cp
[15];
memcpy(cp
, a
, 9 * sizeof(int));
sort(cp
, cp
+ 9);
int cnt
= int(unique(cp
, cp
+ 9) - cp
);
for (int i
= 0; i
< 9; ++i
)
{
a
[i
] = int(lower_bound(cp
, cp
+ cnt
, a
[i
]) - cp
+ 1);
}
for (int i
= 0; i
< 9; ++i
)
{
cout
<< a
[i
] << ' ';
}
return 0;
}
离散化后的结果：
区间离散化：
struct Interval
{
int x
, y
;
}Int
[maxn
<< 2];
int Ele
[maxn
<< 2], cnt
, n
;
scanf("%d", &n
);
for (int i
= 1; i
<= n
; ++i
) {
scanf("%d %d", &Int
[i
].x
, &Int
[i
].y
);
Ele
[++cnt
] = Int
[i
].x
;
Ele
[++cnt
] = Int
[i
].y
;
}
sort(Ele
, Ele
+ cnt
);
cnt
= int(unique(Ele
+ 1, Ele
+ 1 + cnt
) - Ele
);
for (int i
= 1; i
<= n
; ++i
) {
Int
[i
].x
= int(lower_bound(Ele
+ 1, Ele
+ 1 + cnt
, Int
[i
].x
) - Ele
);
Int
[i
].y
= int(lower_bound(Ele
+ 1, Ele
+ 1 + cnt
, Int
[i
].y
) - Ele
);
}
4.4、离散化+线段树例题5
poj 2528 询问宣传栏上能够看到的广告数目
题目大意：
这题说的是，宣传栏上铺设广告牌，广告牌之间可以相互遮挡，问你最后能看到几种广告牌？
算法分析：
设置 id 表示当前区间的广告牌种类是否确定，如果确定就是1 ，否则就是 0（不确定的含义是：当前区间有多种广告牌，也可能没有广告牌！）然后进行区间查询，如果当前区间的广告种类唯一确定，那么它下面的子区间也一定确定！！！
有n次输入，就是有n种牌子，那么这个id就是从 1 到 n 了！每次 update，更新一些结点的id，当前结点下的区间全在目标区间下，则当前结点的id就是当前的牌子id！然后查询的时候，就是设置 bool 数组，查询 id 确定的结点（也就是当前区间就只有这么个牌子，没被遮挡！）然后查到了就做记录，避免重复计算！！！
AC代码：
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std
;
const int maxn
= 10005;
struct Tree
{
int id
, l
, r
;
}tree
[maxn
<< 4];
struct Interval
{
int x
, y
;
}Int
[maxn
<< 2];
int Ele
[maxn
<< 2], cnt
, ans
;
bool isVis
[maxn
<< 2];
void build(int rt
, int l
, int r
) {
tree
[rt
].l
= l
, tree
[rt
].r
= r
;
tree
[rt
].id
= 0;
if (l
== r
)
return;
int mid
= (l
+ r
) >> 1;
build(rt
<< 1, l
, mid
);
build(rt
<< 1 | 1, mid
+ 1, r
);
}
void push_down(int rt
) {
if (tree
[rt
].id
) {
tree
[rt
<< 1].id
= tree
[rt
].id
;
tree
[rt
<< 1 | 1].id
= tree
[rt
].id
;
tree
[rt
].id
= 0;
}
}
void update(int rt
, int l
, int r
, int x
, int y
, int NewId
) {
if (x
<= l
&& r
<= y
) {
tree
[rt
].id
= NewId
;
return;
}
push_down(rt
);
int mid
= (l
+ r
) >> 1;
if (x
<= mid
)
update(rt
<< 1, l
, mid
, x
, y
, NewId
);
if (y
> mid
)
update(rt
<< 1 | 1, mid
+ 1, r
, x
, y
, NewId
);
}
void query(int rt
, int l
, int r
) {
if (l
== r
&& !tree
[rt
].id
)
return;
if (tree
[rt
].id
) {
if (!isVis
[tree
[rt
].id
]) {
ans
++;
isVis
[tree
[rt
].id
] = true;
}
return;
}
int mid
= (l
+ r
) >> 1;
query(rt
<< 1, l
, mid
);
query(rt
<< 1 | 1, mid
+ 1, r
);
}
int main() {
int Tcase
, n
;
scanf("%d", &Tcase
);
while (Tcase
--) {
scanf("%d", &n
);
for (int i
= 1; i
<= n
; ++i
) {
scanf("%d %d", &Int
[i
].x
, &Int
[i
].y
);
Ele
[++cnt
] = Int
[i
].x
;
Ele
[++cnt
] = Int
[i
].y
;
isVis
[i
] = false;
}
sort(Ele
+ 1, Ele
+ 1 + cnt
);
int size_
= cnt
<< 1;
cnt
= int(unique(Ele
+ 1, Ele
+ 1 + cnt
) - Ele
);
for (int i
= 1; i
<= n
; ++i
) {
Int
[i
].x
= int(lower_bound(Ele
+ 1, Ele
+ 1 + cnt
, Int
[i
].x
) - Ele
);
Int
[i
].y
= int(lower_bound(Ele
+ 1, Ele
+ 1 + cnt
, Int
[i
].y
) - Ele
);
}
build(1, 1, size_
);
for (int i
= 1; i
<= n
; ++i
)
update(1, 1, size_
, Int
[i
].x
, Int
[i
].y
, i
);
query(1, 1, size_
);
printf("%d\n", ans
);
ans
= 0;
cnt
= 0;
}
return 0;
}
五、致谢与写在后面的话
本文参考资料： ①《算法竞赛入门到进阶》——罗勇军老师 ② 罗勇军老师的博客，写的很好！
立flag： 明天做一些灵活一点的，线段树的变种题目！！！！
