蓝桥杯 ALGO-40算法训练 会议中心 （APIO 2009）

时间限制：2.0s 内存限制：512.0MB
关键字：APIO 2009
会议中心　　Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。
　　对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止一种满足要求的策略。
　　例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。

          开始日期  结束日期
    公司1    4       9
    公司2    9       11
    公司3    13      19
    公司4    10      17

　　上例中，最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意会议中心一天最多租借给一个公司，所以公司1和公司2不能同时租借会议中心，因为他们在第九天重合了。
　　销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小[1]的候选策略作为最终的策略。
　　例中，会堂最终将被租借给公司1和公司3：3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。
　　你的任务是帮助销售主管确定应该将会堂租借给哪些公司。
输入格式
　　输入的第一行有一个整数N，表示发出租借会堂申请的公司的个数。第2到第N+1行每行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司的申请，起始日期为不小于1的整数，终止日期为不大于109的整数。
输出格式
　　输出的第一行应有一个整数M，表示最多可以租借给多少家公司。第二行应列出M个数，表示最终将会堂租借给哪些公司。
数据规模和约定
　　对于50%的输入，N≤3000。在所有输入中，N≤200000。
样例输入
4
4 9
9 11
13 19
10 17
样例输出
2
1 3

[1] 字典序指在字典中排列的顺序，如果序列l1是序列l2的前缀，或者对于l1和l2的第一个不同位置j，l1[j]

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;

const int maxn=200010;
struct data {
    int l,r;
    friend bool operator < (const data &x,const data &y) {
        return x.r==y.r ? x.l>y.l : x.r<y.r;
    }
}a[maxn],t[maxn];
int X[maxn],Y[maxn],next[maxn][30],L[maxn],R[maxn],n,m;

int cal(int l,int r) {
    int x=lower_bound(X+1,X+1+m,l)-X;
    if (Y[x]>r || x>m) return 0;
    int res=1;
    for (int i=20;i>=0;i--) if (next[x][i] && Y[next[x][i]]<=r) res+=1<<i,x=next[x][i];
    return res;
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&t[i].l,&t[i].r),a[i]=t[i];
    sort(t+1,t+1+n);
    m=0;
    for (int i=1;i<=n;i++) if (m==0 || t[i].l>t[m].l) t[++m]=t[i];
    for (int i=1;i<=m;i++) X[i]=t[i].l,Y[i]=t[i].r;
    for (int i=1,j=1;i<=m;i++) {
        while (j<=m && t[j].l<=t[i].r) j++;
        if (j<=m) next[i][0]=j;
    }
    for (int j=1;j<=20;j++)
        for (int i=1;i<=m;i++) next[i][j]=next[next[i][j-1]][j-1];
    int ans;
    printf("%d\n",ans=cal(-inf,inf));
    set<data> s;
    s.insert((data){inf,inf});
    s.insert((data){-inf,-inf});
    int cnt=0;
    for (int i=1;i<=n;i++) {
        set<data>::iterator x=s.lower_bound(a[i]),y=x;y--;
        int l1=y->r,r1=a[i].l,l2=a[i].r,r2=x->l;
        if (l1>=r1 || l2>=r2) continue;
        if (cal(l1+1,r2-1)==cal(l1+1,r1-1)+cal(l2+1,r2-1)+1) {
            if (++cnt==ans) printf("%d",i);
            else printf("%d ",i);
            s.insert(a[i]);
        }
    }
    return 0;
}

C++：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <set>

const char fi[] = "convention.in";
const char fo[] = "convention.out";
const int maxN = 200010;
const int MAX = 0x3f3f3f3f,MIN = ~MAX;

struct Seg
{
    int L,R;
    Seg()
    {
    }
    Seg(int L,int R): L(L),R(R)
    {
    }
    bool operator<(const Seg &b) const
    {
        return L < b.L || L == b.L && R < b.R;
    }
};
std::set <Seg> S;
std::set <Seg>::iterator iter;
Seg req[maxN],seg[maxN],tmp[maxN];
int tab[maxN << 1],next[20][maxN << 1];
int n,cnt,Lim = 1,logLim;

void init_file()
{
    return;
}

inline int getint()
{
    int res = 0; char tmp;
    while(!isdigit(tmp = getchar()));
    do res = (res << 3) + (res << 1) + tmp - '0';
    while(isdigit(tmp = getchar()));
    return res;
}

void readdata()
{
    n = getint();
    for(int i = 0; i < n; ++i)
    {
        int L = getint(),R = getint();
        req[i] = Seg(L,R);
        tab[i << 1] = L;
        tab[(i << 1) + 1] = R;
    }
    return;
}

int plc(int x)
{
    for(int L = 0,R = Lim - 1; L < R + 1;)
    {
        int Mid = (L + R) >> 1;
        if(x == tab[Mid]) return Mid + 1;
        if(x < tab[Mid]) R = Mid - 1;
        else L = Mid + 1;
    }
}

bool cmp(const Seg &a,const Seg &b)
{
    return a.R < b.R || a.R == b.R && a.L > b.L;
}

void discrete()
{
    std::sort(tab,tab + (n << 1));
    for(int i = 1; i < n << 1; ++i)
        if(tab[i] != tab[i - 1])
            tab[Lim++] = tab[i];
    for(int i = 0; i < n; ++i)
        tmp[i] = req[i] = Seg(plc(req[i].L),
        plc(req[i].R));
    std::sort(tmp,tmp + n,cmp);
    //这里必须要用一个临时数组，
    //保证左界右界同时单调递增。
    int p = 0; seg[cnt++] = tmp[0];
    for(int i = 1; i < n; ++i)
        if(tmp[i].L > tmp[p].L)
            seg[cnt++] = tmp[p = i];
    return;
}

void next_set()
{
    int p = cnt; next[0][Lim + 1] = MAX;
    for(int j = Lim; j; --j)
        if(p > -1 && j == seg[p - 1].L)
            next[0][j] = seg[--p].R + 1;
        else next[0][j] = next[0][j + 1];
        for(int i = 0;; ++i)
        {
            bool flag = 0;
            next[i + 1][Lim + 1] = MAX;
            for(int k = 1; k < Lim + 1; ++k)
            {
                if(next[i][k] == MAX)
                    next[i + 1][k] = MAX;
                else next[i + 1][k] = next[i][next[i][k]];
                if(next[i + 1][k] < MAX) flag = 1;
            }
            if(!flag)
            {
                logLim = i; break;
            }
        }
        return;
}

int max_time(int L,int R)
{
    if(L > R++) return 0;
    int ans = 0,p = L;
    for(int i = logLim; i > -1 && p < R; --i)
        if(next[i][p] <= R)
        {
            p = next[i][p]; ans += 1 << i;
        }
    return ans;
}

bool query(int i)
{
    int L = req[i].L,R = req[i].R;
    iter = S.lower_bound(Seg(L,MAX));
    if(iter-- == S.begin()) return 0;
    if(iter->L > L || iter->R < R)
        return 0;
    int L1 = iter->L,R1 = iter->R;
    if(max_time(L1,L - 1)
        + max_time(R + 1,R1)
        + 1 < max_time(L1,R1))
        //这里要满足放进去过后不影响总的答案。
        return 0;
    S.erase(iter);
    if(L1 < L) S.insert(Seg(L1,L - 1));
    if(R < R1) S.insert(Seg(R + 1,R1));
    return 1;
}

void work()
{
    printf("%d\n",max_time(1,Lim));
    S.insert(Seg(1,Lim));
    for(int i = 0; i < n; ++i)
        if(query(i))
            printf("%d ",i + 1);
    printf("\n");
    return;
}

int main()
{
    init_file();
    readdata();
    discrete();
    next_set();
    work();
    return 0;
}