蒟蒻求条

#include <bits/stdc++.h>
using namespace std;
int ans=INT_MAX;
int l;
int s,t,m;
int dp[1000010];
struct Q{
	int num;
	int tim;
}q[1000010];
vector<int> stone;
int main(){
    cin>>l>>s>>t>>m;
    for(int i=1,x;i<=m;i++){
    	cin>>x;
    	stone.push_back(x);
	}
	sort(stone.begin(),stone.end());
	int last;
	if(stone[0]>s*t){
		dp[s*t]=1;
		last=s*t;
	}else{
		dp[stone[0]]=1;
		last=stone[0];
	}
	for(int i=1;i<stone.size();i++){
		if(stone[1]-stone[0]>=s*t){
			last+=s*t;
			dp[last]=1;
		}else{
			last+=stone[i]-stone[i-1];
			dp[last]=1;
		}
	}
	int head=1,tail=0;
	for(int i=1;i<=last+t;i++){
		if(i>=s){
			while(tail>=head and dp[i-s]<q[tail].num)--tail;
			q[++tail]={dp[i-s],i-s};
			while(q[head].tim<i-t)++head;
		}
		dp[i]+=q[head].num;
	}
	for(int i=last;i<=last+t;i++)ans=min(ans,dp[i]);
	cout<<ans;
    return 0;
}