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

Posted on Symbols count in article: 1.5k Reading time ≈ 5 mins.

Problem

【APIO2009】会议中心

Time  Limit:  15  Sec\mathrm{Time\;Limit:\;15\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

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

公司 开始日期 结束日期
公司1公司1 44 99
公司2公司2 99 1111
公司3公司3 1313 1919
公司4公司4 1010 1717

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

Input

第一行有一个整数N  (N≤2×105)N\;(N\le2\times10^5)，表示发出租借会堂申请的公司的个数。
第22到第N+1N+1行每行有22个整数。第i+1i+1行的整数表示第ii家公司申请租借的起始和终止日期。
对于每个公司的申请，起始日期为不小于11的整数，终止日期为不大于10910^9的整数。

Output

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

Sample Input

1
2
3
4
5
4
4 9
9 11
13 19
10 17

Sample Output

1
2
2
1 3

HINT

修复数据BUG\mathrm{BUG}，并新加数据一组。By  NanoApe  2016.5.11\mathrm{By\;NanoApe\;2016.5.11}
修复后数据

标签：贪心 倍增

Solution

思路清奇的贪心…

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

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

具体地，首先以rr从小到大为第一关键字，以ll从大到小为第二关键字排序，去掉包含的区间。
找到一种方法（一会儿说）计算F(p,q)F(p,q)，表示p∼qp\sim q时间段最多可以放多少个会议。
对于会议ii，其时间段是[l,r][l,r]，已经加入的会议中此会议的前驱的结束时间是lrlr，后继的开始时间是rlrl（前驱和后继用set维护）。

  • 若l≤lrl\le lr或r≥rlr\ge rl，那么一定不能放入。
  • 若F(lr+1,l−1)+F(r+1,rl−1)+1=F(lr+1,rl−1)F(lr+1,l-1)+F(r+1,rl-1)+1=F(lr+1,rl-1)，那么放入后一定不会影响答案，输出编号后把此会议加入set即可。这个等式表示加入此会议后虽然把原区间分成了三个子区间，但最大值依旧不变。
  • 若F(lr+1,l−1)+F(r+1,rl−1)+1≠F(lr+1,rl−1)F(lr+1,l-1)+F(r+1,rl-1)+1\ne F(lr+1,rl-1)，那么不能放入。

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

但如何计算F(p,q)F(p,q)呢？
如果直接算，是O(n)O(n)的，考虑把这个过程变成O(log⁡n)O(\log n)。
倍增预处理出nxt[u][i]nxt[u][i]，表示从区间uu开始向后选2i2^i个连续区间，最后一个区间的编号。于是每次计算可以倍增跳累加答案。

Problem  solved.\mathrm{Problem\;solved.}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
}