hdu1556 线段树段更新(简单题)
简单 更新 线段
2023-09-11 14:14:00 时间
题意:
N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?
思路:
这个题目可以用线段树来做,可以用线段树的段更新点询问,每次把a,b全部+1,最后全部查询一遍就行了,水题不解释,不理解直接看代码。
#include<stdio.h> #include<string.h> #define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1 __int64 sum[440000] ,mark[440000]; void Pushup(int t) { sum[t] = sum[t<<1] + sum[t<<1|1]; } void Pushdown(int t ,int ll) { if(mark[t]) { mark[t<<1] += mark[t]; mark[t<<1|1] += mark[t]; sum[t<<1] += (ll - (ll >> 1)) * mark[t]; sum[t<<1|1] += (ll >> 1) * mark[t]; mark[t] = 0; } } void BuidTree() { memset(sum ,0 ,sizeof(sum)); memset(mark ,0 ,sizeof(mark)); } void Update(int l ,int r ,int t ,int a ,int b ,int c) { if(a <= l && b >= r) { sum[t] += (r - l + 1) * c; mark[t] += c; return; } Pushdown(t ,r - l + 1); int mid = (l + r) >> 1; if(a <= mid) Update(lson ,a ,b ,c); if(b > mid) Update(rson ,a ,b ,c); Pushup(t); } __int64 Query(int l ,int r ,int t ,int a ,int b) { if(a <= l && b >= r) return sum[t]; Pushdown(t ,r - l + 1); int mid = (l + r) >> 1; __int64 ans = 0; if(a <= mid) ans = Query(lson ,a ,b); if(b > mid) ans += Query(rson ,a ,b); return ans; } int main () { int n ,a ,b ,i; while(~scanf("%d" ,&n) && n) { BuidTree(); for(i = 1 ;i <= n ;i ++) { scanf("%d %d" ,&a ,&b); Update(1 ,n ,1 ,a ,b ,1); } for(i = 1 ;i <= n ;i ++) if(i == n) printf("%I64d\n" ,Query(1 ,n ,1 ,i ,i)); else printf("%I64d " ,Query(1 ,n ,1 ,i ,i)); } return 0; }
相关文章
- 用简单的代码,看懂 CPU 背后的重要机制
- 简单而直接的Python web 框架:web.py
- 图片无限轮播-最简单的实现方法
- C#一个简单下载程序实例(可用于更新)
- 最简单的加密---异或加密
- iBatis简单入门教程
- 极大似然估计思想的最简单解释
- Python3的简单语法与常用库(慢慢更新中)
- 大数据学习——kettle的简单使用
- Qt Model/View理解(二)---构造model(细心研读,发现超简单,Model就是做三件事:返回行数量、列数量、data如何显示。然后把model与view联系起来即可,两个例子都是如此)good
- Unity 进阶 之 UGUI 实现动态数据动态翻页显示效果的简单封装(动态更新数据动态更新显示,包括页码和按钮事件等功能)
- Three 之 three.js (webgl)绘制物体模型尺寸虚线包围框工具简单封装 DashLinesBoxTool
- MySql_安装及简单命令
- git fetch 的简单用法:更新远程代码到本地仓库及冲突处理
- 【Unity Shader】纹理实践4.0:简单尝试渐变纹理和遮罩纹理