首页 技术 正文
技术 2022年11月23日
0 收藏 306 点赞 3,807 浏览 1724 个字

BUPT2017 wintertraining(15) #8D

题意

给你x轴上的N个线段,M次查询,每次问你[l,r]区间里最多有多少个不相交的线段。(0<N, M<=100000)

限时15000 MS

题解

如果不看限时,当作是1000MS的话= =,那么可以用倍增来做。

先按右端点排序。

可以去掉一下包含了其它区间的区间,可以优化一点点。

用 f[i][j] 表示 i 节点下 \(2^n\) 个不相交的线段下标。

预处理出 f 数组。

查询的时候,左端点用二分,然后右端点用倍增来找。

实际上不用倍增,也可以卡时间过。

代码

780ms

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100005
using namespace std;
struct Seg{
int s,e;
bool operator < (const Seg &b) const{
return e<b.e||e==b.e&&s>b.s;
}
}seg[N];
int n,m;
int f[N][32];
int main(){
while(~scanf("%d %d", &n, &m)){
for(int i=0;i<n;++i)
scanf("%d %d", &seg[i].s, &seg[i].e);
memset(f,-1,sizeof f);
sort(seg,seg+n);
int nn=0;
for(int i=1;i<n;++i)
if(seg[nn].s<seg[i].s)
seg[++nn]=seg[i];
++nn;
for(int i=0;i<nn;++i){
f[i][0]=i+1;
while(f[i][0]<nn&&seg[f[i][0]].s<seg[i].e)++f[i][0];
if(f[i][0]==nn)f[i][0]=-1;
}
for(int j=0;j<30;++j)
for(int i=0;i<nn;++i)
if(f[i][j]!=-1)
f[i][j+1]=f[f[i][j]][j];
for(int i=1,s,e;i<=m;++i){
scanf("%d %d", &s, &e);
int l=0, r=nn-1;
while(l<r){
int m=l+r>>1;
if(seg[m].s<s)
l=m+1;
else
r=m;
}
if(seg[l].e>e||seg[l].s<s)puts("0");
else{
int ans=1;
for(int j=29;j>=0;--j){
if(f[r][j]!=-1&&seg[f[r][j]].e<=e){
r=f[r][j];
ans+=(1<<j);
}
}
printf("%d\n", ans);
}
}
}
return 0;
}

1045ms

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100005
using namespace std;
struct Seg {
int s, e;
bool operator < (const Seg &b) const {
return e < b.e || e == b.e && s > b.s;
}
} seg[N];
int n, m;
int main() {
while(~scanf("%d %d", &n, &m)) {
for(int i = 0; i < n; ++i)
scanf("%d %d", &seg[i].s, &seg[i].e);
sort(seg, seg + n);
int nn = 0;
for(int i = 1; i < n; ++i)
if(seg[nn].s < seg[i].s)
seg[++nn] = seg[i];
++nn;
for(int i = 1, s, e; i <= m; ++i) {
scanf("%d %d", &s, &e);
int l = 0, r = nn - 1;
while(l < r) {
int m = l + r >> 1;
if(seg[m].s < s)
l = m + 1;
else
r = m;
}
if(seg[l].e > e || seg[l].s < s)puts("0");
else {
int ans = 1;
for(int i = l, j = l + 1; j < nn && seg[j].e <= e; ++j) {
if(seg[i].e <= seg[j].s) {
i = j;
++ans;
}
}
printf("%d\n", ans);
}
}
}
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141556.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站