用j2ee作的网站,建设部网站投诉核查,荥阳网络推广公司,服务好 售后好的网站建设【题目描述】
给定一个长度为n的非负整数序列#xff0c;接下来有m次操作#xff0c;操作共有3种#xff1a;一是修改序列中某个元素的大小#xff0c;二是求某个区间的所有元素的和#xff0c;三是询问某个区间的最大值。整数序列下标从1开始。n10^5, m10^5。
…【题目描述】
给定一个长度为n的非负整数序列接下来有m次操作操作共有3种一是修改序列中某个元素的大小二是求某个区间的所有元素的和三是询问某个区间的最大值。整数序列下标从1开始。n10^5, m10^5。
【输入描述】
第一行2个整数n和m, 分别 表示整数序列的元素个数和操作次数
接下来一行就是这n个非负整数, 每个整数都不超过10^8
接下来m行每行都有三个整数k, a, b;
如果k是0的话就表示把原序列中的第a个位置上的数改为b,b也是不超过10^8的非负整数。
如果k是1的话就表示询问区间[a, b]的最大值 如果k是2的话就表示询问区间[a, b]的元素和。
【输出描述】
对于每个k为1或2的询问输出相对应的结果每个输出结果占一行。
【输入样例】
10 4
5 2 3 4 7 9 5 8 6 2
0 5 9
1 2 5
0 8 6
2 7 10【输出样例】
9
19#includebits/stdc.h
#define ll long long
using namespace std;
const int N 100010;
struct node {int l, r, mx;ll s;
};
node xdt[4*N];
int n, m, p, l, r, x, y, a[N];
void build(int k, int l, int r) {xdt[k].l l; xdt[k].r r;if (lr) {xdt[k].s a[l];xdt[k].mx a[l];return;}int mid (xdt[k].l xdt[k].r) / 2;build(k*2, l, mid);build(k*21, mid1, r);xdt[k].s xdt[k*2].s xdt[k*21].s;xdt[k].mx max(xdt[k*2].mx, xdt[k*21].mx);
}
void change(int k, int x, int y) {if (xdt[k].l x xdt[k].r x) {xdt[k].s y;xdt[k].mx y;return; }int mid (xdt[k].l xdt[k].r) / 2;if (x mid) change(k*2, x, y);else change(k*21, x, y);xdt[k].s xdt[k*2].s xdt[k*21].s;xdt[k].mx max(xdt[k*2].mx, xdt[k*21].mx);
}
long long find_s(int k, int l, int r) {if (xdt[k].l l xdt[k].r r) {return xdt[k].s;}int mid (xdt[k].l xdt[k].r) / 2;if (l mid) return find_s(k*21, l, r);if (r mid) return find_s(k*2, l, r);return find_s(k*2, l, mid) find_s(k*21, mid1, r);
}
int find_mx(int k, int l, int r) {if (xdt[k].l l xdt[k].r r) {return xdt[k].mx;}int mid (xdt[k].l xdt[k].r) / 2;if (l mid) return find_mx(k*21, l, r);if (r mid) return find_mx(k*2, l, r);return max(find_mx(k*2, l, mid), find_mx(k*21, mid1, r));
}
int main() {scanf(%d%d, n, m);for (int i1; in; i) scanf(%d, a[i]);build(1, 1, n);for (int i1; im; i) {scanf(%d, p);if (p0) {scanf(%d%d, x, y);change(1, x, y);} if (p1) {scanf(%d%d, l, r);printf(%d\n, find_mx(1, l, r));}if (p2) {scanf(%d%d, l, r);printf(%lld\n, find_s(1, l, r));}}return 0;
}
