10897 Conveyor Belt

方法

维护一个数组,每次任务添加时将任务的区间内同时加上任务的个数,然后可以发现这个数组的值加上下标(从0开始)中的最大值就是答案
因此可以使用线段树维护区间加与查询最大值的操作,此时需要将树建成初始值为下标-1,然后每次操作后查询区间[l,r] \left(l=1,r=max(b[i]) \right)内的最大值即可。

实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int lqx[N];
struct SegmentTree
{
    int l,r;
    ll add,mx;
}t[N<<2];
void update(int p)
{
    if(t[p].add)
    {
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p*2].mx+=t[p].add;
        t[p*2+1].mx+=t[p].add;
        t[p].add=0;
    }
}
void change(int p,int l,int r,int d)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].add+=d;
        t[p].mx+=d;
        return;
    }
    update(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        t[p].mx=lqx[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
}
ll ask(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].mx;
    update(p);
    int mid=(t[p].l+t[p].r)/2;
    ll val=0;
    if(l<=mid) val=max(val,ask(p*2,l,r));
    if(r>mid) val=max(val,ask(p*2+1,l,r));
    return val;
}
int main()
{
    int n,q,a,b,p,r=0;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=100000;i++) lqx[i]=i-1;
    build(1,1,100000);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&a,&b,&p);
        change(1,a,b,p);
        r=max(r,b);
        printf("%lld\n",ask(1,1,r));
    }
    return 0;
}