SSL-ZYC 2645 线段树练习题二

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

题目大意：
从左往右，从前往后给出n条颜色不同的线段，求最后能看见的线段数量。

思路:

线段树

tree[x]的用处与线段树练习一的用处基本相同，但是tree[x].cover表示的是tree[x].l与tree[x].r之间的线段颜色（没有线段或有多种颜色就为0）

代码的区别就在于插入，建树和计算基本没变化。

代码：

#include <cstdio>
#include <iostream>
using namespace std;int n,m,color[300001],x,y,sum;struct N
{int l,r,cover;
}tree[300001];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 col,int l,int r)
{if (tree[x].cover==col) return;  //这一段已经是要涂的颜色就退出，不必再涂。if (l==tree[x].l&&r==tree[x].r)  //找到这一段{tree[x].cover=col;return;}if (tree[x].cover>0)   //这一段已经涂了其他颜色{tree[x*2].cover=tree[x*2+1].cover=tree[x].cover;  //儿子的颜色为该段的颜色tree[x].cover=0;  //这段有多种颜色，赋值为0}int mid=(tree[x].l+tree[x].r)/2;if (mid>=r)  //完全在左边{insert(x*2,col,l,r);return;}if (mid<=l)  //完全在右边{insert(x*2+1,col,l,r);return;}insert(x*2,col,l,mid);insert(x*2+1,col,mid,r);  //两边都有
}  void count(int x)
{if (tree[x].cover>0&&color[tree[x].cover]==0)   //没有计算过这种颜色{color[tree[x].cover]=1;  sum++;return;}if (tree[x].cover>0) return;  if (tree[x].r<=tree[x].l+1) 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,i,x,y);  //插入}count(1);printf("%d\n",sum);return 0;
}