听说有人使用了 $5\times10^5$ 个 dequeue，然后炸空间了，乐。

听说把空间开大后还是会 WA 一个点，更乐了。

首先这是一个 dp，最简单的 dp 式子是显然的，设 $f_i$ 表示对于前 $i$ 个人需要的最少巴士数量，于是就有一个 $O(nm)$ 的暴力 dp：

$$f_i=\min_{j=\max\{i-m,0\} \wedge \text{sum}_i-\text{sum}_j\in[-k,k]}^{i-1}\{f_j\}+1 $$

其中 $\text{sum}_j$ 表示前缀和（把 A 视为 +1，把 L 视为 -1）。

考虑优化，注意到转移点限制与 $\text{sum}$ 有关，不难想到用线段树维护对应 $\text{sum}$ 上最小的 $f$ 值。

但是还有一个 $m$ 的限制没有处理，所以对应的 $\text{sum}$ 上还需额外维护一个在当前情况下的最小值，类似滑动窗口状物，并随着 $i$ 的增加动态修改（实际上你直接丢进 multiset 里面就行了）。

你发现你做完了，时间复杂度 $O(n\log n)$。

分析一下这道题的本质，实际上就是把 $\text{sum}$ 和下标看成两维，转移的时候取的是一个矩形 $\min$，使用线段树的维护不过是将其降维了而已。

哦对了，这题实际上还有加强版，$n,m\le10^7$，要求时间复杂度线性，你们可以想想怎么做，加油。

#include <iostream>
#include <set>
#define ll int
#define mid ((l+r)>>1)
using namespace std;
const ll N=3e5+10;
const ll INF=998244353;
string s;
ll f[N],n,m,k,num[N],sum[N],tot;
ll lc[N<<3],rc[N<<3],mx[N<<3],head;
ll lst[N];
multiset<ll> st[(N<<1)+2];
multiset<ll> chk;
void build(ll l,ll r,ll &x){
	if(!x) x=++tot;
	if(l==r){mx[x]=INF;return;}
	build(l,mid,lc[x]);
	build(mid+1,r,rc[x]);
	mx[x]=INF;
}
ll get_mx(ll L,ll R,ll l,ll r,ll x){
	if(L<=l&&r<=R) return mx[x];
	ll ret=INF;
	if(L<=mid) ret=min(ret,get_mx(L,R,l,mid,lc[x]));
	if(R>mid) ret=min(ret,get_mx(L,R,mid+1,r,rc[x]));
	return ret;
}
void pop_out(ll p,ll v,ll l,ll r,ll x){
	if(l==r&&l==p){
		multiset<ll>::iterator it;
		if((it=st[p].find(v))!=st[p].end()) st[p].erase(it);
		mx[x]=*st[p].begin();
		return;
	}
	if(p<=mid) pop_out(p,v,l,mid,lc[x]);
	else pop_out(p,v,mid+1,r,rc[x]);
	mx[x]=min(mx[lc[x]],mx[rc[x]]);
}
void push_in(ll p,ll v,ll l,ll r,ll x){
	if(l==r&&l==p){
		st[p].insert(v);
		mx[x]=*st[p].begin();
		return;
	}
	if(p<=mid) push_in(p,v,l,mid,lc[x]);
	else push_in(p,v,mid+1,r,rc[x]);
	mx[x]=min(mx[lc[x]],mx[rc[x]]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(ll i=1;i<=n;i++){
		cin>>s; 
		num[i]=(s[0]=='L'?-1:1);
		sum[i]=sum[i-1]+num[i];
		if(i==1) lst[i]=0;
		else{
			if(num[i]==num[i-1]) lst[i]=max(lst[i-1],i-m);
			else lst[i]=i-1;
		}
	}
	for(ll i=0;i<=(N<<1);i++) st[i].insert(INF);
	build(1,N<<1,head);
	f[0]=0;
	push_in(sum[0]+N,f[0],1,N<<1,head);
	ll lL=0;
	chk.insert(0),chk.insert(INF);
	for(ll i=1;i<=n;i++){
		if(i>m)	pop_out(sum[i-m-1]+N,f[i-m-1],1,N<<1,head);
		while(lst[i]>lL){
			multiset<ll>::iterator it;
			if((it=chk.find(f[lL]))!=chk.end()) chk.erase(it);
			lL++;
		}
		f[i]=(*chk.begin())+1;
		f[i]=min(f[i],get_mx(sum[i]+N-k,sum[i]+N+k,1,N<<1,head)+1);
		push_in(sum[i]+N,f[i],1,N<<1,head);
		chk.insert(f[i]);
	}
	cout<<f[n];
	return 0;
}