一道非常直白的線段樹(shù)題目，甚至不需要慵懶操作233涡驮，如果你不知道什么是線段樹(shù)欧瘪，可以去看我的這篇文章：線段樹(shù)入門(mén)

問(wèn)題描述

給定一個(gè)n個(gè)頂點(diǎn)题篷，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒(méi)有負(fù)環(huán)）屡穗。請(qǐng)你計(jì)算從1號(hào)點(diǎn)到其他點(diǎn)的最短路（頂點(diǎn)從1到n編號(hào)）贴捡。

輸入格式

第一行兩個(gè)整數(shù)n, m。

接下來(lái)的m行鸡捐，每行有三個(gè)整數(shù)u, v, l栈暇，表示u到v有一條長(zhǎng)度為l的邊。

輸出格式

共n-1行箍镜，第i行表示1號(hào)點(diǎn)到i+1號(hào)點(diǎn)的最短路源祈。

樣例輸入

3 3
1 2 -1
2 3 -1
3 1 2

樣例輸出

-1
-2

數(shù)據(jù)規(guī)模與約定

對(duì)于10%的數(shù)據(jù)，n = 2色迂，m = 2香缺。

對(duì)于30%的數(shù)據(jù)，n <= 5歇僧，m <= 10图张。

對(duì)于100%的數(shù)據(jù)，1 <= n <= 20000诈悍，1 <= m <= 200000祸轮，-10000 <= l <= 10000，保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)侥钳。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 100005
int arr[MAXN];
struct tr{
    int l, r, mx, sum;
}Tr[MAXN << 2];
void push(int d){
    Tr[d].mx = max(Tr[d << 1].mx, Tr[d << 1 | 1].mx);
    Tr[d].sum = Tr[d << 1].sum + Tr[d << 1 | 1].sum;
}
void build(int l, int r, int d){
    Tr[d].l = l, Tr[d].r = r;
    if(l == r){
        Tr[d].mx = arr[l], Tr[d].sum = arr[l];
        return;
    }
    int mid = (l + r) >> 1, lc = d << 1, rc = d << 1 | 1;
    build(l, mid, lc);
    build(mid + 1, r, rc);
    push(d);
}
void modify(int d, int pos, int v){
    if(Tr[d].l == Tr[d].r && Tr[d].l == pos){
        Tr[d].mx = v, Tr[d].sum = v;
        return;
    }
    int mid = (Tr[d].l + Tr[d].r) >> 1, lc = d << 1, rc = d << 1 | 1;
    if(pos <= mid)modify(lc, pos, v);
    else modify(rc, pos, v);
    push(d);
}
int querymx(int l, int r, int d){
    if(Tr[d].l == l && Tr[d].r == r)return Tr[d].mx;
    int mid = (Tr[d].l + Tr[d].r) >> 1, lc = d << 1, rc = d << 1 | 1;
    if(r <= mid)return querymx(l, r, lc);  // [L, [l, r], mid, R]
    else if( l > mid )return querymx(l, r, rc);  // [L, mid, [l, r], R]
    else return max(querymx(l, mid, lc), querymx(mid + 1, r, rc));  //[L, [l, mid, r], R]
}
int querysum(int l, int r, int d){
    if(Tr[d].l == l && Tr[d].r == r)return Tr[d].sum;
    int mid = (Tr[d].l + Tr[d].r) >> 1, lc = d << 1, rc = d << 1 | 1;
    if(r <= mid)return querysum(l, r, lc);
    else if( l > mid )return querysum(l, r, rc);
    else return querysum(l, mid, lc)+ querysum(mid + 1, r, rc);
}
int main(){
    int n, m, type, p1, p2;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)scanf("%d", &arr[i]);
    build(1, n, 1);
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &type, &p1, &p2);
        if(type == 1)modify(1, p1, p2);
        else if(type == 2)printf("%d\n", querysum(p1, p2, 1));
        else printf("%d\n", querymx(p1, p2, 1));
    }
    return 0;
}