BZOJ 1178: [Apio2009]CONVENTION会议中心

Description

Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止一种满足要求的策略。例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。开始日期结束日期公司149公司2911公司3131公司41017 上例中，最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意会议中心一天最多租借给一个公司，所以公司1和公司2不能同时租借会议中心，因为他们在第九天重合了。销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小1的候选策略作为最终的策略。例中，会堂最终将被租借给公司1和公司3：3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)< (2,3)。你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

Input

输入的第一行有一个整数N，表示发出租借会堂申请的公司的个数。第2到第N+1行每行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司的申请，起始日期为不小于1的整数，终止日期为不大于10^9的整数。N≤200000

Output

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

Sample Input

4 9

9 11

13 19

10 17

Sample Output

1 3

HINT

修复数据bug,并新加数据一组By NanoApe 2016.5.11

修复后数据:JudgeOnline/upload/201605/dd.rar

Solution

第一问就是线段覆盖，按照右端点排序之后扫一遍就出来了。

第二问就是求字典序最小的方案。

求字典序最小，当然是贪心来做。枚举每一条线段，看看能不能放。

如果加入这条线段后，能放的最大值不变，就加入这条线段。

问题转化成加入某区间求能放线段最大值问题。

考虑先将坐标离散化，令 f[i][j] 表示从左端点 i 开始,出现 2^j 不相交的区间最近的右端点编号。

有f[i][j]=f[f[i][j-1]+1][j-1]。

每次加入一段区间后,相当于将原来的大区间分割成两个小区间,依次用 f 数组找最大值之后判断是否可行即可。

复杂度O(NlogN)。

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
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <algorithm>
#include <functional>
#include <set>
using namespace std;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
const int maxn = 400233;
struct LINE { int l, r, i; } xd[maxn], txd[maxn],mag;
int n, mxlog, tot, cnt, hsk, cur, lst;
int dp[maxn][20], L[maxn], R[maxn], tmp[maxn], has[maxn], id[maxn], dst[maxn], dsttot;
bool cmpi (LINE a, LINE b) { return a.i < b.i; }
bool operator < (LINE x, LINE y) { return x.r < y.r || (x.r == y.r && x.l > y.l); }
bool operator > (LINE x, LINE y) { return x.r > y.r || (x.r == y.r && x.l < y.l); }
set<LINE, greater<LINE> > Left;
set<LINE, less<LINE> > Right;
int bFind(int l, int r, int v) {
	int mid = (l + r) >> 1;
	if (l == r) return has[l];
	if (v == tmp[mid]) return has[mid];
	if (v < tmp[mid])
		return bFind(l, mid - 1, v);
	return bFind(mid + 1, r, v);
}
int calc(int l, int r) {
	int ret = 0, pos = l;
	for (int i = mxlog; i >= 0 && pos <= r; --i) {
		if (dp[pos][i] && dp[pos][i] <= r) {
			ret += (1 << i);
			pos = dp[pos][i] + 1;
		}
	}
	return ret;
}
bool check(int now) {
	LINE pre = *(Left.lower_bound(txd[now])), nxt = *(Right.lower_bound(txd[now]));
	if (pre.r >= txd[now].l || nxt.l <= txd[now].r) return false;
	if (calc(pre.r + 1, nxt.l - 1) == calc(pre.r + 1, txd[now].l - 1) + calc(txd[now].r + 1, nxt.l - 1) + 1) {
		Right.insert(txd[now]); Left.insert(txd[now]);
		return true;
	}
	return false;
}
int main() {
	n = getint();
	for (int i = 1; i <= n; ++i) {
		txd[i].l = getint();
		txd[i].r = getint();
		txd[i].i = i;
		tmp[++cnt] = txd[i].l;
		tmp[++cnt] = txd[i].r;
	}
	sort(txd+1, txd+n+1);
	lst = 0;
	for (int i = 1; i <= n; ++i) {
		if (txd[i].l > lst) {
			++tot;
			lst = xd[tot].l = txd[i].l;
			xd[tot].r = txd[i].r;
			xd[tot].i = i;
		}
	}

	sort(tmp+1, tmp+cnt+1);
	for (int i = 1; i <= cnt; ++i) {
		if (tmp[i] != tmp[i - 1]) ++hsk;
		has[i] = hsk;
	}

	for (int i = 1; i <= n; ++i) {
		txd[i].l = bFind(1, cnt, txd[i].l);
		txd[i].r = bFind(1, cnt, txd[i].r);
	}
	for (int i = 1; i <= tot; ++i) {
		xd[i].l = txd[xd[i].i].l;
		xd[i].r = txd[xd[i].i].r;
		xd[i].i = txd[xd[i].i].i;
	}
	for (int i = txd[n].r; i; i >>= 1, ++mxlog);
	for (int i = 1; i <= tot; ++i)
		for (int j = xd[i-1].l + 1; j <= xd[i].l; ++j)
			dp[j][0] = xd[i].r;
	for (int i = 1; i <= mxlog; ++i)
		for (int j = 1; j <= txd[n].r; ++j)
			if (dp[j][i-1])
				dp[j][i] = dp[dp[j][i-1]+1][i-1];

	int ans1 = 0, ri = 0;
	for (int i = 1; i <= tot; ++i)
		if (xd[i].l > ri) {
			ri = xd[i].r;
			++ans1;
		}
	printf("%d\n", ans1);
	mag.l = mag.r = 0;
	Left.insert(mag);
	mag.l = mag.r = txd[n].r + 1;
	Right.insert(mag);
	sort(txd+1, txd+n+1, cmpi);
	for (int i = 1; i <= n; ++i)
		if (check(i))
			dst[++dsttot] = i;
	for (int i = 1; i < dsttot; ++i)
		printf("%d ", dst[i]);
	printf("%d", dst[dsttot]);
	return 0;
}