SPOJ1716 GSS3(线段树)

 2023-09-11 阅读 19 评论 0

摘要:题意 Sol 会了GSS1,GSS3就比较无脑了 直接加个单点修改即可,然后update一下 /**/ #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<set> #include<queue> #includ

题意

Sol

会了GSS1,GSS3就比较无脑了

直接加个单点修改即可,然后update一下

/**/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long 
#define rg register 
#define sc(x) scanf("%d", &x);
#define pt(x) printf("%d ", x);
#define db(x) double x 
#define rep(x) for(int i = 1; i <= x; i++)
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
char obuf[1<<24], *O = obuf;
#define OS  *O++ = '\n';
using namespace std;
using namespace __gnu_pbds;
const int MAXN = 50001, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}
void print(int x) {if(x > 9) print(x / 10);*O++ = x % 10 + '0';
}
#define ls k << 1
#define rs k << 1 | 1
int N, M;
int a[MAXN];
struct Node {int l, r, lmx, rmx, mx, sum;
}T[MAXN << 2];
void update(int k) {T[k].sum = T[ls].sum + T[rs].sum;T[k].mx = max(T[ls].mx, T[rs].mx);T[k].mx = max(T[k].mx, T[ls].rmx + T[rs].lmx);T[k].rmx = max(T[rs].rmx, T[rs].sum + T[ls].rmx);T[k].lmx = max(T[ls].lmx, T[ls].sum + T[rs].lmx);
}
void Build(int k, int ll, int rr) {T[k] = (Node) {ll, rr, 0, 0, 0};if(ll == rr) {T[k].lmx = T[k].rmx = T[k].mx = T[k].sum = a[ll]; return ;}int mid = ll + rr >> 1;Build(ls, ll, mid);Build(rs, mid + 1, rr);update(k);
}
Node merge(Node a, Node b) {Node now;now.sum = a.sum + b.sum;now.mx = max(a.mx, b.mx);now.mx = max(now.mx, a.rmx + b.lmx);now.rmx = max(b.rmx, b.sum + a.rmx);now.lmx = max(a.lmx, a.sum + b.lmx);    
//    printf("%d %d %d %d\n", now.mx, now.lmx, now.rmx, now.sum);return now;
}
Node Query(int k, int ll, int rr) {Node ans = (Node) {0, 0, 0, 0, 0};if(ll <= T[k].l && T[k].r <= rr) return T[k];int mid = T[k].l + T[k].r >> 1;/*if(ll <= mid) ans = Query(ls, ll, rr);if(rr  > mid) ans = merge(ans, Query(rs, ll, rr));*/if(ll > mid) return Query(rs, ll, rr);else if(rr <= mid) return Query(ls, ll, rr);else return merge(Query(ls, ll, rr), Query(rs, ll, rr));return ans;
}
void PointChange(int k, int pos, int val) {if(T[k].l == T[k].r) {T[k].lmx = T[k].rmx = T[k].mx = T[k].sum = val;return ; }int mid = T[k].l + T[k].r >> 1;if(pos <= mid) PointChange(ls, pos, val);if(pos >  mid) PointChange(rs, pos, val);update(k);
}
main() {//freopen("a.in", "r", stdin);N = read();for(int i = 1; i <= N; i++) a[i] = read();Build(1, 1, N);    int M = read();while(M--) {int opt = read(), x = read(), y = read();if(opt == 1) printf("%d\n", Query(1, x, y).mx);else PointChange(1, x, y);}//fwrite(obuf, O-obuf, 1 , stdout);return 0;
}
/*
5
-10 12 1 -45 134
5
1 5
2 3
4 5
1 4
3 5
*/

线性四叉树编码、 

 

 

转载于:https://www.cnblogs.com/zwfymqz/p/9563858.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/3/44331.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息