「SP1043」GSS1 - Can you answer these queries I

传送门

Luogu

解题思路

这题就是 GSS3 的一个退化版，不带修改操作的区间最大子段和，没什么好讲的。

细节注意事项

• 咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

const int _ = 50000 + 10;

int n, m, a[_];

struct node{ int sum, L, R, mx; }t[_ << 2];

inline int lc(int p) { return p << 1; }

inline int rc(int p) { return p << 1 | 1; }

inline void pushup(int p) {

	t[p].sum = t[lc(p)].sum + t[rc(p)].sum;

	t[p].L = max(t[lc(p)].L, t[lc(p)].sum + t[rc(p)].L);

	t[p].R = max(t[rc(p)].R, t[rc(p)].sum + t[lc(p)].R);

	t[p].mx = max(t[lc(p)].R + t[rc(p)].L, max(t[lc(p)].mx, t[rc(p)].mx));

}

inline void build(int p = 1, int l = 1, int r = n) {

	if (l == r) { t[p] = (node) { a[l], a[l], a[l], a[l] }; return; }

	int mid = (l + r) >> 1;

	build(lc(p), l, mid), build(rc(p), mid + 1, r), pushup(p);

}

inline node query(int ql, int qr, int p = 1, int l = 1, int r = n) {

	if (ql <= l && r <= qr) return t[p];

	int mid = (l + r) >> 1;

	if (ql > mid) return query(ql, qr, rc(p), mid + 1, r);

	if (qr <= mid) return query(ql, qr, lc(p), l, mid);

	node ls = query(ql, mid, lc(p), l, mid);

	node rs = query(mid + 1, qr, rc(p), mid + 1, r);

	node res;

	res.sum = ls.sum + rs.sum;

	res.L = max(ls.L, ls.sum + rs.L);

	res.R = max(rs.R, rs.sum + ls.R);

	res.mx = max(ls.R + rs.L, max(ls.mx, rs.mx));

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n);

	for (rg int i = 1; i <= n; ++i) read(a[i]);

	build();

	read(m);

	for (int ql, qr; m--; )

		read(ql), read(qr), printf("%d\n", query(ql, qr).mx);

	return 0;

}

完结撒花 \(qwq\)