题意:二维平面上给你N颗星,给出星星的坐标,亮度; 然后给你一个W*H的窗口,问你最大的亮度和。

思路:扫描线,假设有一个inf*H的窗口,按照y排序,那么就把H范围内的星星放入了这个窗口(单调队列实现),现在就成了华东窗口问题,在一维数组里面找长度为W的窗口的最大和,但是现在带修改,单点修改,固定区间查询,怎么做呢? 和学生讨论了一下,常规的很难实现。 我们需要转化一下,把单点修改转化为区间修改,然后单点查询最大值。    如果x处插入L,则[x,Rx]区间加x。 ans=max(mx[1]);

(可以出一道,待修改的滑动窗口问题。

#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct in{
int x,y,l;
bool friend operator <(in w,in v){
return w.y<v.y;
}
}s[maxn];
int ans,W,H,lazy[maxn],mx[maxn];
int b[maxn],tot,p[maxn];
void pushdown(int Now)
{
if(!lazy[Now]) return ;
lazy[Now<<]+=lazy[Now]; lazy[Now<<|]+=lazy[Now];
mx[Now<<]+=lazy[Now]; mx[Now<<|]+=lazy[Now];
lazy[Now]=;
}
void add(int Now,int L,int R,int l,int r,int val)
{
if(l<=L&&r>=R){
mx[Now]+=val;
lazy[Now]+=val;
return ;
}
pushdown(Now); int Mid=(L+R)>>;
if(l<=Mid) add(Now<<,L,Mid,l,r,val);
if(r>Mid) add(Now<<|,Mid+,R,l,r,val);
mx[Now]=max(mx[Now<<],mx[Now<<|]);
}
int main()
{
int T,N;
while(~scanf("%d%d%d",&N,&W,&H)){
ans=; tot=;
rep(i,,N) scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].l);
sort(s+,s+N+);
rep(i,,N<<) lazy[i]=mx[i]=;
rep(i,,N) b[++tot]=s[i].x;
sort(b+,b+N+);
tot=unique(b+,b+N+)-(b+);
rep(i,,N) s[i].x=lower_bound(b+,b+tot+,s[i].x)-b;
int R=;
rep(i,,tot) {
while(R+<=tot&&b[R+]-b[i]+<=W) R++;
p[i]=R;
}
for(int i=,j=;i<=N;i++){
add(,,tot,s[i].x,p[s[i].x],s[i].l);
while(j<=i&&s[i].y-s[j].y+>H) {
add(,,tot,s[j].x,p[s[j].x],-s[j].l);
j++;
}
ans=max(ans,mx[]);
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. BZOJ 2127: happiness [最小割]
  2. java学习笔记(3)之面向对象(1)
  3. lua 位运算
  4. 理解nginx的配置
  5. linux 内核手动编译
  6. Android中Activity启动模式详解
  7. Linux下去掉^M的方法
  8. 09_httpclient测试SOAP协议
  9. python针对于mysql的增删改查
  10. 第九章 MySQL中LIMIT和NOT IN案例
  11. C语言第一次博客作业 陈张鑫
  12. Python_lambda
  13. AMH 软件目录介绍
  14. VS2015 代码片段整理
  15. Oracle服务器定位CPU使用率高的瓶颈(SQL)
  16. 使用FPM打包工具打rpm包
  17. Ftp命令使用
  18. 使用robot封装一个模拟键盘复制粘贴并按下回车的方法
  19. java指令备忘
  20. Yii框架2.0的Gii

热门文章

  1. 构建C1000K的服务器(1) – 基础
  2. MATLAB 代码规范
  3. Java多线程编程(1)--Java中的线程
  4. Spring Boot与mybatis整合
  5. swagger list Could not resolve reference because of: Could not resolve point
  6. MySQL和SQL Server一些基本用法区别
  7. np.minimum()与tf.minimum()的用法
  8. 自学Python编程的第三天----------来自苦逼的转行人
  9. 【开发工具】- Atom下载及安装
  10. slf4j的正确使用