标签：后序 pre 包含 iii 思路 main 坐标轴 long 线段
这题好难啊！ 我好菜啊！
思路：对于最多线段不相交， 我们可以按左端点sort之后，贪心取。 但是这个题要求选取的线段排序之后序号的字典序最小。
那么我们如果按序号贪心地从大往小往里放， 那么对于第k个线段，我们考虑放进去之后是能是还能保证所取的线段个数能
达到最大， 我们考虑函数cal(l, r) 表示坐标轴上l 到 r 最多能选取多少线段，第k条线段的左右端点是l, r, 它左边第一条是l1, r1
它右边第一条是l2, r2， 那么k能放进去的充分必要条件就是cal(r1 + 1, l2 - 1) == cal(r1 + 1, l - 1) + cal(r + 1, l2 - 1) + 1。
那么我们的问题就变成了cal()这个函数如何实现，我们将原来的线段按右端点排序之后，把包含其他线段的线段全部删掉，
然后nx[ i ][ 0 ] = k 表示 k是第一个满足b[k].l > b[i].r 的线段， 然后我们再倍增一下，求出nx[ i ][ j ]表示 i 右边第2^j 个线段是谁。
1 #include 2 #define LL long long
3 #define fi first
4 #define se second
5 #define mk make_pair
6 #define pii pair 7 #define piii pair>
8
9 using namespace std;
10
11 const int N=200000+7;
12 const int M=1e4+7;
13 const int inf=0x3f3f3f3f;
14 const LL INF=0x3f3f3f3f3f3f3f3f;
15 const int mod=1e9 + 7;
16
17 int n, m, nx[N][21], L[N], R[N];
18
19 struct Line {
20 int l, r;
21
22 Line(int _l = 0, int _r = 0) {
23 l = _l;
24 r = _r;
25 }
26 bool operator const Line &rhs) const {
27 if(r == rhs.r) return l rhs.l;
28 return r rhs.r;
29 }
30
31 } a[N], b[N];
32
33 int cal(int l, int r) {
34 int x = lower_bound(L + 1, L + 1 + m, l) - L;
35 if(x > m || R[x] > r) return 0;
36 int ans = 1;
37 for(int i = 20; i >= 0; i--) {
38 if(nx[x][i] && R[nx[x][i]] r) {
39 ans += 1 i;
40 x = nx[x][i];
41 }
42 }
43 return ans;
44 }
45 int main() {
46
47 scanf("%d", &n);
48 for(int i = 1; i ) {
49 scanf("%d%d", &a[i].l, &a[i].r);
50 b[i] = a[i];
51 }
52
53 sort(b + 1, b + n + 1);
54
55 for(int i = 1; i ) {
56 if(!m || b[i].l > b[m].l)
57 b[++m] = b[i];
58 }
59
60 for(int i = 1; i )
61 L[i] = b[i].l, R[i] = b[i].r;
62
63 for(int i = 1, j = 1; i ) {
64 while(j ;
65 if(j 0] = j;
66 }
67
68 for(int i = 1; i 20; i++) {
69 for(int j = 1; j ) {
70 nx[j][i] = nx[nx[j][i - 1]][i - 1];
71 }
72 }
73
74 int ans = cal(-inf, inf);
75 printf("%d\n", ans);
76 set st;
77 int cnt = 0;
78 st.insert(Line(inf, inf));
79 st.insert(Line(-inf, -inf));
80
81 for(int i = 1; i ) {
82 set::iterator it = st.lower_bound(a[i]), itt = it; itt--;
83 int l1 = itt -> r, r1 = a[i].l, l2 = a[i].r, r2 = it -> l;
84 if(l1 >= r1 || l2 >= r2) continue;
85 if(cal(l1 + 1, r2 - 1) == cal(l1 + 1, r1 - 1) + cal(l2 + 1, r2 - 1) + 1) {
86 if(++cnt == ans) printf("%d", i);
87 else printf("%d ", i);
88 st.insert(a[i]);
89 }
90 }
91 puts("");
92 return 0;
93 }
94 /*
95 */
bzoj 1178 [Apio2009]CONVENTION会议中心
标签：后序 pre 包含 iii 思路 main 坐标轴 long 线段
原文地址：https://www.cnblogs.com/CJLHY/p/9054045.html