# 【HDU 4343】Interval query（倍增）

2022年11月23日
0 收藏 306 点赞 3,807 浏览 1724 个字

BUPT2017 wintertraining(15) #8D

### 代码

780ms

``#include <cstdio>#include <algorithm>#include <cstring>#define N 100005using 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;elser=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 100005using 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;}``

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com