[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=2482
[算法]
线段树维护历史最值
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 200010 typedef long long ll; typedef long double ld; const int T = 233333; struct query { int l , r; int id; } q[MAXN]; int n , m; int loc[MAXN << 2] , pre[MAXN << 2] , val[MAXN << 2]; ll ans[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } struct Segment_Tree { struct Node { int l , r; ll sum , hsum; ll taga , tagb; } a[MAXN << 2]; inline void build(int index , int l , int r) { a[index].l = l , a[index].r = r; if (l == r) return; int mid = (l + r) >> 1; build(index << 1 , l , mid); build(index << 1 | 1 , mid + 1 , r); } inline void pushdown(int index) { int l = a[index].l , r = a[index].r; int mid = (l + r) >> 1; if (l == r) return; a[index << 1].hsum = max(a[index << 1].hsum , a[index << 1].sum + a[index].tagb); a[index << 1 | 1].hsum = max(a[index << 1 | 1].hsum , a[index << 1 | 1].sum + a[index].tagb); a[index << 1].sum += a[index].taga; a[index << 1 | 1].sum += a[index].taga; chkmax(a[index << 1].tagb , a[index << 1].taga + a[index].tagb); chkmax(a[index << 1 | 1].tagb , a[index << 1 | 1].taga + a[index].tagb); a[index << 1].taga += a[index].taga; a[index << 1 | 1].taga += a[index].taga; a[index].taga = a[index].tagb = 0; } inline void update(int index) { a[index].sum = max(a[index << 1].sum , a[index << 1 | 1].sum); a[index].hsum = max(a[index << 1].hsum , a[index << 1 | 1].hsum); } inline void modify(int index , int l , int r , ll val) { pushdown(index); if (a[index].l == l && a[index].r == r) { a[index].sum += val; chkmax(a[index].hsum , a[index].sum); a[index].taga += val; chkmax(a[index].tagb , a[index].taga); } else { int mid = (a[index].l + a[index].r) >> 1; if (mid >= r) modify(index << 1 , l , r , val); else if (mid + 1 <= l) modify(index << 1 | 1 , l , r , val); else { modify(index << 1 , l , mid , val); modify(index << 1 | 1 , mid + 1 , r , val); } update(index); } } inline ll query(int index , int l , int r) { pushdown(index); if (a[index].l == l && a[index].r == r) return a[index].hsum; int mid = (a[index].l + a[index].r) >> 1; if (mid >= r) return query(index << 1 , l , r); else if (mid + 1 <= l) return query(index << 1 | 1 , l , r); else return max(query(index << 1 , l , mid) , query(index << 1 | 1 , mid + 1 , r)); } } SGT; inline bool cmp(query a , query b) { return a.r < b.r; } int main() { read(n); for (int i = 1; i <= n; i++) read(val[i]); read(m); for (int i = 1; i <= m; i++) { read(q[i].l); read(q[i].r); q[i].id = i; } sort(q + 1 , q + m + 1 , cmp); for (int i = 1; i <= n; i++) { pre[i] = loc[val[i] + T]; loc[val[i] + T] = i; } SGT.build(1 , 1 , n); int now = 1; for (int i = 1; i <= n; i++) { SGT.modify(1 , pre[i] + 1 , i , val[i]); while (now <= m && q[now].r == i) { ans[q[now].id] = max(SGT.query(1 , q[now].l , q[now].r) , 0LL); ++now; } } for (int i = 1; i <= m; i++) printf("%lld " , ans[i]); return 0; }