题目描述

x轴上有若干条不同线段，问某个单位区间[x,x+1]上重叠了多少条线段？

思路

随便搞搞

#include <stdio.h>
#define maxn 1000005
struct tree
{
    int l,r,c;
}t[maxn];
int fl[maxn],lc=0,rc=0;
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int insert(int f,int x,int y)
{
    int m=(t[f].l+t[f].r)/2;
    if (t[f].l==x&&t[f].r==y) t[f].c++;
    else
    {
        if (y<=m) insert(f*2,x,y);
        else if (x>=m) insert(f*2+1,x,y);
        else 
        {
            insert(f*2,x,m);
            insert(f*2+1,m,y);
        }
    }

}
int ans;
int count(int p)
{
    int ans=0;
    while (p>0)
    {
        ans+=t[p].c;
        p=p>>1;
    }
    return ans;
}
int create(int f)
{
    if (t[f].r-t[f].l>1)
    {
        int m=(t[f].l+t[f].r)/2;
        t[f*2].l=t[f].l;
        t[f*2].r=m;
        t[f*2+1].l=m;
        t[f*2+1].r=t[f].r;
        create(f*2);
        create(f*2+1);
    }
}
int o;
int find(int p,int l,int r,int x,int y)
{
    int m=(l+r)>>1;
    if (l==x&&r==y)
    {
        o=p;return 0;
    }
    else if (m>=y) find(p<<1,l,m,x,y);
    else if (m<=x) find(p<<1|1,m,r,x,y);
    else 
    {
        find(p<<1,l,m,x,m);
        find(p<<1|1,m,r,m,y);
    }
}
int main()
{
    t[1].c=1;
    int n,m;
    scanf("%d%d",&m,&n);
    t[1].l=1; t[1].r=m;
    create(1);
    for (int i=1;i<=n;i++)
    {
        int x=read(),y=read();
        insert(1,x,y);
    }
    int x,y;
    scanf("%d%d",&x,&y);
    find(1,1,m,x,y);
    printf("%d\n",count(o)-1);
}