首先会发现若 \(t_i <= T\) 的话那么他最终一定会造反。
我们只考虑 \(t_i >T\) 的情况。设 \(lst_i\) 表示 \(i\) 左边第一个可以影响（使他造反）到 \(i\) 的位置，那么我们一定要在 \([lst_i,i]\) 这个区间中的某一个位置放上床垫才能使 \(i\) 不造反。
这样有一个 \(O(nd)\) 的 dp，但是复杂度显然会炸。考虑挖掘一些性质，会发现所有区间都是包含或者不交的。证明也比较简单，若两个区间有交，即 \(i<j,lsti \le lst_j \le i\)，那么 \(lst_j\) 这个位置也一定能影响到 \(i\)，矛盾。所以任意两个区间都不交叉。
那么我们按照区间的包含关系建图，就变成一个森林。考虑转化题意，若在叶子节点的区间中放一个床垫，那么它到根节点的路径上的所有点都不会造反了。所以题意转化为求 \(d\) 条不相交的链，使得这些链的总长度最大。直接长链剖分，然后取前 \(d\) 长的链即可。
求 \(lst\) 数组以及连边都可以用单调栈维护，最终求前 \(d\) 长链可以用优先队列维护，时间复杂度 \(O(n+d \log n)\)。
关于取前 \(d\) 长的链的证明：对于两条不是最长链的链，我们都可以把它换成最长链加另外一条链，这样总长度一定不劣（画个图更容易理解）。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 10;
int n,d,T,t[MAXN],lst[MAXN],ans,fa[MAXN];
int head[MAXN],cnt,depth[MAXN],son[MAXN],mx[MAXN];
struct Node {int u,v,nxt;}e[MAXN << 1];
void Add(int u,int v) {e[++cnt] = {u,v,head[u]};head[u] = cnt;}
priority_queue <int,vector <int>,less <int> > q;
void dfs(int u,int father) {
depth[u] = depth[father] + 1,mx[u] = depth[u];
for(int i = head[u]; ~ i;i = e[i].nxt) {
int now = e[i].v;
if(now == father) continue;
dfs(now,u),mx[u] = max(mx[u],mx[now]);
if(mx[now] > mx[son[u]]) son[u] = now;
}
} void sdfs(int u,int father,int len) {
if(son[u] == 0) return q.push(len);
sdfs(son[u],u,len + 1);
for(int i = head[u]; ~ i;i = e[i].nxt)
if(e[i].v != father && e[i].v != son[u]) sdfs(e[i].v,u,1);
} stack <int> s;
signed main() {
memset(head,-1,sizeof head);
cin >> n >> d >> T;
for(int i = 1;i <= n;i++) cin >> t[i];
for(int i = 1;i <= n;i++)
if(t[i] > T) {
while(s.size() && t[s.top()] + i - s.top() > T) s.pop();
if(s.size()) lst[i] = s.top();
} else {
while(s.size() && t[s.top()] + i - s.top() >= t[i]) s.pop();
s.push(i);
}
while(!s.empty()) s.pop();
for(int i = n;i >= 1;i--) {
if(lst[i] == 0) continue;
while(!s.empty() && lst[s.top()] > lst[i]) s.pop();
if(!s.empty()) Add(s.top(),i),fa[i] = s.top();
s.push(i);
} for(int i = 1;i <= n;i++) {
if(t[i] <= T) continue;
if(lst[i] == 0) ans++;
else if(fa[i] == 0) dfs(i,0),sdfs(i,0,1);
} while(d > 0 && !q.empty())
ans += q.top(),q.pop(),d--;
cout << n - ans;
return 0;
}