【题意概述】

  给出一个[0,1,000,000,000]的整数数轴,刚开始每个位置都为0,有n个区间加操作,最后询问数轴上最大的数是多少。

【题解】

  我写的是离散化后线段树维护区间最值。

  其实貌似不用线段树QAQ...

#include<cstdio>
#include<algorithm>
#define N 400010
#define rg register
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((a[u].l+a[u].r)>>1)
using namespace std;
int n,ans,l[N],r[N],b[N];
struct tree{
int l,r,del,mx;
}a[N];
inline int read(){
int f=1,k=0; char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
inline int max(int a,int b){
return a>b?a:b;
}
inline void pushup(int u){
a[u].mx=max(a[ls].mx,a[rs].mx);
}
inline void pushdown(int u){
if(!a[u].del) return; int D=a[u].del; a[u].del=0;
a[ls].del+=D; a[ls].mx+=D;
a[rs].del+=D; a[rs].mx+=D;
}
void build(int u,int l,int r){
a[u].l=l; a[u].r=r; a[u].mx=0;
if(l<r) build(ls,l,mid),build(rs,mid+1,r);
}
void add(int u,int l,int r,int d){
if(l<=a[u].l&&a[u].r<=r){
a[u].del+=d; a[u].mx+=d; return;
}
pushdown(u);
if(l<=mid) add(ls,l,r,d);
if(r>mid) add(rs,l,r,d);
pushup(u);
}
int query(int u,int l,int r){
if(l<=a[u].l&&a[u].r<=r) return a[u].mx;
pushdown(u); int ret=0;
if(l<=mid) ret=query(ls,l,r);
if(r>mid) ret=max(ret,query(rs,l,r));
return ret;
}
int main(){
n=read();
for(rg int i=1;i<=n;i++){
l[i]=b[i]=read(); r[i]=b[i+n]=read();
}
sort(b+1,b+1+(n<<1)); int n2=unique(b+1,b+1+(n<<1))-b-1;
for(rg int i=1;i<=n;i++) l[i]=lower_bound(b+1,b+1+n2,l[i])-b;
for(rg int i=1;i<=n;i++) r[i]=lower_bound(b+1,b+1+n2,r[i])-b;
// for(rg int i=1;i<=n;i++){
// printf("%d %d\n",l[i],r[i]);
// }
// printf("n2=%d\n",n2);
ans=0; build(1,1,n2);
for(rg int i=1;i<=n;i++){
add(1,l[i],r[i],1);
}
for(rg int i=1;i<=n2;i++){
ans=max(ans,query(1,i,i));
//printf("%d\n",query(1,i,i));
}
printf("%d\n",ans);
return 0;
}

  

最新文章

  1. Python学习笔记(3)
  2. PHP上传(单个)文件示例
  3. Math类常用方法(Java)
  4. 基于webmagic的爬虫小应用--爬取知乎用户信息
  5. CentOS6.4 配置mysql服务器启动多个端口,同步单表数据
  6. Android --MainActivity模板
  7. BZOJ 1047 理想的正方形
  8. 多设备同时安装apk问题(安卓)
  9. CoreSeek中文检索引擎
  10. 【转】怎么导出jar包
  11. lintcode 链表求和
  12. Unity优化之贴图
  13. day 09
  14. transform带来的坑
  15. datetime学习
  16. PAT甲题题解-1040. Longest Symmetric String (25)-求最长回文子串
  17. 洛谷P2398 GCD SUM [数论,欧拉筛]
  18. 短网址(short URL)系统的原理及其实现
  19. oracle主从表主外键对应关系
  20. Word2007:如何在竖版(纵向)页面中间插入横版(横向)页面

热门文章

  1. Android App调用MediaRecorder实现录音功能的实例【转】
  2. 【关键字】volatile
  3. 洛谷 P3398 仓鼠找sugar —— 树链剖分
  4. bzoj1018
  5. 63.ExtJs事件(自定义事件、on、eventManager)示例
  6. 腾讯云SSL证书管理
  7. eclipse中Kotlin的基础应用
  8. [Swift通天遁地]八、媒体与动画-(10)在项目中播放GIF动画
  9. SQLServer局部变量和全局变量介绍05-29学习笔记
  10. ACM_二维数组的查找