【题目描述:】

/*
飞逝的的时光不会模糊我对你的记忆。难以相信从我第一次见到你以来已经过去了3年。我仍然还生动地记得,3年前,在美丽的集美中学,从我看到你微笑着走出教室,你将头向后仰,柔和的晚霞照耀着你玫瑰色的脸颊。我明白,我已经沉醉于你了。之后,经过几个月的观察和窥探,你的优雅与智慧,你对待生活的态度和你对未来的愿望深切地在我心中留下了印象。你是迷人的阳光女孩,我总是梦想着与你分享余生。唉,实际上你远远超过了我最疯狂的梦想。我不知道如何桥起我与你之间的鸿沟。所以我没有任何计划,仅仅只是等待,等待一个适当的机会到来。直到现在,毕业的到来,我意识到我是个傻瓜,我应该创造机会并且抓住它而不只是等待。 这些日子里,我和我的朋友、室友、同学一个接一个地分开。我仍无法相信,在挥手之后,这些熟悉的面孔很快就会从我们的生活中消失,仅仅留下回忆。我明天就将离开学校。你已经计划远走高飞,追求你的未来,实现你的梦想。如果没有命运,也许我们不会再次相遇。所以今晚,我正在你的宿舍楼下徘徊,希望能偶然遇见你。但矛盾的是,你的美貌一定会使我心跳加速,我笨拙的舌头也许无法吐出一个字。我不记得我曾多少次经过你的宿舍楼,每次都希望看到你出现在阳台上或是窗台上。我不记得这个想法曾多少次在我的脑海中涌出:打电话叫她一起吃晚饭或是聊聊天。但每次,考虑到你的优秀和我的平凡,胆怯的优势超越勇气驱使我静静地离开。 毕业,意味着中学生活的终结。这些光荣与浪漫的时代结束。你可爱的微笑是我原来努力学习的动力,这单相思的爱情会被密封,作为一个我心灵深处的记忆。毕业,也意味着新生活的开始,一个到达光明未来的足迹。我真希望你在国外天天开心,一切顺利。同时,我将努力从幼稚中走出来,变得更加成熟。我的理想将是在现实中追求我的爱与幸福,我永远不会放弃。 再见了,我的公主! 如果有一天,在某个天涯海角,我们有机会相聚,即使是白发苍苍的男人和女人,在那个时候,我希望我们可以成为好朋友来自豪地分享这个记忆,重温年轻快乐的激情。如果这个机会永远没有到来,我希望我是天空中的星星,在你的窗外闪烁。远远地保佑着你,就像一个朋友,每天晚上陪伴在你左右,一同分享甜美的梦亦或是一同经历可怕的梦。
*/

题目背景

天空可以理解为一条数轴,在这条数轴上分布着许多颗星星,对于每颗星星都有它的位置Xi和自身的亮度Bi。而窗户所能看到的范围是一个给出的参数W,我们看到的星星也包括窗户边缘的星星。现在,要你求出调整窗户位置后能看到星星的亮度之和最大值。

【输入格式:】

一行N,W,分别代表星星的数量和窗户的宽度

余下N行,输入Xi和Bi,代表星星的坐标和亮度

【输出格式:】

一个数字,代表能看到星星的最大亮度和

输入样例#: 

输出样例#:

输入输出样例

【算法分析:】

这是一道统计题,不需要支持修改完全可以那前缀和做

但是为了练习线段树,还是写线段树吧

询问区间和,区间长度为w,枚举每一个w区间并快速地求出[i, i + w - 1]的元素和,可以通过线段树来实现。

对于一开始读入的x, b,可以通过单点修改使 a[x] += b

所以用单点修改区间查询的线段树,时间复杂度O((n - w) log2 n)

【代码:】

 //在你窗外闪耀的星星
#include<iostream>
#include<cstdio>
using namespace std; const int MAXN = + ; int n, w;
int tree[MAXN << ]; void Update(int o, int l, int r, int p, int v) {
if(l == r) tree[o] += v;
else {
int mid = (l + r) >> ;
if(l <= p && p <= mid) Update(o << , l, mid, p, v);
else Update(o << |, mid + , r, p, v);
tree[o] = tree[o << ] + tree[o << |];
}
}
long long Query(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return tree[o];
int mid = (l + r) >> ;
long long ret = ;
if(ql <= mid) ret += Query(o << , l, mid, ql, qr);
if(qr > mid) ret += Query(o << |, mid + , r, ql, qr);
return ret;
}
int main() {
scanf("%d%d", &n, &w);
if(w == ) { puts(""); return ; }
for(int i = ; i <= n; ++i) {
int pos, num;
scanf("%d%d", &pos, &num);
Update(, , n, pos, num);
}
long long ans = ;
for(int i = , j = w; j <= n; ++i, ++j) {
ans = max(ans, Query(, , n, i, j));
}
printf("%lld\n", ans);
}

最新文章

  1. Linux安装mariadb二进制版本
  2. 1219 spring3 项目总结
  3. innodb buffer pool小解
  4. vs xamarin android StartActivity
  5. there is issue about change event of checkbox in the ie8 oe ie7
  6. 一文彻底了解join的各种用法
  7. Session的SqlServer模式的配置
  8. 欧几里得证明$\sqrt{2}$是无理数
  9. 全面整理的C++面试题
  10. Fast Intro To Java Programming (1)
  11. Powershell 设置数值格式 1
  12. maven学习2,安装插件
  13. MySQL-InnoDB引擎
  14. (原创)(三)机器学习笔记之Scikit Learn的线性回归模型初探
  15. 关于如何在微信里面让video不全屏播放
  16. a标签文字选中后的颜色样式更改
  17. Vim保存时权限不足
  18. 四十、Linux 线程——互斥锁和读写锁
  19. 如何构造分层次的 Json 数据
  20. Hive分区表新增字段及修改表名,列名,列注释,表注释,增加列,调整列顺序,属性名等操作

热门文章

  1. git 拉取远程分支报错(fatal: &#39;&#39; is not a commit and a branch &#39;&#39; cannot be created from it)
  2. 面向对象(static关键字的特点)
  3. Spring系列之——Spring事务以及两大核心IOC和AOP
  4. ORACLE数据库数据的备份与恢复
  5. &lt;!DOCTYPE html&gt;声明下div高度100%
  6. CentOS /lib/ld-linux.so.2: bad ELF interpreter: No such file or directory
  7. Java 实验案例(多态)
  8. linux系统下安装ssl证书(tomcat)
  9. Android MVP模式就是这么回事儿
  10. ArrayMap代替HashMap