tagged-zkw.
稍后做一个教程。

namespace DEL
{
    const int INF = 1e9, maxn = 1 << 25;
    struct info
    {
        int Max;
        info(int x = -INF) : Max(x){}
    } A[maxn];
}
#include <cstdio>
#include <algorithm>
using namespace std;
using namespace DEL;
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        int t;
        for(t = 1; t <= n + 3; t <<= 1);
        for(int i = t + 1; i < t + 1 + n; i++)
        {
            int a;
            scanf("%d", &a);
            A[i] = info(a);
        }
        for(int i = t - 1; i > 0; i--)
            A[i].Max = max(A[i * 2].Max, A[i * 2 + 1].Max);
        while(m--)
        {
            static char c[maxn];int x, y;
            scanf("%s%d%d", &c, &x, &y);
            if(c[0] == 'Q')
            {
                int ans = 0;
                for(x += t - 1, y += t + 1; x ^ y ^ 1; x >>= 1, y >>= 1)
                {
                    if(~x & 1)
                        ans = max(ans, A[x ^ 1].Max);
                    if(y & 1)
                        ans = max(ans, A[y ^ 1].Max);
                }
                printf("%d\n", ans);
            }
            else
            {
                for(A[x += t] = info(y), x >>= 1; x > 0; x >>= 1)
                    A[x].Max = max(A[x * 2].Max, A[x * 2 + 1].Max);
            }
        }
    }
    return 0;
}

Segment tree.
祝卡cin/cout的出题者全·家·爆·炸！

#include <cstdio>
#include <cstring>
#include <limits> 
#include <algorithm>
using namespace std;
namespace DEL
{
    int n;
    template<int maxn, class T>
    class SegmentTree
    {
    private:
        T maxv[maxn*3], minv[maxn*3];
        T left, right, v;
        T _max, _min;
    public:
        void init()
        {
            memset(maxv, 0, sizeof maxv);
            memset(minv, 0, sizeof minv);
            _max = 0;
            _min = numeric_limits<T>::max(); 
        }
        void set(int l, int r, int _v)
        {
            left = l, right = r, v = _v;
        }
        void update(T o = 1, T L = 1, T R = n)
        {
            if(L == R)
            {
                maxv[o] += v;
                minv[o] += v;
            }
            else
            {
                T lc = o << 1, rc = lc + 1, M = (L + R) / 2;
                if(left <= M)
                    update(lc, L, M);
                else
                    update(rc, M + 1, R);
                maxv[o] = max(maxv[lc], maxv[rc]);
                minv[o] = min(minv[lc], minv[rc]);
            }
        }
        void query(T o = 1, T L = 1, T R = n)
        {
            if(left <= L && R <= right)
            {
                _max = max(_max, maxv[o]);
                _min = min(_min, minv[o]);
            }
            else
            {
                T lc = o << 1, rc = lc + 1, M = (L + R) / 2;
                if(left <= M)
                    query(lc, L, M);
                if(M < right)
                    query(rc, M + 1, R);
            }
        }
        T get()
        {
            int ans = _max - _min;
            _max = 0;
            _min = numeric_limits<T>::max(); 
            return ans;
        }
    };
}
using namespace DEL;
SegmentTree<(int)5e4 + 10, int> st;
int q;
int main()
{
    st.init();
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        st.set(i, 0, tmp);
        st.update();
    }
    while(q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        st.set(a, b, 0);
        st.query();
        printf("%d\n", st.get());
    }
    return 0;
}

Segment Tree.
但是区间修改前缀和的话不一定需要线段树吧……有时间再想想……

#include <cstdio>
#include <cstring>
using namespace std;
namespace DEL
{
    int n;
    template<int maxn, class T>
    class SegmentTree
    {
    private:
        T setv[maxn*3], sumv[maxn*3];
        T left, right, v;
        void maintain(T o, T L, T R)
        {
            int M = (L + R) >> 1, lc = o << 1, rc = lc + 1;
            sumv[o] = 0;
            if(L < R)
                sumv[o] = sumv[lc] + sumv[rc];
            if(setv[o] != 0)
                sumv[o] = setv[o] * (R - L + 1);
        }
        void pushdown(int o)
        {
            T lc = o << 1, rc = lc + 1;
            if(setv[o] != 0)
            {    
                setv[lc] = setv[rc] = setv[o];
                setv[o] = 0;
            }
        }

    public:
        void init()
        {
            memset(setv, 0, sizeof setv);
            memset(sumv, 0, sizeof sumv);
        }

        void set(T _left, T _right, T _v)
        {
            left = _left, right = _right, v = _v;
        }

        void update(T o = 1, T L = 1, T R = n)
        {
            if(left <= L && R <= right)
                setv[o] = v;
            else
            {
                pushdown(o);
                int M = (L + R) >> 1, lc = o << 1, rc = lc + 1;
                if(left <= M)
                    update(lc, L, M);
                else
                    maintain(lc, L, M);
                if(M < right)
                    update(rc, M + 1, R);
                else
                    maintain(rc, M + 1, R);
            }
            maintain(o, L, R);
        }

        T getans()
        {
            return sumv[1];
        }
    };
}
using namespace DEL;
SegmentTree<int(1e5), int> st;
int q;
int main()
{
    int t;
    scanf("%d", &t);
    for(int i = 1; i <= t; i++)
    {
        st.init();
        scanf("%d%d", &n, &q);
        for(int j = 1; j <= n; j++)
        {
            st.set(j, j, 1);
            st.update();
        }
        while(q--)
        {
            int l, r, v;
            scanf("%d%d%d", &l, &r, &v);
            st.set(l, r, v);
            st.update();
        }
        printf("Case %d: The total value of the hook is %d.\n", i, st.getans());
    }
    return 0;
}

Segment Tree

#include <cstdio>
#include <cstring>
using namespace std;
namespace DEL
{
    int n, q;
    template<int maxn, class T>
    class SegmentTree
    {
    private:
        T sumv[maxn*3], addv[maxn*3];
        
        inline void maintain(T o, T L, T R)
        {
            T lc = o << 1, rc = lc + 1, M = (L + R) / 2;
            sumv[o] = 0;
            if(L < R)
                sumv[o] = sumv[lc] + sumv[rc];
            sumv[o] += addv[o] * (R - L + 1);
        }
    public:
        void init()
        {
            memset(addv, 0, sizeof addv);
            memset(sumv, 0, sizeof sumv);
        }
        
        T yl, yr, v, ans;
        void update(T o = 1, T L = 1, T R = n)
        {
            if(yl <= L && R <= yr)
                addv[o] += v;
            else
            {
                T lc = o << 1, rc = lc + 1, M = (L + R) >> 1;
                if(yl <= M)
                    update(lc, L, M);
                if(M < yr)
                    update(rc, M + 1, R);
            }
            maintain(o, L, R);
        }
        
        void query(T o = 1, T L = 1, T R = n, T add = 0)
        {
            if(yl <= L && R <= yr)
                ans += sumv[o] + add * (R - L + 1);
            else
            {
                T lc = o << 1, rc = lc + 1, M = (L + R) / 2;
                if(yl <= M)
                    query(lc, L, M, add + addv[o]);
                if(M < yr)
                    query(rc, M + 1, R, add + addv[o]);
            }
        }
    };
}
using namespace DEL;
SegmentTree<int(1e5), long long> t;
int main()
{
    scanf("%d%d", &n, &q);
    t.init();
    for(int i = 1; i <= n; i++)
    {
        t.yl = t.yr = i;
        scanf("%I64d", &t.v);
        t.update();
    }
    char c[2];
    while(q--)
    {
        scanf("%s", &c);
        if(c[0] == 'Q')
        {
            scanf("%I64d%I64d%I64d", &t.yl, &t.yr, &t.v);
            t.ans = 0;
            t.query();
            printf("%I64d\n", t.ans);
        }
        else if(c[0] == 'C')
        {
            scanf("%I64d%I64d%I64d", &t.yl, &t.yr, &t.v);
            t.update();
        }
    }
    return 0;
}

Segment Tree.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;

template<int maxn>
class SegmentTree
{
private:
    int maxv[maxn];
public:
    void clear()
    {
        memset(maxv, 0, sizeof maxv);
    }
    
    int yl, v;
    void update(int o = 1, int L = 1, int R = n)
    {
        if(L == R)
            maxv[o] = v;
        else
        {
            int M = (L + R) / 2, lc = o << 1, rc = lc + 1;
            if(yl <= M)
                update(lc, L, M);
            else
                update(rc, M + 1, R);
            maxv[o] = max(maxv[lc], maxv[rc]);
        }
    }

    int yr, ans;
    void query(int o = 1, int L = 1, int R = n, int add = 0)
    {
        if(yl <= L && R <= yr)
            ans = max(ans, maxv[o]);
        else
        {
            int M = (L + R) / 2, lc = o << 1, rc = lc + 1;
            if(yl <= M)
                query(lc, L, M);
            if(M < yr)
                query(rc, M + 1, R);
        }
    }
};

SegmentTree<int(2e6+10)> s;

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        s.clear();
        for(int i = 1; i <= n; i++)
        {
            s.yl = i;
            scanf("%d", &s.v);
            s.update();
        }
        char type[100];
        while(m--)        
        {
            scanf("%s", type);
            if(type[0] == 'Q')
            {
                scanf("%d%d", &s.yl, &s.yr);
                s.ans = 0;
                s.query();
                printf("%d\n", s.ans);
            }
            else if(type[0] == 'U')
            {
                scanf("%d%d", &s.yl, &s.v);
                s.update();
            }
        }
    }
    return 0;
}