题解：P12263 『STA - R9』回听

· · 题解

题目传送门

前言

本人在比赛时没有想到这题要用线段树，连暴力都没打，就宣告退出了 （主要是比较懒），现在细细想来，才发现我有多愚蠢。

本题涉及知识

线段树模板，没什么多说的，不懂的点这里。

思路分析

如果已经明白的大佬，可以自行跳过。

看了题目后，发现 b_i 随着 i 的增，始终单调不降，所以我们只需要知道 b_i 的最小值 \min 是多少即可解决问题。

要让 x 的位置的值尽可能小，我们就要用两个线段树分别维护 a_x 和 a_x-x+1，于是就有了下面的代码。

线段树做法，时间复杂度 O(q \times \log n)。

注意：本题要开 long long。

代码部分（内含注释）

蒟蒻马蜂丑陋，大佬勿喷。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//以下的 p<<1 是 p*2 ，表示左孩子； p<<1|1 是 p*2+1 ，表示右孩子； 
const int N=5e5+5;//题目给的空间
int n,q,a[N];
struct node{
    int l,r,lazy,minn; 
}tree1[4*N],tree2[4*N];//正常开*4的空间~ 
void pushdown1(int p){//处理 tree1 
    if(tree1[p].lazy==0) return ;
    tree1[p<<1].lazy+=tree1[p].lazy;
    tree1[p<<1|1].lazy+=tree1[p].lazy;
    tree1[p<<1].minn+=tree1[p].lazy;
    tree1[p<<1|1].minn+=tree1[p].lazy;
    tree1[p].lazy=0;
} 
void pushdown2(int p){//处理 tree2
    if(tree2[p].lazy==0) return ;
    tree2[p<<1].lazy+=tree2[p].lazy;
    tree2[p<<1|1].lazy+=tree2[p].lazy;
    tree2[p<<1].minn+=tree2[p].lazy;
    tree2[p<<1|1].minn+=tree2[p].lazy;
    tree2[p].lazy=0;
} 
void build1(int p,int l,int r){//处理 tree1 
    tree1[p]={l,r,0,a[l]};//初始化
    if(l==r) return ;
    int mid=l+r>>1;
    //二分建树 
    build1(p<<1,l,mid);build1(p<<1|1,mid+1,r);
    tree1[p].minn=min(tree1[p<<1].minn,tree1[p<<1|1].minn);//更新 p 节点的信息 minn 
} 
void build2(int p,int l,int r){//处理 tree2
    tree2[p]={l,r,0,a[l]-l+1};//初始化 
    if(l==r) return ; 
    int mid=l+r>>1;
    //二分建树
    build2(p<<1,l,mid);build2(p<<1|1,mid+1,r);
    tree2[p].minn=min(tree2[p<<1].minn,tree2[p<<1|1].minn);//更新 p 节点的信息 minn 
} 
void update1(int p,int x,int y,int k){//处理 tree1 
    int l=tree1[p].l;
    int r=tree1[p].r;
    if(x<=l&&r<=y){
        tree1[p].lazy+=k;
        tree1[p].minn+=k;
        return ;
    }pushdown1(p);//处理懒标记 
    int mid=l+r>>1;
    if(x<=mid) update1(p<<1,x,y,k);
    if(y>mid) update1(p<<1|1,x,y,k);
    tree1[p].minn=min(tree1[p<<1].minn,tree1[p<<1|1].minn);//更新 p 节点的信息 minn 
}
void update2(int p,int x,int y,int k){//处理 tree2 
    int l=tree2[p].l;
    int r=tree2[p].r;
    if(x<=l&&r<=y){
        tree2[p].lazy+=k;
        tree2[p].minn+=k;
        return ;
    }pushdown2(p);//处理懒标记 
    int mid=l+r>>1;
    if(x<=mid) update2(p<<1,x,y,k);
    if(y>mid) update2(p<<1|1,x,y,k);
    tree2[p].minn=min(tree2[p<<1].minn,tree2[p<<1|1].minn);//更新 p 节点的信息 minn 
}
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    //经典建树函数
    build1(1,1,n);build2(1,1,n);
    while(q--){
        int l,r,v;
        scanf("%lld%lld%lld",&l,&r,&v);
        //经典更新函数 
        update1(1,l,r,v);update2(1,l,r,v);
        printf("%lld\n",tree1[1].minn-max(tree2[1].minn,0ll)+1);
    }
    return 0;
}

后附

不要抄袭代码！！不要直接复制！！

先清晰思路，再进行借鉴！！

若有笔误，请指出，感谢。