专栏首页饶文津的专栏【HDU 4343】Interval query(倍增)

【HDU 4343】Interval query(倍增)

BUPT2017 wintertraining(15) #8D

题意

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

题解

代码

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Codeforces 707A】Brain's Photos 水题

    饶文津
  • 「UVA10766」Organising the Organisation(生成树计数)

    饶文津
  • 【USACO 2.2】Party Lamps

    四种开关,n盏灯,1:改变所有灯状态,2:改变奇数灯状态,3:改变偶数灯状态,4:改变3k+1灯状态

    饶文津
  • 大数据揭秘!明年这些行业将最吃香!

    继2014年高校毕业生人数突破700万之后,2015年的毕业生人数达到749万之多。毕业生人数在年年递增,就业之难也似乎成了常态。连续几年的“史上最难就业季”给...

    华章科技
  • 12张数据图讲述了2016过去一年的故事

    身处影响我们生活的社会、政治和经济动荡之中,面对频繁成为头条新闻的暴力事件和难民潮,对2016年感到悲观失望是可以理解的。统计数据不仅揭示出我们面临的挑战,也...

    灯塔大数据
  • 纽约时报&CB Insights:全球100位最佳风险投资人(附排名)

    CB Insights连续第三年与纽约时报合作,利用算法评选出了全球前100位最佳风险投资人。NYT-CBI排名没有受到风险投资人的个人宣传或传奇历史的影响,...

    点滴科技资讯
  • kmskeys10 By HKL, Saturday 7

    https://technet.microsoft.com/en-us/library/jj612867.aspx?lc=1033

    hiplon
  • iOS多线程编程之二——NSOperation与NSOperationQueue

    NSOperation是基于Object-C封装的一套管理与执行线程操作的类。这个类是一个抽象类,通常情况下,我们会使用NSInvocationOperatio...

    珲少
  • 研究人员利用深度学习实时生成完整的3D头发模型

    南加州大学,Pinscreen和微软的研究人员开发了一种基于深度学习的方法,可以从单视图图像中实时生成完整的3D头发几何图形。该团队表示,这是第一个能够实时渲...

    AiTechYun
  • 阿里与百联合作打造多场景消费模式,苹果投资数百元刀或将开启手机解 | 大数据24小时

    数据猿导读 数据服务公司Immuta完成800万美元融资;苹果数百元美元收购人脸识别公司RealFace,或将其技术应用于新款iphone;基于大数据技术的心理...

    数据猿

扫码关注云+社区

领取腾讯云代金券