北京师范大学第十七届程序设计竞赛决赛-重现赛 G

            因为本题只存在单点查询,所以我们考虑每次不更新到叶子节点,而是直接更新到当前区间,如果同一区间存在多次更新,我们每次只需要保留最优情况，每次查询,我们途中一定会经过这些区间,向上回溯的时候取最小值即可.
            线段树维护两个值,一个是区间[l,r]上,L的值,另一个是这个区间的差值(可以想象成一个等差数列或者线段).
            不是很懂的可以了解一下扫描线的思想，同样也是不更新到叶子节点si

Ac_Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#define fir first
#define sec second
using namespace std;

const int maxn = 1e5+7;
const int INF = 1e9+7;

int n,m;
int a[maxn];
int d[maxn<<2],f[maxn<<2];

void build(int l,int r,int num) {
    d[num] = 0;
    f[num] = INF;
    if(l==r) {
        f[num] = a[l];
        d[num] = 0;
        return ;
    }
    int mid = (l+r) >>1;
    build(l,mid,num<<1);
    build(mid+1,r,num<<1|1);
    return ;
}

void modify(int l,int r,int num,int le,int ri,int x,int y) {
    if(le<=l && r<=ri) {
        if(f[num] <=  (l-le) * y+x && (r-le) * y+x >= f[num] + (r-l) * d[num]) return ;
        if(f[num] >= (l-le) * y+x && ((r-le) * y+x <= f[num] + (r-l) * d[num])) {
            f[num] = (l-le) *y +x;
            d[num] = y;
            return ;
        }
    }
    int mid = (l+r) >>1;
    if(le<=mid) modify(l,mid,num<<1,le,ri,x,y);
    if(mid< ri) modify(mid+1,r,num<<1|1,le,ri,x,y);
}

int quriy(int l,int r,int num,int pos) {
    if(l==r) return f[num];
    int mid = (l+r) >>1;
    if(pos <= mid) return min(f[num] + (pos-l)*d[num] ,quriy(l,mid,num<<1,pos));
    else return min(f[num] + (pos -l) * d[num],quriy(mid+1,r,num<<1|1,pos));
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    while(m--) {
        int op,l,r,x,y;
        scanf("%d",&op);
        if(op == 1) {
            scanf("%d%d%d%d",&l,&r,&x,&y);
            modify(1,n,1,l,r,x,y);
        }
        else {
            scanf("%d",&x);
            printf("%d\n",quriy(1,n,1,x));
        }
    }
    return 0;
}