Spoj GSS 系列….
GSS 1
线段树最长字段和裸题
GSS 2
题意：给出$n$个数，$q$次询问求$[l,r]$最大子段和，相同的数只算一次。
线段树离线好题
考虑这题相同的数只算一次，也就是颜色问题，我们可以从颜色思考，可以发现能离线。
我们将询问按右端点排序，然后从左到右扫描到$i$，然后线段树每个节点$j$记录$\text{sum}(j)=\sum\limits_{j + 1 \leq k \leq i} a_k$，即我们维护的线段树每个节点都是区间$[j+1,i]$的值，我们维护的线段树实际上是区间套上了区间。
先不考虑颜色不同的情况，我们每次扫描到$i$更新，相当于是在线段树上$[1,i]$更新，然后处理$r=i$的询问，答案显然是$\max\limits_{l \leq j \leq r} (\text{sum}(j))$，但是好像不太正确，因为不一定右端点在$r$最优。所以我们要记录整个过程中的最大值 (历史最大值)。
考虑维护
max_now, 当前区间$\max \text{sum}(j)$lazy_now,当前区间更新标记max_old, 当前区间历史最大值lazy_old,当前区间历史最大更新标记
now的就按照常规线段树维护最大值的方法来更新
然后update时
lazy_now[o] += v;
max_now[o] += v; // now 按照常规线段树维护最大值的方法来更新
chkmax(lazy_old[o], lazy_now[o]);
chkmax(max_old[o], max_now[o]); // 更新历史最优值
pushdown时
chkmax(max_old[lc], max_now[lc] + lazy_old[o]);
chkmax(max_old[rc], max_now[rc] + lazy_old[o]);
chkmax(lazy_old[lc], lazy_now[lc] + lazy_old[o]);
chkmax(lazy_old[rc], lazy_now[rc] + lazy_old[o]); // 更新历史最优值
max_now[lc] += lazy_now[o];
max_now[rc] += lazy_now[o];
lazy_now[lc] += lazy_now[o];
lazy_now[rc] += lazy_now[o]; // now 按照常规线段树维护最大值的方法来更新
lazy_now[o] = lazy_old[o] = 0;
值得注意的是，为什么我们用lazy_now[rc] + lazy_old[o], max_now[rc] + lazy_old[o]而不是都用old。因为这样会导致最大字段和不连续。
比如说有$4$个数是2 -1 -3 1执行这个命令就相当于把$2$加进去的时候lazy_old[1]=2,然后加$-1$和$-3$的时候lazy_old[1]不会更新，把$1$加进去的时候又会更新lazy_old[1]=2+1=3，此时，就相当于把$2$和$1$加起来了而没有加上$-1$和$-3$，不再是一个连续的区间！
如果考虑去重的话，那么每个数字记录他前一个出现在$\text{pre}_i$，然后每次更新$[\text{pre}_i + 1, i]$即可
知识点
1、线段树记得开4倍空间
2、离线1、右端点排序、2、记录前驱颜色
3、线段树叶子节点记录位置$\to$当前扫描位置的值
4、历史最优值的记录
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 100000 + 5, BS = 100000;
LL chkmax(LL &x, LL y) {return x = (x > y) ? x : y;}
LL chkmin(LL &x, LL y) {return x = (x < y) ? x : y;}
LL n, Q, a[MAXN], tax[MAXN * 2], pre[MAXN], ans[MAXN];
struct qry {
LL l, r, id;
bool operator < (const qry &rhs) const {return r < rhs.r;}
} xw[MAXN];
#define M ((l + r) >> 1)
#define lc (o << 1)
#define rc (o << 1 | 1)
#define ls lc, l, M
#define rs rc, M + 1, r
LL max_now[MAXN * 4], lazy_now[MAXN * 4], max_old[MAXN * 4], lazy_old[MAXN * 4];
void pushup(LL o) {
max_now[o] = max(max_now[lc], max_now[rc]);
max_old[o] = max(max_old[lc], max_old[rc]);
}
void pushdown(LL o) {
chkmax(max_old[lc], max_now[lc] + lazy_old[o]);
chkmax(max_old[rc], max_now[rc] + lazy_old[o]);
chkmax(lazy_old[lc], lazy_now[lc] + lazy_old[o]);
chkmax(lazy_old[rc], lazy_now[rc] + lazy_old[o]); // 更新历史最优值
max_now[lc] += lazy_now[o];
max_now[rc] += lazy_now[o];
lazy_now[lc] += lazy_now[o];
lazy_now[rc] += lazy_now[o]; // now 按照常规线段树维护最大值的方法来更新
lazy_now[o] = lazy_old[o] = 0;
}
void update(LL o, LL l, LL r, LL x, LL y, LL v) {
if (x <= l && r <= y) {
lazy_now[o] += v;
max_now[o] += v; // now 按照常规线段树维护最大值的方法来更新
chkmax(lazy_old[o], lazy_now[o]);
chkmax(max_old[o], max_now[o]); // 更新历史最优值
return ;
}
pushdown(o);
if (x <= M) update(ls, x, y, v);
if (M < y) update(rs, x, y, v);
pushup(o);
}
LL query(LL o, LL l, LL r, LL x, LL y) {
if (x <= l && r <= y) return max_old[o];
pushdown(o);
LL ret = 0;
if (x <= M) chkmax(ret, query(ls, x, y));
if (M < y) chkmax(ret, query(rs, x, y));
return ret;
}
void clean() {
}
int solve() {
clean();
cin >> n;
for (LL i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
pre[i] = tax[a[i] + BS], tax[a[i] + BS] = i;
}
cin >> Q;
for (LL i = 1; i <= Q; ++i) scanf("%lld%lld", &xw[i].l, &xw[i].r), xw[i].id = i;
sort(xw + 1, xw + 1 + Q);
LL j = 1;
for (LL i = 1; i <= n; ++i) {
update(1, 1, n, pre[i] + 1, i, a[i]);
while (j <= Q && xw[j].r <= i) ans[xw[j].id] = query(1, 1, n, xw[j].l, xw[j].r), ++j;
}
for (LL i = 1; i <= Q; ++i) printf("%lld\n", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
GSS 3
同 GSS 1
