Lpl and Energy-saving Lamps ( 线段树 求第一个小于等于k的数）

传送门：https://vjudge.net/contest/349835#problem/A

题意

　　长度为n的序列代表每个房间的灯泡需求，k为每个月新获得的灯泡，从左往右找当手头的灯泡>=房间的需求时为房间更换灯泡，若没有房间满足则留着下一个月用，q次询问，回答在第i个月装修了多少个房间，手头上的灯泡还剩多少。

思路

　　线段树维护区间最小值，月份数可达1e5，预处理每一个月份的答案，每个月份用logn的时间从左往右找可以装修的房间，找到则维护答案并单点更新叶子结点为inf代表去除该结点，记录ans数组最后输出就行。

AC代码

#include<iostream>
#include<math.h>
const int maxn=1e5+50;
const int inf=0X3f3f3f3f;
using namespace std;

int n,m,q;
int a[4*maxn],A[maxn],que[maxn];

struct node{
    int num;
    int res;
}ans[maxn];

void pushup(int rt){
    a[rt]=min(a[rt<<1],a[rt<<1|1]);
}

void build(int l,int r,int rt){
    if(l==r){
        a[rt]=A[l];
        return;
    }
    int m=l+r>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}

void updata(int p,int x,int l,int r,int rt){
    if(l==r){
        a[rt]=x;
        return;
    }
    int m=l+r>>1;
    if(p<=m)
        updata(p,x,l,m,rt<<1);
    else
        updata(p,x,m+1,r,rt<<1|1);
    pushup(rt);
}

int query(int x,int l,int r,int rt){//从左到右查找第一个大于x的叶子节点位置
    if(a[rt]>x){
        //cout<<"现在的rt"<<rt<<" "<<x<<endl;
        return 0;
    } 
    int m=l+r>>1;
    if(l==r) return l;
    else{
        if(a[rt<<1]<=x)        query(x,l,m,rt<<1);
        else if(a[rt<<1|1]<=x) query(x,m+1,r,rt<<1|1);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>A[i];
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>que[i];
    }
    build(1,n,1);
    int nnum=0,nres=0;
    for(int i=1;i<=1e5+10;i++){
        if(nnum>=n){
            ans[i].num=nnum;
            ans[i].res=nres;
            continue;
        }
        nres+=m;
        while(nres){
            int index=query(nres,1,n,1);
            //cout<<"现在的下标"<<index<<endl;
            if(index==0) break;
            nnum++;nres-=A[index];
            updata(index,inf,1,n,1);
        }
        ans[i].num=nnum;
        ans[i].res=nres;
    }
    for(int i=1;i<=q;i++){
        cout<<ans[que[i]].num<<" "<<ans[que[i]].res<<'
';
    }
    return 0;
}