BZOJ1178【APIO2009】会议中心 <贪心+倍增>

Problem

【APIO2009】会议中心

Description

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

公司	开始日期	结束日期

上例中，最多将会堂租借给两家公司。租借策略分别是租给和，或是和，也可以是和。注意会议中心一天最多租借给一个公司，所以和不能同时租借会议中心，因为他们在第九天重合了。
销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小的候选策略作为最终的策略。
例中，会堂最终将被租借给和：个候选策略是，而在字典序中。
你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

Input

第一行有一个整数，表示发出租借会堂申请的公司的个数。
第到第行每行有个整数。第行的整数表示第家公司申请租借的起始和终止日期。
对于每个公司的申请，起始日期为不小于的整数，终止日期为不大于的整数。

Output

输出的第一行应有一个整数，表示最多可以租借给多少家公司。
第二行应列出个数，表示最终将会堂租借给哪些公司。

Sample Input

Sample Output

1
2

2
1 3

HINT

修复数据，并新加数据一组。
修复后数据

标签：贪心 倍增

Solution

思路清奇的贪心…

如果没有“字典序最小”，直接无脑贪心即可。有输方案的要求后，就需要用另外一种贪心。

首先先做一遍贪心找到最多能有多少个会议，然后从到按编号枚举会议，看当前会议加入后会不会使答案变小，如果不会变小就贪心把这个会议加入到方案中。

具体地，首先以从小到大为第一关键字，以从大到小为第二关键字排序，去掉包含的区间。
找到一种方法（一会儿说）计算，表示时间段最多可以放多少个会议。
对于会议，其时间段是，已经加入的会议中此会议的前驱的结束时间是，后继的开始时间是（前驱和后继用set维护）。

若或，那么一定不能放入。
若，那么放入后一定不会影响答案，输出编号后把此会议加入set即可。这个等式表示加入此会议后虽然把原区间分成了三个子区间，但最大值依旧不变。
若，那么不能放入。

这样一来，就可以解决输出方案的问题了。

但如何计算呢？
如果直接算，是的，考虑把这个过程变成。
倍增预处理出，表示从区间开始向后选个连续区间，最后一个区间的编号。于是每次计算可以倍增跳累加答案。

Code

#include <bits/stdc++.h>
#define LOG 20
#define MAX_N 200000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, L[MAX_N+5], R[MAX_N+5], nxt[MAX_N+5][LOG+1];
struct node {int l, r; bool operator < (const node &t) const;} a[MAX_N+5], b[MAX_N+5];
bool node::operator < (const node &t) const {return r == t.r ? l > t.l : r < t.r;}
int calc(int l, int r) {
    int u = lower_bound(L+1, L+m+1, l)-L, ret = 1;
    if (u > m || R[u] > r) return 0;
    for (int i = LOG; ~i; i--)
        if (nxt[u][i] && R[nxt[u][i]] <= r)
            ret += 1<<i, u = nxt[u][i];
    return ret;
}
int main() {
    read(n); set <node> s;
    for (int i = 1; i <= n; i++)
        read(a[i].l), read(a[i].r), b[i] = a[i];
    sort(b+1, b+n+1), m = 0;
    for (int i = 1; i <= n; i++)
        if (b[i].l > b[m].l) b[++m] = b[i];
    for (int i = 1; i <= m; i++) L[i] = b[i].l, R[i] = b[i].r;
    for (int i = 1, j = 1; i <= m; i++) {
        while (j <= m && b[j].l <= b[i].r) j++;
        if (j <= m) nxt[i][0] = j;
    }
    for (int i = 1; i <= LOG; i++)
        for (int j = 1; j <= m; j++)
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
    s.insert((node){-INF, -INF}), s.insert((node){INF, INF});
    printf("%d\n", calc(-INF, INF));
    for (int i = 1; i <= n; i++) {
        set <node> :: iterator ln = s.lower_bound(a[i]), rn = ln;
        ln--; int l = a[i].l, r = a[i].r, lr = ln->r, rl = rn->l;
        if (l <= lr || r >= rl) continue;
        if (calc(lr+1, rl-1) == calc(lr+1, l-1)+calc(r+1, rl-1)+1)
            s.insert(a[i]), printf("%d ", i);
    }
    return puts(""), 0;
}