先放代码。

#include<bits/stdc++.h>
#define add 1000010
#define MAXN 100010
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
typedef long long ll;
struct node{
    int l, r;
    ll now_res, now_tag, max_res, max_tag;
};
struct ques{ int l, r, id; };
ques ask[MAXN];
node tree[MAXN << 2];
bool operator > (ques a, ques b){
    if(a.r == b.r) return a.r > b.r;
    return a.l > b.l;
}
bool operator < (ques a, ques b){
    if(a.r == b.r) return a.r < b.r;
    return a.l < b.l;
}
int n, q;
int a[MAXN], pos[add << 1], pre[MAXN];
ll ans[MAXN];
void push_up(node &now, node &ls, node &rs){
    now.now_res = max(ls.now_res, rs.now_res);
    now.max_res = max(ls.max_res, rs.max_res);
    now.now_tag = now.max_tag = 0;
}
void push_down(int now){
    tree[lson].max_res = max(tree[lson].max_res, tree[lson].now_res + tree[now].max_tag);
    tree[lson].max_tag = max(tree[lson].max_tag, tree[lson].now_tag + tree[now].max_tag);
    tree[rson].max_res = max(tree[rson].max_res, tree[rson].now_res + tree[now].max_tag);
    tree[rson].max_tag = max(tree[rson].max_tag, tree[rson].now_tag + tree[now].max_tag);
    tree[lson].now_res += tree[now].now_tag; tree[lson].now_tag += tree[now].now_tag;
    tree[rson].now_res += tree[now].now_tag; tree[rson].now_tag += tree[now].now_tag;
    tree[now].max_tag = tree[now].now_tag = 0;
}
void build(int now, int l, int r){
    tree[now].l = l; tree[now].r = r;
    if(tree[now].l == tree[now].r) return ;
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    push_up(tree[now], tree[lson], tree[rson]);
}
void update(int now, int l, int r, int val){
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].now_res += val; tree[now].max_res = max(tree[now].max_res, tree[now].now_res);
        tree[now].now_tag += val; tree[now].max_tag = max(tree[now].max_tag, tree[now].now_tag);
        return ;
    }
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) update(lson, l, r, val);
    else if(l > mid) update(rson, l, r, val);
    else update(lson, l, mid, val), update(rson, mid + 1, r, val);
    push_up(tree[now], tree[lson], tree[rson]);
}
node query(int now, int l, int r){
    if(tree[now].l >= l && tree[now].r <= r){
        return tree[now];
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else{
        node ls = query(lson, l, mid), rs = query(rson, mid + 1, r), res;
        res.l = l; res.r = r;
        push_up(res, ls, rs);
        return res;
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i = 1; i <= n; i++){
        int tmp = a[i] + add;
        pre[i] = pos[tmp];
        pos[tmp] = i;
    }
    scanf("%d",&q);
    for(int i = 1; i <= q; i++) scanf("%d%d",&ask[i].l,&ask[i].r), ask[i].id = i;
    sort(ask + 1, ask + q + 1, greater<ques>());
    // printf("------------\n");
    // for(int i = 1; i <= q; i++) printf("%d %d\n",ask[i].l,ask[i].r);
    build(1, 1, n);
    for(int i = 1, j = 1; i <= n; i++){
        printf("%d ",pre[i]);
        update(1, pre[i] + 1, i, a[i]);
        // printf("i = %d, j = %d, [%d, %d]\n",i,j,ask[j].l,ask[j].r);
        while(j <= q && ask[j].r == i){
            // printf("%d ",ask[j].id);
            ans[ask[j].id] = query(1, ask[j].l, ask[j].r).max_res;
            j++;
        }
    }
    printf("\n");
    for(int i = 1; i <= q; i++) printf("%lld\n",ans[i]);  
    return 0;
}

会被下面这组数据 Hack 掉，但不知道哪里错了：

10
1 2 3 2 1 -1 5 2 -5 5
4
1 10
2 8
3 5
2 4