使用实现区间查询最小值，和的线段树

解题思路:看注释

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000010

#define INF 1000010

typedef long long ll;

int a[maxn];

ll ans;

struct node{

    ll l,r;

    ll minval,minpla;

    ll sum;

    ll lazy;//懒标记,表示tree[i]的所有子树都要修改（tree[i]不用修改）

}tree[maxn<<2];

void push_up(int i){

    if(tree[i<<1].minval<=tree[i<<1|1].minval){

        tree[i].minval=tree[i<<1].minval;

        tree[i].minpla=tree[i<<1].minpla;

    }

    else{

        tree[i].minval=tree[i<<1|1].minval;

        tree[i].minpla=tree[i<<1|1].minpla;

    }

    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;

}

void build(int i,int l,int r){

    tree[i].l=l;tree[i].r=r;tree[i].lazy=0;

    if(l==r){

        tree[i].minval=a[l];

        tree[i].minpla=l;

        tree[i].sum=a[l];

        return;

    }

    int mid=(l+r)>>1;

    build(i<<1,l,mid);

    build(i<<1|1,mid+1,r);

    push_up(i);

}

void push_down(int i){//这个区间应该每个数减k

    if(!tree[i].lazy)return;

    tree[i<<1].sum-=tree[i].lazy*(tree[i<<1].r+1-tree[i<<1].l);

    tree[i<<1].minval-=tree[i].lazy;

    tree[i<<1|1].sum-=tree[i].lazy*(tree[i<<1|1].r+1-tree[i<<1|1].l);

    tree[i<<1|1].minval-=tree[i].lazy;

    tree[i<<1].lazy+=tree[i].lazy;

    tree[i<<1|1].lazy+=tree[i].lazy;

    tree[i].lazy=0;

}

void modify(int i,int l,int r,int k){//让区间l,r的每一个数都减去k，并更新线段树

    //if(tree[i].l>r||tree[i].r<l)return;//实际上永远不会到这种情形

    if(tree[i].l>=l&&tree[i].r<=r){

        tree[i].lazy+=k;

        tree[i].sum-=(tree[i].r-tree[i].l+1)*k;//就是这个地方，可能会超过int类型，所以我索性把结构体里所有变量定义为了long long

        tree[i].minval-=k;

        return;

    }

    push_down(i);

    if(tree[i<<1].r>=l){

        modify(i<<1,l,r,k);

    }

    if(tree[i<<1|1].l<=r){

        modify(i<<1|1,l,r,k);

    }

    push_up(i);

}

pair<int,int> querymin(int i,int l,int r){//应该能同时返回minval和minpla

    //if(tree[i].l>r||tree[i].r<l)return;//实际上永远不会到这种情形

    pair<int,int> ret,tmp;

    if(tree[i].l>=l&&tree[i].r<=r){

        ret.first=tree[i].minval;

        ret.second=tree[i].minpla;

        return ret;

    }

    push_down(i);

    ret.first=INF;tmp.first=INF;

    if(tree[i<<1].r>=l){

        ret=querymin(i<<1,l,r);

    }

    if(tree[i<<1|1].l<=r){

        tmp=querymin(i<<1|1,l,r);

    }

    if(ret.first<=tmp.first)return ret;

    else return tmp;

}

ll querysum(int i,int l,int r){

    if(tree[i].l>=l&&tree[i].r<=r){

        return tree[i].sum;

    }

    push_down(i);

    ll sum=0;

    if(tree[i<<1].r>=l){

        sum+=querysum(i<<1,l,r);

    }

    if(tree[i<<1|1].l<=r){

        sum+=querysum(i<<1|1,l,r);

    }

    return sum;

}

int main(){

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

    }

    build(1,1,n);

    int l=1,r=min(n,k);

    pair<int,int> x;

    int minpla,minval;

    while(l<=n){

        if(querysum(1,l,l)==0){

            l++;

            r=min(n,l+k-1);

            continue;

        }

        if(r==l+k-1){

            x=querymin(1,l,r);

            minval=x.first;minpla=x.second;

            ans+=minval;

            modify(1,l,r,minval);//[l,r]整体减minval

            if(l<minpla)ans+=querysum(1,l,minpla-1);

            l=minpla+1;

            r=min(n,l+k-1);

        }

        else{

            ans+=querysum(1,l,r);

            break;

        }

    }

    printf("%lld",ans);

    system("pause");

    return 0;

}