Lpl and Energy-saving Lamps【线段树求最左边小于k】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define cl(a) memset(a,0,sizeof(a))
typedef long long ll;
const int maxn = 100000+50;
const ll inf=1e18;
int n,m,q;
ll a[maxn];
struct state
{
    int ct,left;
}ans[maxn];
struct Node
{
    int l,r;
    ll val;
}node[4*maxn];
void pushup(int root)
{
    node[root].val=min(node[root*2].val,node[root*2+1].val);
}
void build(int root,int l,int r)
{
    if(l>r)return ;
    node[root].l=l;
    node[root].r =r;
    node[root].val = 0;
    if(l==r) node[root].val=a[l];
    else
    {
        int mid = l+(r-l)/2;
        build(root*2,l,mid);
        build(root*2+1,mid+1,r);
        pushup(root);
    }
}
void update(int root,int pos,ll val)
{
    if(node[root].l==node[root].r)
    {
        node[root].val = val;
        return;
    }
    int mid = node[root].l+(node[root].r-node[root].l)/2;
    if(pos<=mid) update(root*2,pos,val);
    if(pos>mid) update(root*2+1,pos,val);
    pushup(root);
}
int query(int root,int k)
{
    if(node[root].val>k)return 0;
    int l = node[root].l;
    int r = node[root].r;
    int ans = 0;
    if(node[root].l==node[root].r) return node[root].l;
    else
    {
        ans = query(root*2,k);
        if(!ans) ans = query(root*2+1,k);
        return ans;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    int cnt=0,all=0,day=0;
    while(cnt<n)
    {
        all+=m;
        day++;
        int t=query(1,all);
        while(t)
        {
            all-=a[t];
            cnt++;
            update(1,t,inf);
            t=query(1,all);
        }
        ans[day].ct = cnt;
        ans[day].left = all;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int d;
        scanf("%d",&d);
        if(d>day) d= day;
        printf("%d %d\n",ans[d].ct,ans[d].left);
    }
    return 0;
}