学步园

题意：给定n(n<=100000)个区间（左闭右开）和m(m<=100000)次询问[l, r]，问所有在[l, r]区间内最多有多少个两两不相交的区间。

题解：这个题可以暴力贪心，排序后筛选掉能覆盖其他任意区间的区间，然后扫描[l,r]得到答案。
          正解：坐标离散化，将区间排序后在初始化pos[i][j]（代表i坐标向右数最小的连续第2^j合法区间的右端点坐标）的过程中可以删除覆盖其他区间的区间，
          然后枚举[l,r]区间内答案的二进制，最后得到答案。

PS：upper_bound：第一个大于val的指针位置。
       lower_bound：第一个等于val的指针位置，如果不存在则指向第一个大于val的指针位置，此时与upper_bound的返回值相同。
       upper_bound()- lower_bound 即为val在所查找数组中出现的次数，数组须为升序。

Sure原创，转载请注明出处。

暴力贪心：

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int inf = 1000000002;
const int maxn = 100002;
struct interval
{
    int l,r;
    bool operator < (const interval &other) const
    {
        if(l == other.l)
        {
            return r > other.r;
        }
        return l < other.l;
    }
}inter[maxn];
int m,n,cnt;

void read()
{
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&inter[i].l,&inter[i].r);
    }
    sort(inter , inter + n);
    return;
}

void make()  //筛选掉能覆盖住其他任意区间的大区间
{
    int tot = 0;
    for(int i=0;i<n;++i)
    {
        bool flag = true;
        for(int j=i+1;j<n;++j)
        {
            if(inter[j].l >= inter[i].l && inter[j].r <= inter[i].r)
            {
                flag = false;
                break;
            }
            if(inter[j].l >= inter[i].r)
            {
                break;
            }
        }
        if(flag)
        {
            inter[tot++] = inter[i];
        }
    }
    n = tot;
    return;
}

int bis(int val)
{
    int le = 0,ri = n-1;
    while(le <= ri)
    {
        int mid = (le + ri) >> 1;
        if(inter[mid].l >= val)
        {
            ri = mid - 1;
        }
        else
        {
            le = mid + 1;
        }
    }
    return le;
}

void dfs(int l,int r)
{
    int wei = bis(l);   //找到第一个在l右方最近区间的左端点
    if(wei == n || inter[wei].l >= r || inter[wei].r > r) return;
    cnt++;
    l = inter[wei].r;
    return dfs(l , r);
}

void solve()
{
    int fr,to;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&fr,&to);
        cnt = 0;
        dfs(fr , to);
        printf("%d\n",cnt);
    }
    return;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        read();
        make();
        solve();
    }
    return 0;
}

离散化+倍增思想：

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 100002;
const int maxm = 20;
struct interval
{
    int l,r;
    bool operator < (const interval &other) const
    {
        if(l == other.l)
        {
            return r < other.r;
        }
        return l < other.l;
    }
}inter[maxn];
int pos[maxn << 1][maxm],x[maxn << 1];
int m,n,tot;

inline int getid(int val,bool flag)
{
    if(flag == false) return lower_bound(x , x + tot , val) - x;
    else return upper_bound(x , x + tot , val) - x - 1;
}

void read()
{
    tot = 0;
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&inter[i].l,&inter[i].r);
        x[tot++] = inter[i].l;
        x[tot++] = inter[i].r;
    }
    return;
}

void discretization()  //坐标离散化
{
    sort(inter , inter + n);
    sort(x , x + tot);
    tot = unique(x , x + tot) - x;
    for(int i=0;i<n;i++)
    {
        inter[i].l = getid(inter[i].l , 0);
        inter[i].r = getid(inter[i].r , 1);
    }
    x[tot] = tot;
    inter[n].l = inter[n].r = tot;
    return;
}

int MIN(int a,int b)
{
    return a < b ? a : b;
}

void init()
{
    int wei = tot,ri = n-1;
    for(int i=tot-1;i>=0;i--)
    {
        while(ri >= 0 && inter[ri].l >= i)
        {
            wei = MIN(wei , inter[ri--].r);   //可以筛掉覆盖其他区间的大区间
        }
        pos[i][0] = wei;
    }
    for(int i=0;i<maxm;i++)
    {
        pos[tot][i] = tot;
    }
    for(int i=1;i<maxm;i++)
    {
        for(int j=0;j<tot;j++)
        {
            pos[j][i] = pos[pos[j][i-1]][i-1];
        }
    }
    return;
}

int ask(int l,int r)
{
    if(l > r || l == tot || r == -1) return 0;
    int res = 0,k = maxm;
    while(k)  //枚举答案的二进制
    {
        k--;
        if(pos[l][k] <= r)
        {
            res += (1 << k);
            l = pos[l][k];
        }
    }
    return res;
}

void solve()
{
    int fr,to;
    while(m--)
    {
        scanf("%d %d",&fr,&to);
        fr = getid(fr , 0);
        to = getid(to , 1);
        printf("%d\n",ask(fr,to));
    }
    return;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        read();
        discretization();
        init();
        solve();
    }
    return 0;
}