https://www.cnblogs.com/violet-acmer/p/9720603.html
变量解释：
need[ i ] : 第 i 个房间含有的旧灯泡个数。
remain[ i ] : 第 i 月后，换完满足条件的房间的旧灯泡后剩余节能灯泡的个数。
total[ i ] : 前 i 个月换灯泡的房间数。
题意：
有n个房间，每个房间都有need[ i ] 个旧灯泡等着男主角去换，男主角Lpl每个月都会购买m个节能灯泡，按照输入顺序给房间换灯泡，如果当前房间满足条件，则全部换完，不满足，跳到下一个房间，重复当前步骤。
如果当前房间并不能将新灯泡全部用完，则留着新灯泡给下个月使用。
有q个询问，每个询问给你一个值mon，代表当前月，输出[1,mon]月换灯泡的房间个数，以及还玩灯泡后新灯泡的剩余个数。
题解：
最简单的方法就是暴力，从第一个月开始枚举所有的房间，知道所有的房间都换完，或来到询问的最大月份，毋庸置疑，此操作的时间复杂度为O(max_mon*n)，而本题的数据范围为1~1e5，显然会超时，1e5需要的实践复杂度至多为n*logn。
换个思路，考虑一下线段树。
线段树中当前结点的val值存储的是左右孩子中需要换灯泡的最小值，对于第 i 个月份，优先更新满足条件的左孩子区间，当左孩子不满足条件是，回溯到右孩子区间，直到不满足条件跳出递归。
对于满足条件的房间，在更换完灯泡后，将其val值设为最大值INF，并向上更新其父亲的val。
具体细节，看代码............
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1 | 1)
#define INF 0x3f3f3f3f
const int maxn=1e5+; int need[maxn];
int remain[maxn];
int total[maxn];
int lamps;//当前月份的新灯泡数量
int sum;//前 i 个月可以换灯泡的房间数
struct Node1
{
int l,r;
int val;
int mid(){
return l+((r-l)>>);
}
}segTree[*maxn];
void pushUp(int pos)
{
segTree[pos].val=min(segTree[ls(pos)].val,segTree[rs(pos)].val);
}
void buildTree(int l,int r,int pos)
{
segTree[pos].l=l,segTree[pos].r=r;
if(l == r)
{
segTree[pos].val=need[l];
return ;
}
int mid=l+((r-l)>>);
buildTree(l,mid,ls(pos));
buildTree(mid+,r,rs(pos));
pushUp(pos);
}
void update(int pos,int i)
{
if(segTree[pos].l == segTree[pos].r && segTree[pos].val <= lamps)
{
lamps -= segTree[pos].val;
segTree[pos].val=INF;//当前房间换完灯泡后，设置成最大值
pushUp(pos>>);//向上更新 sum++;//可以更换的房间数 ++
return ;
}
if(segTree[pos].val <= lamps)
{
if(segTree[ls(pos)].val <= lamps)//优先判断左孩子是否满足条件
update(ls(pos),i);
update(rs(pos),i);
}
pushUp(pos>>);//向上更新
}
void init()
{
lamps=;
sum=;
memset(remain,,sizeof(remain));
memset(total,,sizeof(total));
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=;i <= n;++i)
scanf("%d",need+i);
buildTree(,n,); for(int i=;i <= ;++i)//月份最多是100000
{
lamps=remain[i-]+m;
update(,i);
remain[i]=(total[i-] == n ? remain[i-]:lamps);//更新当前月份的剩余新灯泡数量
total[i]=sum;//更新前 i 个月可以更换的房间数
}
int q;
scanf("%d",&q);
for(int i=;i <= q;++i)
{
int mon;
scanf("%d",&mon);
printf("%d %d\n",total[mon],remain[mon]);
}
}
}