[loj3561]The short shank; Redemption

记$L_{i}=\max_{1\le j

换言之，即在$D$个位置放床垫，并最大化$[L_{i},i)$内存在床垫的$i$数量

注意到不存在$L_{i}

进一步的，即区间关系仅有包含或相离，对每一个区间将包含其的最小区间作为其父亲，得到一棵森林

此时，问题即选择$D$个叶子，覆盖其到根的路径，长链剖分后取最长的$D$条链即可

细节上，注意特判$L_{i}$不存在和$L_{i}=i$的情况

时间复杂度为$o(n)$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 2000005
 4 vector<int>v0,v[N];
 5 int n,D,T,ans,a[N],st[N],L[N],dep[N],son[N],cnt[N];
 6 int read(){
 7     int x=0;
 8     char c=getchar();
 9     while ((c<'0')||(c>'9'))c=getchar();
10     while ((c>='0')&&(c<='9')){
11         x=x*10+c-'0';
12         c=getchar();
13     }
14     return x;
15 }
16 void dfs1(int k){
17     dep[k]=1;
18     for(int i=0;i){
19         dfs1(v[k][i]);
20         if (dep[v[k][i]]+1>dep[k]){
21             dep[k]=dep[v[k][i]]+1;
22             son[k]=v[k][i];
23         }
24     }
25 }
26 void dfs2(int k,int t){
27     if (son[k])dfs2(son[k],t);
28     if (k==t)v0.push_back(dep[k]);
29     for(int i=0;i)
30         if (v[k][i]!=son[k])dfs2(v[k][i],v[k][i]);
31 }
32 int main(){
33     n=read(),D=read(),T=read();
34     for(int i=1;i<=n;i++)a[i]=read()-i;
35     for(int i=1;i<=n;i++){
36         while ((st[0])&&(a[st[st[0]]]>min(a[i],T-i)))st[0]--;
37         if (a[i]<=T-i)st[++st[0]]=i;
38         if (st[0])L[i]=st[st[0]];
39         else ans++,L[i]=i;
40     }
41     st[0]=0;
42     for(int i=n;i;i--){
43         if (L[i]==i)continue;
44         while ((st[0])&&(L[st[st[0]]]>L[i]))st[0]--;
45         if (st[0])v[st[st[0]]].push_back(i);
46         st[++st[0]]=i;
47     }
48     for(int i=n;i;i--)
49         if ((L[i]dep[i]))dfs1(i),dfs2(i,i);
50     for(int i=0;i;
51     for(int i=n;i;i--)
52         while ((D)&&(cnt[i]))D--,cnt[i]--,ans+=i;
53     printf("%d\n",n-ans);
54     return 0;
55 }