Acwing 245.你能回答这些问题吗

标签：oid   query   接下来   限制   def   main   The   时空   大连   

题目描述

给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤y{∑ri=lA[i]}。

2、“2 x y”，把 A[x] 改成 y。

对于每个查询指令，输出一个整数表示答案。

输入格式

第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

N≤500000,M≤100000

输入样例：

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

输出样例：

2
-1

时/空限制：

1s / 64MB

rt。

一道挺难的线段树题。

#include
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
struct seg{
    int ans, sum, l, r, L, R;
    #define ans(p) t[p].ans
    #define sum(p) t[p].sum
    #define l(p) t[p].l
    #define r(p) t[p].r
    #define L(p) t[p].L
    #define R(p) t[p].R
}t[maxn > 1;
    build(p  r(p))
        return ;
    if(l(p) == r(p)){
        sum(p) = ans(p) = L(p) = R(p) = k;
        return ;
    }
    change(p > 1, val = -1e9;
    lson = (seg){val, val, 0, 0, val, val};
    rson = lson;
    res.sum = 0;
    if(l  mid)
        res.L = max(res.L, rson.L);
    if(r  z)
                swap(y, z);
            printf("%lld\n", query(1, y, z).ans);
        } else {
            change(1, y, z);
        }
    }
    return 0;
}

Acwing 245.你能回答这些问题吗

标签：oid   query   接下来   限制   def   main   The   时空   大连   

原文地址：https://www.cnblogs.com/yangxuejian/p/11565453.html