【bzoj2422】 Times 前缀和
2024-09-25 01:18:10
本来想练一下树状数组的,看到网上某人的blog后点了进来。
第一眼发现不会,出去上了个厕所发现离散化后不是一道简单前缀和题吗。
考虑到每一个人出现且仅出现一次,且出现的时间是在一个连续的区间内。
那么对于一组询问(l,r),当这个人在时刻l前消失,或者再时刻l+r后出现,那么你才会看不到。
那么我们维护一个sum1[i],表示在时刻i及之前,出现过并且已经消失的人的数量。
维护一个sum2[i],表示在时刻i及之后才出现的人的数量。
答案显然是n-sum1[l-1]-sum2[l+r]。
然后就没了,空间记得开够!
#include<bits/stdc++.h>
#define M 200005
using namespace std; int c[M*]={},cnt=;
int a[M]={},b[M]={},l[M]={},r[M]={};
int sum1[M*]={},sum2[M*]={}; int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d%d",a+i,b+i);
b[i]+=a[i]-;
c[++cnt]=a[i];
c[++cnt]=b[i];
}
for(int i=;i<=m;i++){
scanf("%d%d",l+i,r+i);
r[i]+=l[i]-;
c[++cnt]=l[i];
c[++cnt]=r[i];
}
sort(c+,c+cnt+);
for(int i=;i<=n;i++)
a[i]=lower_bound(c+,c+cnt+,a[i])-c,
b[i]=lower_bound(c+,c+cnt+,b[i])-c;
for(int i=;i<=m;i++)
l[i]=lower_bound(c+,c+cnt+,l[i])-c,
r[i]=lower_bound(c+,c+cnt+,r[i])-c; for(int i=;i<=n;i++)
sum1[b[i]]++,sum2[a[i]]++;
for(int i=;i<=cnt;i++) sum1[i]+=sum1[i-];
for(int i=cnt;i;i--) sum2[i]+=sum2[i+]; for(int i=;i<=m;i++){
printf("%d\n",n-sum1[l[i]-]-sum2[r[i]+]);
}
}
最新文章
- 网络服务器之HTTPS服务
- windows svn 配置以及iis同步传送
- user-select : 保护版权内容的简单方案
- dojo 一 require 路径问题
- Java类的生命周期详解
- 【Android - 框架】之ButterKnife的使用
- [TypeScript] Inheritance
- ubuntu下安装postgres
- 去除除服串中的某些字符,不用String内置方法
- SUBSTRING_INDEX ——网上的解释
- MySQL主从复制的配置
- 腾讯面试:一条SQL语句执行得很慢的原因有哪些?---不看后悔系列
- 创建DVWA环境时遇到的问题
- 小甲鱼Python第九讲课后习题--010列表
- Core Java 面经
- 191. Number of 1 Bits (Int; Bit)
- Windows10内置Linux子系统
- SQL Server学习路径(文章目录)
- 10个CSS简写/优化技巧-摘自网友
- js基础学习笔记(五)
热门文章
- nodejs的优点
- 2018.09.09 bzoj4403: 序列统计(Lucas定理)
- POJ 3320 Jessica&#39;s Reading Problem (滑动窗口)
- “无后端”的web应用开发模式
- (线段树 点更新 区间求和)lightoj1112
- shell中的重定向(输入输出)
- 个人封装JavaScript函数
- CentOS搭建NFS服务
- 浏览器中调用PHP在执行linux sudo指令时报sudo: sorry, you must have a tty to run sudo
- [转载]将json字符串转换成json对象