1. 人品rmq

· · 题解

首先因为我们先修改再查询，这个问题实际上是二维的。

那么不妨考虑将整个平面直角坐标系的横轴看时间轴，纵轴看成序列，那么相当于有 n 个版本的序列，修改则是对一段时间轴上的序列的一段区间全部加上一个值，查询类似，求最大值。

先考虑一个暴力的想法，我们能否维护所有时刻的序列呢？

先分析修改，我们考虑扫描线掉。将修改 (l_1,r_1,l_2,r_2,x) 看做在 l_1 时刻，对 [l_2,r_2] 执行区间加 x；在 r_1+1 时刻，对 [l_2,r_2] 执行区间减 x。

然后再考虑修改，用类似的思路，假设初始的序列是 l_1 时刻的序列，那么我们从 l_1 开始，r_1 结束进行每个时刻进行的操作，每次求出 [l_2,r_2] 的最大值。查询这么多遍肯定不优美，注意到这是个历史最大值的问题，可以用吉司机线段树做。我们一样的把询问挂到时间轴上，每次从每个时间开始做修改，在某个位置查询即可。

这是一个看起来可以优化的暴力的思路。不妨考虑一个弱化的问题，询问都跨过同一个时间点。将询问拆成两部分，放在时间点 l1,r1 上。我们可以从这个时间点开始，向左/向右依次执行操作，一个询问的答案就是两次的查询出的最大值。

我们考虑一些分治方法来解决这个问题。只需要不重不漏地找到分割点且可以优秀地回答上面的问题就好了。于是考虑猫树分治。

树上的每一个结点存下子树内都会执行的操作，以及当前结点需要做的操作。询问则挂在第一个中点在询问间的结点。剩下的就是直接做了。

注意到这样的话每个位置的操作和查询只会执行 O(\log n) 次，那么复杂度是 O(n \log^2n) 的。

有一些小细节，比如修改应该先减再加（不然历史最大值会出错），以及每次线段树的复原（每个结点的历史最大值及其标记变为当前的值及标记，注意到 push_down 要主动下放直到孙子结点，即两层下放），可以参考代码实现。

void insmodify(LL l,LL r,LL now,LL x,LL y,LL id)
{
    if(x<=l && r<=y)    return trm[now].push_back(id);
    tre[now].push_back(id);
    Mm;
    if(x<=mid)  insmodify(l,mid,lc(now),x,y,id);
    if(mid<y)   insmodify(mid+1,r,rc(now),x,y,id);
}
void insquery(LL l,LL r,LL now,LL x,LL y,LL id)
{
    Mm;
    if(l==r || (x<=mid && mid<y))   return req[now].push_back(id);
    if(x<=mid)  insquery(l,mid,lc(now),x,y,id);
    else    insquery(mid+1,r,rc(now),x,y,id);
}
struct segTree{
    struct node{
        LL l,r;
        LL maxn;
        LL bmax;
        LL ta,tb;
    }tr[2000005];
    bool tag[2000005];
    inline void push_up(LL now){tr[now].bmax=max(tr[lc(now)].bmax,tr[rc(now)].bmax),tr[now].maxn=max(tr[lc(now)].maxn,tr[rc(now)].maxn);}
    inline void reset(LL u){tr[u].bmax=tr[u].maxn,tr[u].tb=tr[u].ta,tag[u]=true;}
    void push_tag(LL now,LL ta,LL tb,bool flag=false)
    {
        if(!flag && tr[now].l!=tr[now].r && tag[now])   push_down(now,true);
        tr[now].bmax=max(tr[now].bmax,tr[now].maxn+tb),tr[now].tb=max(tr[now].tb,tr[now].ta+tb),tr[now].maxn+=ta,tr[now].ta+=ta;
    }
    void push_down(LL now,bool flag=false)
    {
        if(tr[now].ta || tr[now].tb)    push_tag(lc(now),tr[now].ta,tr[now].tb,flag),push_tag(rc(now),tr[now].ta,tr[now].tb,flag),tr[now].ta=tr[now].tb=0;
        if(tag[now])    reset(lc(now)),reset(rc(now)),tag[now]=false;
    }
    void build(LL l,LL r,LL now)
    {
        tr[now].l=l,tr[now].r=r;
        tr[now].ta=tr[now].tb=0;
        if(l==r)
        {
            tr[now].maxn=tr[now].bmax=0;
            return ;
        }
        Mm;
        build(l,mid,lc(now)),build(mid+1,r,rc(now));
        push_up(now);
    }
    void modify(LL now,LL x,LL y,LL k)
    {
        LL l=tr[now].l,r=tr[now].r;
        if(x<=l && r<=y)    return push_tag(now,k,k);
        push_down(now);
        Mm;
        if(x<=mid)  modify(lc(now),x,y,k);
        if(mid<y)   modify(rc(now),x,y,k);
        push_up(now);
    }
    LL query(LL now,LL x,LL y)
    {
        LL l=tr[now].l,r=tr[now].r;
        if(x<=l && r<=y)    return tr[now].bmax;
        push_down(now);
        Mm;
        LL ret=0;
        if(x<=mid)  ret=max(query(lc(now),x,y),ret);
        if(mid<y)   ret=max(query(rc(now),x,y),ret);
        return ret;
    }
}segt;
vector<LL> catQ[50005],add[50005],sub[50005];
void Solve(LL now,LL l,LL r)
{
    Mm;
    for(auto id:trm[now])   segt.modify(1,mdf[id].rp,mdf[id].rq,mdf[id].v);
    if(l^r) Solve(lc(now),l,mid),Solve(rc(now),mid+1,r);
    if(req[now].empty())
    {
        for(auto id:trm[now])   segt.modify(1,mdf[id].rp,mdf[id].rq,-mdf[id].v);
        return ;
    }
    for(auto id:req[now])   catQ[qry[id].lp].push_back(id),catQ[qry[id].lq].push_back(id);
    for(auto id:tre[now])
    {
        LL L=mdf[id].lp,R=mdf[id].lq;
        if(R<=mid)
        {
            add[R].push_back(id);
            sub[max(L-1,l-1)].push_back(id);
        }
        else if(L>mid)
        {
            add[L].push_back(id);
            sub[min(R+1,r+1)].push_back(id);
        }
        else
        {
            add[mid].push_back(id);
            add[mid+1].push_back(id);
            sub[max(L-1,l-1)].push_back(id);
            sub[min(R+1,r+1)].push_back(id);
        }
    }
    segt.reset(1);
    for(LL i=mid;i>=l-1;--i)
    {
        for(auto id:sub[i]) segt.modify(1,mdf[id].rp,mdf[id].rq,-mdf[id].v);
        for(auto id:add[i]) segt.modify(1,mdf[id].rp,mdf[id].rq,mdf[id].v);
        if(i!=l-1)  for(auto id:catQ[i])    ans[id]=max(ans[id],segt.query(1,qry[id].rp,qry[id].rq));
    }
    segt.reset(1);
    for(LL i=mid+1;i<=r+1;++i)
    {
        for(auto id:sub[i]) segt.modify(1,mdf[id].rp,mdf[id].rq,-mdf[id].v);
        for(auto id:add[i]) segt.modify(1,mdf[id].rp,mdf[id].rq,mdf[id].v);
        if(i!=r+1)  for(auto id:catQ[i])    ans[id]=max(ans[id],segt.query(1,qry[id].rp,qry[id].rq));
    }
    for(LL i=l;i<=r;++i)    catQ[i].clear();
    for(LL i=l-1;i<=r+1;++i)    sub[i].clear(),add[i].clear();
    for(auto id:trm[now])   segt.modify(1,mdf[id].rp,mdf[id].rq,-mdf[id].v);
}