题目链接

题意:成段染色,初始为0,每次改变一个区间的颜色,求最后每种颜色分别有多少段。颜色按照从

小到大输出。

分析:改变了代码的风格,因为看了学长的博客。直接用数组,可以只是记录节点的编号,因为节点编号

确定了,则l,r也就确定了。

 #include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL __int64
#define lson l, mid, 2*rt
#define rson mid+1, r, 2*rt+1
const int maxn = +;
using namespace std;
int val[*maxn], num[maxn]; void pushdown(int rt) //如果没有更新,向下更新
{
if(val[rt]!=-)
{
val[*rt] = val[rt];
val[*rt+] = val[rt];
val[rt] = -;
}
}
void update(int ll, int rr, int c, int l, int r, int rt) //ll,rr代表要找的区间,不用减小了,一直都是这个
{
if(ll<=l && rr>=r) //如果当前节点的范围在 改变的节点的范围内就 改变
{
val[rt] = c;
return;
}
pushdown(rt);
int mid = (l+r)/;
if(ll<=mid) update(ll, rr, c, lson); //看这个左半区间内是否还有点
if(rr>mid) update(ll, rr, c, rson);
}
int query(int p, int l, int r, int rt)
{
if(l>p) return ;
if(r<p) return ;
if(p==l&&p==r) return val[rt];
if(p>=l && p<=r && val[rt]!=-) return val[rt];
int mid = (l+r)/;
return query(p, lson)+query(p, rson);
}
int main()
{
int i, n, l, r, c, x, pre;
while(~scanf("%d", &n))
{
memset(val, -, sizeof(val)); //相当于建树
memset(num, , sizeof(num));
while(n--)
{
scanf("%d%d%d", &l, &r, &c);
if(r- >= l)
update(l, r-, c, , , );
}
pre = -;
for(i = ; i <= ; i++) //查询的是区间00,11.。。
{
x = query(i, , , );
if(x!=pre) //如果不连续 就加上
{
pre = x;
if(x>=) num[x]++;
}
}
for(i = ; i <= ; i++)
{
if(num[i])
printf("%d %d\n", i, num[i]);
}
printf("\n");
}
return ;
}

最新文章

  1. PHP中curl_init函数用法
  2. Java连接SQLServer2008终极解决办法(亲身上机演练版)
  3. 游戏引擎PushButtonEngine简介
  4. How to use kingshard building a MySQL cluster
  5. Xen虚拟机磁盘镜像模板制作(二)—Windows Server 2008(2012)
  6. 设计模式Day02
  7. string string.h=cstring=str
  8. SQL Server 判断表中是否存在某字段
  9. SPOJ839 OPTM - Optimal Marks
  10. Tesseract pytesseract的安装和使用
  11. KVM之十:虚拟机在线添加网卡
  12. 安卓图片Bitmap一些旋转处理
  13. Linux/Ubuntu 16.04 好用的视频播放器 SMPlayer
  14. 《JAVA程序设计》结对编程联系_四则运算(第二周:整体性总结)
  15. ckeditor 在dwz里面使用
  16. Linux 内核的定时机制实验
  17. vue-form表单验证插件
  18. C语言对文件的基本操作
  19. 利用git向github中推送文件
  20. asterisk channel driver dev ref

热门文章

  1. 二分查找or折半查找
  2. DVDRW光驱无法读DVD刻录盘
  3. Qt html 界面混合编程
  4. SiteMesh3 介绍和使用
  5. 1021 玛丽卡 - Wikioi
  6. Codeforces Round #347 (Div. 2) C. International Olympiad 找规律
  7. SQL SERVER调优常用方法
  8. Matlab找二维数组最大值
  9. 剑指offer--面试题5
  10. mysql之sql语句导入与导出讲解