题解：P11790 [JOI 2017 Final] 焚风现象 / Foehn Phenomena

wala5456 · 2025-10-28 23:20:34 · 题解

线段树板子题

我们先算出一开始没有变化前地点 N 的温度，然后我们发现每个变化区间中相邻两个值的差值是不变的，因为都增加或减少了。假设区间是 l~r，我们只需要看 l 与 l-1 和 r 与 r+1 差值的变化就行了，相当于区间修改，单点查询。如果线段树有不会的可以看板子题P3372 【模板】线段树 1

AC代码

#include <bits/stdc++.h>
using namespace std;
long long n,q,s,t,a[200005],zans = 0;
struct node{
    long long l,r,j;
}tree[800005];
void build(long long l,long long r,long long id){
    tree[id].l = l;
    tree[id].r = r;
    if(l == r)return;
    long long mid = (l+r)/2;
    build(l,mid,id*2);
    build(mid+1,r,id*2+1);
}
void add(long long l,long long r,long long p,long long id){
    if(tree[id].l >= l && tree[id].r <= r){
        tree[id].j += p;
        return;
    }
    if(tree[id].l == tree[id].r) return;
    if(l > tree[id].r || r < tree[id].l) return;
    if(l <= tree[2*id].r)   add(l,r,p,2*id);
    if(r >= tree[2*id+1].l)   add(l,r,p,2*id+1);
}
long long se(long long x,long long id,long long ans){
    ans += tree[id].j;
    if(tree[id].l == tree[id].r && tree[id].l == x){
        return ans+a[x];
    }
    if(tree[id].l == tree[id].r) return 0;
    if(tree[2*id].l <= x && tree[2*id].r >= x) return se(x,2*id,ans);
    if(tree[2*id+1].l <= x && tree[2*id+1].r >= x) return se(x,2*id+1,ans);
}
int main(){
    cin >> n >> q >> s >> t;
    s = -s;
    for(long long i = 0;i <= n;i++) cin >> a[i];
    for(long long i = 1;i <= n;i++){
        if(a[i] >= a[i-1]) zans += (a[i]-a[i-1])*s;
        else zans += (a[i-1]-a[i])*t;
    }
    build(0,n,1);
    while(q--){
        long long l,r,p;
        cin >> l >>r >> p; 
        long long nl = se(l,1,0);
        long long nr = se(r,1,0);
        long long wl = se(l-1,1,0);
        long long wr = se(r+1,1,0);
        add(l,r,p,1);
        long long xl = se(l,1,0);
        long long xr = se(r,1,0);
        long long anss = 0;
        if(p > 0){
            if(l > 0){
                if(nl < wl && xl >= wl){
                    anss -= (wl-nl)*t;
                    anss += (xl-wl)*s; 
                }
                else if(nl < wl && xl < wl){
                    anss -= (xl-nl)*t;
                }
                else{
                    anss += (xl-nl)*s;
                }
            }
            if(r < n){
                if(nr < wr && xr >= wr){
                    anss -= (wr-nr)*s;
                    anss += (xr-wr)*t; 
                }
                else if(nr < wr && xr < wr){
                    anss -= (xr-nr)*s;
                }
                else{
                    anss += (xr-nr)*t;
                }
            }
        }
        if(p < 0){
            if(l > 0){
                if(nl > wl && xl <= wl){
                    anss -= (nl-wl)*s;
                    anss += (wl-xl)*t; 
                }
                else if(nl > wl && xl > wl){
                    anss -= (nl-xl)*s;
                }
                else{
                    anss += (nl-xl)*t;
                }
            }
            if(r < n){
                if(nr > wr && xr <= wr){
                    anss -= (nr-wr)*t;
                    anss += (wr-xr)*s; 
                }
                else if(nr > wr && xr > wr){
                    anss -= (nr-xr)*t;
                }
                else{
                    anss += (nr-xr)*s;
                }
            }
        }//分支结构有点乱，看懂大概就行了
        zans += anss;
        cout << zans << endl;
    }
}