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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;
long long read()
{
long long 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;
}
const int N=200000+100;
struct line
{
int l,r,no;
friend bool operator < (line A,line B)
{
return A.l<B.l;
}
}l[N];
bool cmp(line A,line B)
{
if(A.l==B.l)
{
if(A.r!=B.r)
return A.r>B.r;
else
return A.no>B.no;
}
return A.l<B.l;
}
bool cmp2(line A,line B)
{
return A.no<B.no;
}
int n,ans,root,fa[N][20+2];
bool use[N],vis[N];
stack <int> ms;
set <line> mset;
set <line> used;
vector <int> e[N];
void dfs(int now,int FA)
{
vis[now]=true;
fa[now][0]=FA;
for(int i=1;i<=20;i++)
fa[now][i]=fa[fa[now][i-1]][i-1];
for(int i=0;i<int(e[now].size());i++)
if(vis[e[now][i]]==false)
dfs(e[now][i],now);
}
int POW[21];
int Count(int L,int R)
{
line temp; temp.l=L;
set<line>:: iterator t=mset.lower_bound(temp);
if((*t).r > R) return 0;
int now=(*t).no,ans=1;
for(int i=20;i>=0;i--)
if(l[fa[now][i]].r<=R and fa[now][i]!=0)
now=fa[now][i],ans+=POW[i];
return ans;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
l[i].l=read(),l[i].r=read(),l[i].no=i;
sort(l+1,l+1+n,cmp);
memset(use,1,sizeof use);
for(int i=1;i<=n;i++)
{
while(ms.empty()==false and l[ms.top()].r>=l[i].r)
{
use[ms.top()]=false;
ms.pop();
}
ms.push(i);
}
int to=-1;
for(int i=1;i<=n;i++)
if(use[i]==true and l[i].l>to)
{
ans++;
to=l[i].r;
}
for(int i=1;i<=n;i++) e[i].reserve(4);
for(int i=1;i<=n;i++)
if(use[i]==true)
{
mset.insert(l[i]);
bool OK=false;
for(int j=i+1;j<=n;j++)
if(use[j]==true and l[j].l>l[i].r)
{
e[l[j].no].push_back(l[i].no);
OK=true;
break;
}
if(OK==false)
e[0].push_back(l[i].no);
}
printf("%d\n",ans);
dfs(0,0);
sort(l+1,l+1+n,cmp2);
for(int i=0;i<=20;i++)
POW[i]=1<<i;
l[0].r=0x3f3f3f3f;
line tt;
tt.l=-1,tt.r=-1,tt.no=0; mset.insert(tt),used.insert(tt);
tt.l=0x3f3f3f3f,tt.r=0x3f3f3f3f;mset.insert(tt),used.insert(tt);
for(int i=1;i<=n;i++)
{
int L,R;
set<line>:: iterator t=used.lower_bound(l[i]);
if((*t).l<=l[i].r) continue;
R=(*t).l-1;
t--;
if((*t).r>=l[i].l) continue;
L=(*t).r+1;
if(Count(L,l[i].l-1)+Count(l[i].r+1,R)==Count(L,R)-1)
{
printf("%d ",i);
used.insert(l[i]);
}
}
return 0;
}
|
那怎么求一段区间的最大线段数呢？ 第一想法是前缀和？看起来很OK？ nope 因为不同区间中，里面的的初始线段会不同，以下这个图可以简单说明这种情况 
但是，我们可以发现一个很重要的特点： 每条线段的下一条可行线段是固定的 有了这个特点，我们就可以对路径做倍增，就可以在log的时间求出某一个区间的线段数。 至于求每一个区间的第一条线段，我们可以用set+lowbound的方法找。 这样子，你就可以嘴巴AC这道题啦 实际上你会花费大量的时间来调这道毒瘤题
