线段树的高级应用

标记与信息的抽象化

我们要实现标记与标记，信息与信息，标记与信息的合并。

标记与标记：原来的懒标记与新的懒标记之间的合并。push_down

标记的信息：原来的信息与新的懒标记之间的合并。push_down

信息与信息：主要涉及push_up的操作。

幺半群

简单来说，就是有幺元与运算满足结合律的群。线段树的标记与信息都是幺半群。

为什么在线段树上要满足结合律，因为你标记统计起来再下放要与一个一个下放一样的。

矩阵

线段树标记与信息的合并可以用矩阵的思路比如区间加乘求和：

[sum,len]$ $[mul,0,add,1]

思考：区间加区间乘区间历史和？

NOIP2022 比赛

题意：给定两个排列 a , b 。然后给定 Q 个询问 [l,r] 然后对于每一个可能的 l\ge p\ge q\ge r 的 p,q ,找出 [p,q] 中 a 的最大值与 b 的最大值乘积的和。

我们就可以预处理 A_{i,j} 表示 [j,i] 这个区间内的最大值，所以说每次只需要再之前找第一个大于等于 a_i 了，然后之后的就是之前那个的答案。然后 A_i 对 A_{i-1} 的影响就是这一段区间内的最大值赋值。

然后我们查询按右端点排序之后就转化为了区间覆盖--区间历史和问题。

就是 A,B 的区间覆盖，然后查询 C=A\times B 的历史和就行。

我们设计信息

[len,sumA,sumB,sumC,hsumC]$ 然后我们找到一个区间的 $A$ 被全部覆盖或 $B$ 被全部覆盖。然后$sumC=sumA\times sumB/len

那么我们对于每一次 r 的扩大，我们要执行如下操作：

1. 更新a
2. 更新b
3. 将 [1,r] 的 f_i 都加上 a_i\times b_i : 就是说又有线段以它为起点。

我们每次就要查询区间 [l,r] 上的历史区间和。

我们对于后面的要快速求出 \sum\limits_{i=l}^{r}a_i\times b_i 那么我们在进行覆盖时比如说区间覆盖 x ,然后就是更新为x\times sum(y) 如果两个都满足，就是x\times y\times len 就行，注意标记的出现的位置。

#include<bits/stdc++.h>
#define mid (l+r)/2
#define lc x<<1
#define rc x<<1|1
#define int unsigned long long
using namespace std;
const int maxn=25e4+5;
int T,n,a[maxn],b[maxn],ans[maxn];
struct query{int l,r;}q[maxn];
bool cmp(query a,query b){return a.r<b.r;}
struct Que{int ll,id;};
vector<Que> Qu[maxn];
struct Tag{
    int a,b,lh,ah,bh,ch;
    void apply(const Tag &r){
        *this={
            r.a?:a,//如果说标记后加入，那么它在后面进行覆盖
            r.b?:b,
            lh+r.lh+a*r.ah+b*r.bh+a*b*r.ch,
            ah+(a?0:r.ah+b*r.ch),
            bh+(b?0:r.bh+a*r.ch),
            ch+((a||b)?0:r.ch)
        };
    }
};
struct Info{
    int suma,sumb,sumc,hsum;
    void apply(const Tag &r,int len){
        hsum+=len*r.lh+suma*r.ah+sumb*r.bh+sumc*r.ch;
        suma=(r.a?len*r.a:suma);sumb=(r.b?len*r.b:sumb);
        sumc=len*r.a*r.b+(r.a?0:r.b*suma)+(r.b?0:r.a*sumb)+(r.b||r.a ?0:sumc);
    }
    Info operator +(const Info &r) const{
        return {suma+r.suma,sumb+r.sumb,sumc+r.sumc,hsum+r.hsum};
    }
};
stack<int> sta,stb;
Info Tr[maxn<<2];
Tag tag[maxn<<2];
int Q;
void update(int x,int l,int r,const Tag &xx){
    Tr[x].apply(xx,r-l+1);
    tag[x].apply(xx);//表示对于两个进行操作
}
void push_down(int x,int l,int r){
    update(lc,l,mid,tag[x]),update(rc,mid+1,r,tag[x]);
    tag[x]=(Tag){0,0,0,0,0,0};//表示形成幺元
}
void push_up(int x){Tr[x]=Tr[lc]+Tr[rc];}
void build(int x,int l,int r){
    if(l==r) return;
    build(lc,l,mid),build(rc,mid+1,r);//表示这里    
}
void cover(int x,int l,int r,int ql,int qr,const Tag &xx){
    if(l>qr||r<ql) return;
    if(l>=ql&&r<=qr){
        update(x,l,r,xx);
        return;
    }
    push_down(x,l,r);
    cover(lc,l,mid,ql,qr,xx);
    cover(rc,mid+1,r,ql,qr,xx);
    push_up(x);
}
int query(int x,int l,int r,int ql,int qr){
    if(l>qr||r<ql) return 0;
    if(l>=ql&&r<=qr) return Tr[x].hsum;
    push_down(x,l,r);
    return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    cin>>Q;
    for(int i=1;i<=Q;++i){
        cin>>q[i].l>>q[i].r;
        Qu[q[i].r].push_back((Que){q[i].l,i});//表示这里的
    }
    sort(q+1,q+Q+1,cmp);
    build(1,1,n);
    for(int r=1;r<=n;++r){//一个一个进行操作
        while((!sta.empty())&&a[sta.top()]<=a[r]) sta.pop();
        while((!stb.empty())&&b[stb.top()]<=b[r]) stb.pop();
        int ua=sta.empty()?1:sta.top()+1;
        int ub=stb.empty()?1:stb.top()+1;
        sta.push(r);stb.push(r);
        cover(1,1,n,ua,r,(Tag){a[r],0,0,0,0,0}),cover(1,1,n,ub,r,(Tag){0,b[r],0,0,0,0});
        cover(1,1,n,1,r,(Tag){0,0,0,0,0,1});//表示Ch给hsum的贡献为1
        for(auto [l,id]:Qu[r]) ans[id]=query(1,1,n,l,r);
    }
    for(int i=1;i<=Q;++i) cout<<ans[i]<<endl;
    return 0;
}