题目真的好甜呢QwQ

冲着这题面也要来做


满分解法:线段树

我们暴力地把所有点建成一颗线段数

接着在从1到maxx里每个长度为 w的区间中执行区间求和

其实单点修改都不需要,可以在输入的时候统计出每个点上星星的亮度和

另:同一点上可能有多个星星

#include<bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
using namespace std;
#define maxn 100009
struct node{
int l,r,val;
}tr[maxn*];
int n;
int a[maxn];
void Buildtree(int x,int l,int r)
{
tr[x].l=l;
tr[x].r=r;
if(l==r)
{
tr[x].val=a[l];
return;
}
int mid=(l+r)>>;
Buildtree(x*,l,mid);
Buildtree(x*+,mid+,r);
tr[x].val=tr[x*].val+tr[x*+].val;
}
int Query(int x,int l,int r)
{
if(l<=tr[x].l&&tr[x].r<=r)
{
return tr[x].val;
}
int mid=(tr[x].l+tr[x].r)/;
int ans=;
if(l<=mid) ans+=Query(x*,l,r);
if(r>mid) ans+=Query(x*+,l,r);
return ans;
}
int main()
{
int maxx=;
int w;
scanf("%d%d",&n,&w);
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x]+=y;
maxx=max(maxx,x);
}
Buildtree(,,maxx);
//建树的范围是所有点,从1到最大点的位置 int ans=;
for(int i=;i<=maxx;i++)
{
ans=max(ans,Query(,i,i+w-));//记得w-1
/*
窗框算在W之内
W=3
框 星 框
| * |
------------------------
*/
}
printf("%d\n",ans);
return ;
}
 

最新文章

  1. VS2015 Git 源码管理工具简单入门
  2. 启动Tomcat报异常host-manager does not exist or is not a readable directory
  3. 【总结】总结写了3个React页面后遇到的各种坑
  4. CVTE实习面经
  5. codeforces 725D . Contest Balloons(贪心+优先队列)
  6. C/C++中函数参数传递详解(二)
  7. 敏捷开发之道(二)极限编程XP
  8. 远程控制篇:在DELPHI程序中拨号上网
  9. dtrace4linux
  10. Java中x+=y和x=x+y两种实现的区别
  11. 验证浏览器是否安装已flash插件的js脚本
  12. dva + antd + mockjs 实现基础用户管理
  13. studio中碰到的jni问题:java.lang.UnsatisfiedLinkError
  14. egret 添加帧动画
  15. vue监听滚动事件-元素固定位置显示
  16. Python对elasticsearch的CRUD
  17. faster rcnn 做识别
  18. MySQL5.7 虚拟列实现表达式或函数索引
  19. oj错误之char型超出范围
  20. 20155204 王昊《网络对抗技术》EXP2 后门原理与实践

热门文章

  1. JavaWeb_(Hibernate框架)Hibernate中数据查询语句SQL基本用法
  2. 8 HashMap
  3. Configure vyatta
  4. ansiblle---roles
  5. C#实现MJPEG服务器
  6. 【SR汇总】效果对比
  7. 埃利斯(A.Ellis)ABCDE情绪管理理论
  8. .SpringIOC容器
  9. 小D课堂-SpringBoot 2.x微信支付在线教育网站项目实战_2-5.开源工具的优缺点选择和抽象方法的建议
  10. tomcat简单快捷改端口