势能线段树、李超线段树专题（补

下面是OI Wiki对吉司机线段树（势能线段树的一种）和李超线段树的详解：
吉司机线段树
李超线段树

在信息学中，势能被用于计算某一个过程，或者某一类过程时间复杂度的总和。

我们知道，线段树能够通过打标记实现区间修改的条件有两个：
1.能够快速处理标记对区间询问结果的影响
2.能够快速实现标记的合并
但有的区间修改不满足上面两个条件（如区间开方，区间取模等）
但某些修改存在一些奇妙的性质，使得序列每个元素被修改的次数有一个上限
可以在线段树每个节点上记录一个值，表示对应区间内是否每个元素都达到修改次数上限
区间修改时暴力递归到叶子节点，如果途中遇到一个节点，这个节点的对应区间内每个元素都达到修改次数上限则在这个节点 return 掉
引用：https://blog.csdn.net/Daniel__d/article/details/105104831

A 智乃的直线

代码链接：

B 弩蚊怒夏

代码链接：

C 势能线段树模板题二

带修改的区间开方

我们发现对于一个序列，如果开方的前后，最大值的变化量等于最小值的变化量，那么其实这就是一个区间减的操作（因为显然这个变化量是有单调性的），因此我们只需要维护区间最大值和区间最大值即可，然后暴力修改，遇到满足条件的就区间减，然后直接return

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48707568

int n,m;
ll a[N];
struct node{
    int l,r;
    ll lazy;
    ll sum,maxx,minn;
}tree[N<<2];

void pushup(int u){
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
    tree[u].maxx=max(tree[u<<1].maxx,tree[u<<1|1].maxx);
    tree[u].minn=min(tree[u<<1].minn,tree[u<<1|1].minn);
}

void addlazy(int u,ll v){
    tree[u].lazy+=v;
    tree[u].sum+=v*(tree[u].r-tree[u].l+1);
    tree[u].maxx+=v;
    tree[u].minn+=v;
}  

void pushdown(int u){
    if(tree[u].lazy){
        addlazy(u<<1,tree[u].lazy);
        addlazy(u<<1|1,tree[u].lazy);
        tree[u].lazy=0;
    }
}

void build(int u,int l,int r){
    tree[u].l=l,tree[u].r=r;
    tree[u].minn=INF;tree[u].maxx=-INF;
    if(l==r){
        tree[u].sum=tree[u].maxx=tree[u].minn=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r){
        ll fx=tree[u].maxx-(ll)sqrt(tree[u].maxx);
        ll fy=tree[u].minn-(ll)sqrt(tree[u].minn);
        if(fx==fy) return addlazy(u,-fx);
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify(u<<1,l,r);
    else if(l>mid) modify(u<<1|1,l,r);
    else modify(u<<1,l,r),modify(u<<1|1,l,r);
    pushup(u);
}

ll query(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].sum;
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else return query(u<<1,l,r)+query(u<<1|1,l,r);
}

void add(int u,int l,int r,ll v){
    if(l<=tree[u].l&&tree[u].r<=r){
        addlazy(u,v);
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) add(u<<1,l,r,v);
    else if(l>mid) add(u<<1|1,l,r,v);
    else add(u<<1,l,r,v),add(u<<1|1,l,r,v);
    pushup(u);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            modify(1,l,r);
        }
        else if(op==2){
            int l,r;ll v;cin>>l>>r>>v;
            add(1,l,r,v);
        }
        else{
            int l,r;cin>>l>>r;
            cout<<query(1,l,r)<<"\n";
        }
    }
}

D 势能线段树模板题一

区间开方
我们可以发现对 1 或 0 的开方，对他的值是不会改变的
所以当遇到 1 或 0 可以提前return掉
即题目中的定义区间最大值max为势能，势能初始值为区间最大值，定义0势能点为max=1

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48704791

int n,m;
ll a[N];
struct node{
    int l,r;
    ll sum,maxx;
}tree[N<<2];

void pushup(int u){
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
    tree[u].maxx=max(tree[u<<1].maxx,tree[u<<1|1].maxx);
}

void build(int u,int l,int r){
    tree[u].l=l,tree[u].r=r;
    if(l==r){
        tree[u].sum=tree[u].maxx=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r){
    if(tree[u].maxx<=1) return;
    if(tree[u].l==tree[u].r){
        tree[u].sum=tree[u].maxx=sqrt(tree[u].maxx);
        return;
    }
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify(u<<1,l,r);
    else if(l>mid) modify(u<<1|1,l,r);
    else modify(u<<1,l,r),modify(u<<1|1,l,r);
    pushup(u);
}

ll query(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].sum;
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else return query(u<<1,l,r)+query(u<<1|1,l,r);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1) modify(1,l,r);
        else cout<<query(1,l,r)<<"\n";
    }
}

E [HEOI2013]SEGMENT

代码链接：