线段树

线段树是我的弱项
我们来看这一题：
要维护值得乘积
对 abc
如果a发生变化，那么我们要是知道b*c则只要加上a得增量就好了

基于着中国想法，我们使用了线段树。

我们一共开了7棵线段树！
先开三棵a,b,c
在我们的线段树所开的数组中记录的点seg[x]是，从点x到目前边界的极差
线段树维护这个极差的和
而这个边界我们在不断地向后推，从而极差发生变化，用线段树维护。

同时，在维护了a,b,c每一次推边界后，以当前边界为右端点的区间的极差和后。
我们可以利用刚开始的思想维护出ab,ac,bc,abc的值
满足结合律，我们当然可以利用线段树！

而，如何在将边界向后推的过程中，维护变化的极差呢？
这里就要用到单调栈了！
我们枚举到一个新的边界，然后利用两个单调栈，得到左边第一个大于值他的索引l1,
第一个值小于他的索l2
那么显然，l1之内的极差要产生增加，l1之内的极差要减小
当然要先减去之前的值了，这个在维护单调栈时也能实现。
具体见代码。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int unsigned int
typedef long long ll;
const int max_n = 1e5+100;
struct segment{
    unsigned int sum[max_n<<2][8];
    unsigned int add[max_n<<2][8];
    unsigned int ls(int x){return x<<1;}
    unsigned int rs(int x){return x<<1|1;}

    void f(int id,int l,int r,int val,int tar){
        sum[id][tar]+=val*(r-l+1);
        if (tar==1){
            sum[id][4]+=val*sum[id][2];
            sum[id][5]+=val*sum[id][3];
            sum[id][7]+=val*sum[id][6];
        }
        else if (tar==2){
            sum[id][4]+=val*sum[id][1];
            sum[id][6]+=val*sum[id][3];
            sum[id][7]+=val*sum[id][5];
        }
        else{
            sum[id][5]+=val*sum[id][1];
            sum[id][6]+=val*sum[id][2];
            sum[id][7]+=val*sum[id][4];
        }
        add[id][tar]+=val;
    }

    void push_up(int id){
        for (int i=1;i<=7;++i)sum[id][i]=sum[ls(id)][i]+sum[rs(id)][i];
    }
    void push_down(int id,int l,int r){
        int mid = (l+r)>>1;
        for (int tar=1;tar<=3;++tar){
            if (add[id][tar]!=0){
                f(ls(id),l,mid,add[id][tar],tar);
                f(rs(id),mid+1,r,add[id][tar],tar);
                add[id][tar]=0;
            }
        }
    }
    void update(int id,int l,int r,int lpos,int rpos,int val,int tar){
        if (l>=lpos&&r<=rpos){
            f(id,l,r,val,tar);
            return;
        }
        push_down(id,l,r);
        int mid = (l+r)>>1;
        if (mid>=lpos)update(ls(id),l,mid,lpos,rpos,val,tar);
        if (mid+1<=rpos)update(rs(id),mid+1,r,lpos,rpos,val,tar);
        push_up(id);
    }    
}seg;
int n;
int a[4][max_n];
vector<int> st1[4],st2[4];



signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    int ans=0;
    for (int j=1;j<=3;++j){
        for (int i=1;i<=n;++i){
            cin>>a[j][i];
        }
    }
    for (int i=1;i<=n;++i){
        for (int k=1;k<=3;++k){
            while (!st1[k].empty()&&a[k][st1[k].back()]<=a[k][i]){
                if (st1[k].size()==1)seg.update(1,1,n,1,st1[k].back(),-a[k][st1[k].back()],k);
                else seg.update(1,1,n,st1[k][st1[k].size()-2]+1,st1[k].back(),-a[k][st1[k].back()],k);
                st1[k].pop_back();
            }
            if (st1[k].empty())seg.update(1,1,n,1,i,a[k][i],k);
            else seg.update(1,1,n,st1[k].back()+1,i,a[k][i],k);
            st1[k].push_back(i);

            while (!st2[k].empty()&&a[k][st2[k].back()]>=a[k][i]){
                if (st2[k].size()==1)seg.update(1,1,n,1,st2[k].back(),a[k][st2[k].back()],k);
                else seg.update(1,1,n,st2[k][st2[k].size()-2]+1,st2[k].back(),a[k][st2[k].back()],k);
                st2[k].pop_back();
            }
            if (st2[k].empty())seg.update(1,1,n,1,i,-a[k][i],k);
            else seg.update(1,1,n,st2[k].back()+1,i,-a[k][i],k);
            st2[k].push_back(i);

        }
        ans+=seg.sum[1][7];
    }cout<<ans<<endl;
}