【题解】月儿的背包
题面：
月儿有一些背包
背包可以装背包
背包可以装装了背包的背包
背包可以装装了很多背包的背包...
具体来说，地上有n个位置
你可以看到每个位置上有一个背包，背包从1到n依次编号
一开始第i个背包里有ai个背包
现在月儿要整理一下背包
从第二个背包开始（第一个背包不用整理）
整理第i个背包的方法：
将该背包的前k个背包中所装背包最少的背包j中的背包取出（如果背包j中没有背包，则忽略）
（如果前方不足k个背包，则从第1个背包开始）
放入第i个背包
然后为了保持那个被取出了所有背包的背包j的整理完了的状态
月儿会从她的口袋里（她的口袋也是一个背包）掏出一些背包放入背包j中
使得背包j中的背包数量恢复
整理后，她想知道第n个位置有多少个背包
月儿想了101ms，觉得并不难 于是她不给你样例，并且将时限降至100ms
分析：
（单调队列模板题）
和天明的背包不同，月儿的背包整理是从前k个背包里，挑最少的背包放入（那就不能像天明那么无脑了）
那么我们该如何快速找出前k个背包中所装背包最少的背包呢
先看一个例子
k=3
整理背包时有如下情况
3 4 5 6 7（背包编号）
4 7 6 1 2（所装背包）
我们即将整理第6个背包
粗体为候选背包，设候选背包组成一个队列（会前后进出调整）
这时队列里有3个元素，分别对应背包编号3 4 5
当处理下一个背包时，队列里是4 5 6
编号3的背包出队了，很明显在队列里，左边的元素“存活时间”比右边的元素短
再回到队列3 4 5，对应背包数4 7 6
5背包存活时间比4背包长，而且5背包比4背包更“优秀”（在这里更小即是更优秀），那么在之后的整理中，4背包都不可能发挥作用直到出队，因为4背包在5背包就在，5背包又更优...（如果一个OIer比你小还比你强，你就可以退役了）
为了简化队列，在元素进入队列时就把队列末尾能淘汰的淘汰掉，直到最后一个元素比本元素优秀或队列为空，再把本元素入队，这样队列就一定是单调的，队头即是最优的（这就是单调队列），这样就能快速找出前k个背包中的目标
然后还要考虑元素出队，即将“存活时间”结束了的元素出队，操作很简单
在队列里，左边的元素“存活时间”比右边的元素短，所以从队头开始，如果队头元素“存活结束”，则出队，直到队头元素可以“存活”或队列为空
队列的元素可用结构体，两成员变量，数量v，“存活时间”l
本题结合单调队列依次整理背包即可
总结一下：单调队列的操作：添加（从队尾淘汰一些元素后添加一个元素，维持单调性），清除（从队头清除不该存在于队列中的元素），还要记得判断队列是否为空（不判断会爆）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node{
long long v,l;
} team[40005];//单调队列
long long n,k,a[40005],h,t;
void tin(long long v,long long l) {//添加元素的操作
while(h<=t) {//当队列不为空
if(v>team[t].v) break ;//队尾更优就跳出
t--;//队尾出队
}
++t;
team[t].v=v;
team[t].l=l;//添加
return ;
}
void tout(long long l) {
while(h<=t) {//当队列不为空
if(l<=team[h].l) break;//队头能存活跳出
h++;
}
return ;
}
int main() {
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
}
h=t=1;//初始化
team[1].v=a[1];
team[1].l=1;
for(int i=2;i<=n;i++) {
tout(i-k);//清除，负数也没关系
a[i]+=team[h].v;//放
tin(a[i],i);//添加
}
printf("%lld",a[n]+1);
return 0;
}