MarioYC's blog

By MarioYC, 12 years ago, In English

Hi everyone, I've been trying this problem, my approach was using sweep line after ordering the queries by its ending and considering only the last ocurrence of a number. However it fails for cases like:

N = 4

4 -2 3 -2

Q = 1

1 4

where the answer is 4,-2,3 which contains a -2 that isn't the last one, hence I return 7, but the correct answer is 5.

Any ideas on how to solve the problem?

My code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100000
#define MAXQ 100000

int a[MAXN],b[MAXN],pos[MAXN];
long long pref[4 * MAXN],suff[4 * MAXN],sum[4 * MAXN],best[4 * MAXN];
long long best_suff;

long long query(int node, int l, int r, int x, int y){
    if(r < x || l > y) return 0;
    
    if(x <= l && r <= y){
        long long ret = max(best[node],best_suff + pref[node]);
        best_suff = max(suff[node],best_suff + sum[node]);
        return ret;
    }else{
        int mi = (l + r) >> 1;
        long long ret1 = query(2 * node + 1,l,mi,x,y);
        long long ret2 = query(2 * node + 2,mi + 1,r,x,y);
        return max(ret1,ret2);
    }
}

void update(int node, int l, int r, int x, int val){
    if(r < x || l > x) return;
    
    if(l == r){
        pref[node] = suff[node] = best[node] = max(0,val);
        sum[node] = val;
    }else{
        int mi = (l + r) >> 1;
        
        update(2 * node + 1,l,mi,x,val);
        update(2 * node + 2,mi + 1,r,x,val);
        
        pref[node] = max(pref[2 * node + 1],sum[2 * node + 1] + pref[2 * node + 2]);
        suff[node] = max(suff[2 * node + 2],sum[2 * node + 2] + suff[2 * node + 1]);
        sum[node] = sum[2 * node + 1] + sum[2 * node + 2];
        best[node] = max(suff[2 * node + 1] + pref[2 * node + 2],max(best[2 * node + 1],best[2 * node + 2]));
    }
}

vector<int> q[MAXN],id[MAXN];
long long ans[MAXQ];

int main(){
    int N;
    scanf("%d",&N);
    
    for(int i = 0;i < N;++i){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    
    sort(b,b + N);
    int m = unique(b,b + N) - b;
    memset(pos,-1,sizeof pos);
    
    
    int Q;
    scanf("%d",&Q);
    
    for(int i = 0,l,r;i < Q;++i){
        scanf("%d %d",&l,&r);
        q[r - 1].push_back(l - 1);
        id[r - 1].push_back(i);
    }
    
    for(int i = 0;i < N;++i){
        update(0,0,N - 1,i,a[i]);
        
        int ind = lower_bound(b,b + m,a[i]) - b;
        
        if(pos[ind] != -1)
            update(0,0,N - 1,pos[ind],0);
        
        pos[ind] = i;
        
        for(int j = q[i].size() - 1;j >= 0;--j){
            best_suff = 0;
            ans[ id[i][j] ] = query(0,0,N - 1,q[i][j],i);
        }
    }
    
    for(int i = 0;i < Q;++i)
        printf("%lld\n",ans[i]);
    
    return 0;
}

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Every time I read this problem I can't get the statement :/

What do we have to do here?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Queries are intervals [l,r]

    You have to find a segment [x,y] (l <= x and y <= r)

    with maximum sum.

    But, when calculating the sum of a segment you only consider a number once.

    For example the sum of 1,1,2,3,3 is 1 + 2 + 3 = 6

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you able to say the answer for segments (l+1,r), (l-1,r) and (l,r+1) if you already know it for a segment (l,r)?

      If yes, you can use an interesting kind of sqrt-heuristic.

      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I think you could build two arrays to find the previous and next ocurrences of a given value, and so you if you have the answer for (l,r) you can calculate the answer (l+1,r), (l-1,r) and (l,r+1) in O(1).

»
12 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Yes, it can be solved with the approach similar to that you have described, I've got AC a few years ago.
Seems that my idea was similar to your in some things.
Think more on the data structure you use...
It's possible to get AC in O((N+M)logN) with a segment tree.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should maintain the possible sums in a data structure instead of only consider the last one.

Hope it helps :)

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it