JZOJ 6159 麻雀

根据题意，我们知道每个位置都是非负整数（你搞个负数只麻雀出来）……
于是当两个区间互相包含时，小的区间是没用的。
所以至多有 n 个区间，我们按照它们的左端点来维护。

我们用线段树来维护每个左端点对应的最大右端点的区间，以及它的区间和。

对于第一个操作，在线段树上二分找包含这个点的最靠左的区间。
然后把它的左端点到修改点这一段全部加 y（不必考虑没有贡献的区间，它们对答案没有影响）。

对于第二个操作，直接塞进线段树。

同时用一个树状数组维护区间和。

代码：

#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 5e5;
int n,m,c[N + 5];
inline void update(int x,int k)
{
    for(;x <= n;x += lowbit(x))
        c[x] += k;
}
inline int query(int x)
{
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret += c[x];
    return ret;
}
struct node
{
    int max,val,tag;
    int ls,rs;
} seg[(N << 2) + 10];
int rt,seg_tot;
inline void push(int p)
{
    if(seg[p].tag)
    {
        if(!seg[p].ls)
            seg[p].ls = ++seg_tot;
        seg[seg[p].ls].val += seg[p].tag,seg[seg[p].ls].tag += seg[p].tag;
        if(!seg[p].rs)
            seg[p].rs = ++seg_tot;
        seg[seg[p].rs].val += seg[p].tag,seg[seg[p].rs].tag += seg[p].tag;
        seg[p].tag = 0;
    }
}
void insert(int x,int k,int v,int &p,int tl,int tr)
{
    if(!p)
        p = ++seg_tot;
    seg[p].max = max(seg[p].max,k),seg[p].val = max(seg[p].val,v);
    if(tl == tr)
        return ;
    push(p);
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,v,seg[p].ls,tl,mid) : insert(x,k,v,seg[p].rs,mid + 1,tr);
}
void update(int l,int r,int k,int &p,int tl,int tr)
{
    if(!p)
        p = ++seg_tot;
    if(l <= tl && tr <= r)
    {
        seg[p].val += k,seg[p].tag += k;
        return ;
    }
    push(p);
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
    r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
    seg[p].val = max(seg[seg[p].ls].val,seg[seg[p].rs].val);
}
int query(int x,int p,int tl,int tr)
{
    if(tl == tr)
        return tl;
    push(p);
    int mid = tl + tr >> 1;
    if(seg[seg[p].ls].max >= x)
        return query(x,seg[p].ls,tl,mid);
    else
        return query(x,seg[p].rs,mid + 1,tr);
}
int main()
{
    freopen("sparrow.in","r",stdin),freopen("sparrow.out","w",stdout);
    scanf("%d%d",&n,&m);
    int op,x,y;
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1)
        {
            update(x,y);
            if(seg[rt].max >= x)
            {
                int l = query(x,rt,1,n);
                update(l,x,y,rt,1,n);
            }
        }
        else
            insert(x,y,query(y) - query(x - 1),rt,1,n);
        printf("%d\n",seg[rt].val);
    }
}