[BZOJ1178][Apio2009]CONVENTION会议中心
试题描述
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的整数，终止日期为不大于10^9的整数。
输出
输出的第一行应有一个整数M，表示最多可以租借给多少家公司。第二行应列出M个数，表示最终将会堂租借给哪些公司。
输入示例
4 4 9 9 11 13 19 10 17
输出示例
2 1 3
数据规模及约定
对于50%的输入，N≤3000。在所有输入中，N≤200000 请注意使用Readln读入数据........
题解
这里把所有的“公司”等价成左端点为“开始日期”，右端点为“结束日期”的线段。
如果只考虑第一问，贪心即可，按右端点升序排序，把所有包含别的线段的线段去掉数个数即可。
加了个字典序，就好玩了。
然而“字典序”还是要用到贪心，于是从1~n条线段依次判断，若第 i 条线段满足加进去后不影响最终能选的线段条数则毫无疑问地选择 i。如何判断是核心问题，我们可以用倍增算法：令 f(j, i) 表示从点 i 开始，选择 2j 个不相交线段可能的最靠左的点，那么就不难算出一个区间 [L, R] 中最优能选择的线段条数了（详见代码中的 getans() 函数）。以后判断线段时，先确保当前线段与前面所有加进来的线段无交集，再找到这个线段的前驱 ql 和后继 qr，然后当 ans(ql + 1, qr - 1) = ans(ql + 1, l - 1) + 1 + ans(r + 1, qr - 1) 时说明这个线段可以选进来（ans(i, j)表示区间[i, j]中最优能够选择的线段的条数，l、r 表示当前线段左、右端点）。
至于判断线段是否有交集，可以用个平衡树找前驱后继。（如果不怕慢可以用set）
代码注释多，请忽略。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 200010
#define maxm 400010
#define maxlog 20
#define oo 2147483647
int n, N, cnt, num[maxm], c, ans[maxn];
struct Line { int l, r, id; } ls[maxn];
int Right[maxlog][maxm];
void init() {
for(int j = 1; j < maxlog; j++)
for(int i = 1; i <= N && Right[j-1][i] < N && Right[j-1][Right[j-1][i]+1] <= N; i++)
Right[j][i] = Right[j-1][Right[j-1][i]+1];
return ;
}
int getans(int l, int r) {
if(l > r) return 0;
int ans = 0, p = l;
for(int i = maxlog-1; i >= 0; i--) if(Right[i][p] <= r)
ans += (1 << i), p = Right[i][p];
return ans;
}
int ToT, fa[maxm], ch[maxm][2], root;
struct Node { int v, r, minv, maxv, siz; } nodes[maxm];
void newnode(int& o, int v) {
nodes[o = ++ToT] = (Node) { v, rand(), v, v, 1 };
return ;
}
void maintain(int o) {
Node &u = nodes[o], &lc = nodes[ch[o][0]], &rc = nodes[ch[o][1]];
u.minv = min(min(lc.minv, rc.minv), u.v);
u.maxv = max(max(lc.maxv, rc.maxv), u.v);
u.siz = lc.siz + 1 + rc.siz;
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(ch[y][1] == u) swap(l, r);
if(z >= 0) ch[z][ch[z][1]==y] = u;
else root = u;
fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;
ch[y][l] = ch[u][r]; ch[u][r] = y;
maintain(y); maintain(u);
return ;
}
void insert(int& o, int v, int pa) {
if(!o) {
newnode(o, v);
fa[o] = pa;
return ;
}
int d = v > nodes[o].v;
insert(ch[o][d], v, o);
if(nodes[ch[o][d]].r > nodes[o].r) rotate(ch[o][d]);
maintain(o);
return ;
}
int _l, _r, _s;
void findp(int o, int v) {
// printf("\no: %d %d %d %d\n", o, nodes[o].v, ch[o][0], nodes[ch[o][0]].maxv);
if(!o) { _l = _r = -1; return ; }
if(nodes[o].v == v){ _l = _r = v; return ; }
if(nodes[o].v > v && ch[o][0] && nodes[ch[o][0]].maxv < v) {
_s += nodes[ch[o][0]].siz;
_l = nodes[ch[o][0]].maxv; _r = nodes[o].v;
return ;
}
if(nodes[o].v < v && ch[o][1] && nodes[ch[o][1]].minv > v) {
_s += nodes[ch[o][0]].siz + 1;
_l = nodes[o].v; _r = nodes[ch[o][1]].minv;
return ;
}
int d = v > nodes[o].v;
if(d) _s += nodes[ch[o][0]].siz + 1;
findp(ch[o][d], v);
return ;
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
srand(1314);
n = read(); N = n << 1;
for(int i = 1; i <= n; i++) {
num[++cnt] = ls[i].l = read(); num[++cnt] = ls[i].r = read();
ls[i].id = i;
}
sort(num + 1, num + cnt + 1);
unique(num + 1, num + cnt + 1);
for(int i = 1; i <= n; i++) {
ls[i].l = lower_bound(num + 1, num + cnt + 1, ls[i].l) - num;
ls[i].r = lower_bound(num + 1, num + cnt + 1, ls[i].r) - num;
}
int p = 0;
for(int j = 0; j < maxlog; j++)
for(int i = 1; i <= N; i++) Right[j][i] = N + 1;
for(int i = 1; i <= n; i++) Right[0][ls[i].l] = min(Right[0][ls[i].l], ls[i].r);
// for(int i = 1; i <= n; i++) printf("%d %d\n", ls[i].l, ls[i].r);
for(int i = N - 1; i; i--) Right[0][i] = min(Right[0][i], Right[0][i+1]);
// for(int i = 1; i <= N; i++) printf("%d ", Right[0][i]); putchar('\n');
init();
printf("%d\n", getans(1, N));
nodes[0] = (Node) { 0, 0, oo, -oo, 0 };
insert(root, 0, -1); insert(root, N + 1, -1);
for(int i = 1; i <= n; i++) {
findp(root, ls[i].l); int ll = _l, lr = _r; _s = 0;
findp(root, ls[i].r); int rl = _l, rr = _r;
// printf("%d [%d, %d]: %d %d %d %d %d\n", i, ls[i].l, ls[i].r, ll, lr, rl, rr, _s);
if(ll == lr || rl == rr || ll != rl || lr != rr || !(_s & 1)) continue;
ll++; lr--;
if(getans(ll, lr) == getans(ll, ls[i].l-1) + 1 + getans(ls[i].r+1, lr)) {
ans[++c] = i; insert(root, ls[i].l, -1); insert(root, ls[i].r, -1);
}
}
// printf("getans: %d %d\n", getans(1, 3), Right[0][1]);
for(int i = 1; i <= c; i++) printf("%d ", ans[i]); putchar('\n');
// printf("%d\n", c);
return 0;
}
/*
5
4 8
3 6
1 4
1 3
9 10
*/