666这题对我这种蒟蒻来说太难了（考场上甚至没看一眼）

考完后才发现 很容易得到一个 $O(nm)$ 的dp暴力，详见代码

inline int read(){//不判负数的快读！！
	int x=0; char c=getchar();
	while (c<'0' || c>'9'){
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}
inline int read_bool(){//卡常专用
	char c=getchar();
	while (c!='A' && c!='L'){
		c=getchar();
	}
	return (c=='A')?1:-1;//将A看做-1，将L看做1，用来维护前缀和
}
inline int abs(int x){
	return x>0?x:-x;
}

int main(){
	n=read(); m=read(); k=read();
	for (int i=1;i<=n;i++){
		sum[i]=sum[i-1]+read_bool();
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for (int i=1;i<=n;i++){
		for (int j=max(i-m+1,1);j<i;j++){//其实就是将 [i,j] 里的人分到同一辆车里
			if (abs(sum[i]-sum[j-1])<=k || abs(sum[i]-sum[j-1])==i-j+1){//符合转移的条件
				f[i]=min(f[i],f[j-1]+1);
			}
		}
	}
	printf("%d",f[n]);
	return 0;
}

这样做竟然能的 $80pts$ vvahning的数据太水了

听说有人使用了 $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;
}

一道题养活机房三代人

大体思路和 $O(nlogn)$ 是差不多的，这里给几个 Hint:

1.如果用单调队列去维护最小值，每个队列里最多有两个元素

2.区间求最小值是 $O(1)$ 的，可以在 $dp$ 的值域连续性上思考

回头会把这个坑填上

主播主播，你的 $multiset$ 确实不会炸空间，那我非要开 $1e6$ 个双端队列可不可以呢？

可以的兄弟，可以的

你注意到我往双端队列里插入的东西其实可以用 $vector$ 摸你的。

我们考虑每个叶子开一个 $vector$ ，一个 $top$ ，表示当前的队头。

出队直接 $top++$，入队直接 $pushback$ ，$popback$ 直接删队尾，（$vector$ 删除队尾是 $O(1)$）

至于我 $WA$ 一个点，是因为是因为我在转移一个车全部一种人的时候只考虑了尽可能长的段，但实际上需要用单调队列维护一下。

这样跑貌似比某个 名字里带 $Gram$ 的老哥的 $multiset$ 的做法快了那么一倍

CODE

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
int tr[1000005<<2];
int f[1000005],S[1000005];
vector<int>dq[1000005];
int top[1000005];
int n,m,k,lim;
void build(int rt,int l,int r){
	tr[rt]=1000000000;
	if(l==r)return;
	int mid=l+r>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
}
void update(int rt,int l,int r,int x,int k){
	if(l==r){
		int id=l+n; 
		if(k>=0){
			int id=l+=n;
			while(top[id]<dq[id].size()&&f[dq[id][dq[id].size()-1]]>=f[k]){
				vector<int>::iterator it=dq[id].end();it--;
				dq[id].erase(it);
			}
			dq[id].push_back(k);
		}else{
//			cout<<x<<" "<<lim<<" "<<dq[id].front()<<endl<<endl;
			while(top[id]<dq[id].size()&&dq[id][top[id]]<=lim)top[id]++;
		}
		if(top[id]<dq[id].size())tr[rt]=f[dq[id][top[id]]];
		else tr[rt]=1000000000;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)update(lson,l,mid,x,k);
	else update(rson,mid+1,r,x,k);
	tr[rt]=min(tr[lson],tr[rson]);
}int query(int rt,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return tr[rt];
	}
	int mid=l+r>>1,ans=100000000;
	if(x<=mid)ans=min(ans,query(lson,l,mid,x,y));
	if(y>mid)ans=min(ans,query(rson,mid+1,r,x,y));
	return ans;
}deque<int>dqq;
int main(){
//	freopen("E_ex.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	build(1,-n,n);
	update(1,-n,n,S[0],0);
	int cnt=0;
	char last=0;
	lim=0;
	dqq.push_back(0);
	for(int i=1; i<=n; i++){
		char ch[10];scanf("%s",ch);
		S[i]=S[i-1]+(ch[0]=='A'?1:-1);
		if(ch[0]==last)cnt++;
		else cnt=1;
		cnt=min(cnt,m);
		
		while(dqq.size()&&i-dqq.front()>cnt)dqq.pop_front();
//		cout<<dqq.size()<<endl;
		f[i]=f[dqq.front()]+1;
		if(i-lim>m){
			update(1,-n,n,S[lim],-1);
			lim++;
		}f[i]=min(f[i],query(1,-n,n,S[i]-k,S[i]+k)+1);
		update(1,-n,n,S[i],i);
		last=ch[0];
		while(dqq.size()&&f[i]<=f[dqq.back()])dqq.pop_back();
		dqq.push_back(i);
	}cout<<f[n];
	return 0;
}