spoj GSS系列之GSS1 和 GSS3

题目：

GSS1

GSS3

题意：

维护一个数列a[1], a[2], …, a[N] . (|a[i]| ≤ 15007, 1 ≤ N ≤ 50000)。

有一种共M个操作：Query(x, y) = max{a[i] + a[i + 1] + … + a[j]; x ≤ i ≤ j ≤ y}。

思路：

没啥特别思路。。就是。。看代码吧。。

另外时间卡的特别紧，JAVA同学请注意！

感觉就是弄清楚lx和rx表达的到底是啥就好说了！！

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#define INF 0x3f3f3f3f  
using namespace std;  
struct node{  
    int sum,mx,lx,rx;    //save this line's sum,maxx,lson's max and rson's max; 但是请注意：是左起和右起最大和不是严格的左端！！！！
    node(int x = ){  
        sum = mx = lx = rx = x;    //interesting new
    }  
}tree[];  
int ql,qr;  
node update(node x, node y){       
    node ans;  
    ans.sum = x.sum + y.sum;          
    ans.mx = max(x.rx + y.lx, max(x.mx, y.mx));  
    ans.lx = max(x.lx, x.sum + y.lx);  //不确定最大和到底有没有越过中点！
    ans.rx = max(y.rx, y.sum + x.rx);  //同理
    return ans;  
}  

void build(int num,int l,int r){  
    if(l == r){  
        int x;  
        scanf("%d",&x);  
        tree[num] = node(x);  
        return ;  
    }  
    int mid = (l+r)>> ;  
    build(num*,l,mid);  
    build(num*+,mid+,r);  
    tree[num] = update(tree[num*], tree[num*+]);  
}  

node query(int num,int l,int r){  
    if(ql <= l && r <= qr)  return tree[num];  
    node x(-INF), y(-INF);  
    x.sum=y.sum=;
    int mid = (l+r)>> ;  
    if (ql <= mid)  x = query(num*,l,mid);  
    if (qr > mid)   y = query(num*+,mid+,r); 
    return update(x,y);  
}  
int main(){  
    int n,m;  
    while(scanf("%d", &n)!=EOF){  
        build(,,n);  
        scanf("%d",&m);  
        while(m--){  
            scanf("%d%d",&ql,&qr);  
            printf("%d\n", query(,,n).mx);  
        }  
    }  
    return ;  
} 
           

GSS 3

在上题基础上加了个 修改！

差不多加一个修改函数就行！

上代码：

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#define INF 0x3f3f3f3f  
using namespace std;  
struct node{  
    int sum,mx,lx,rx;    //save this line's sum,maxx,lson's max and rson's max;
    node(int x = ){  
        sum = mx = lx = rx = x;    //interesting new
    }  
}tree[];  
int ql,qr;  
int in[];
node update(node x, node y){       
    node ans;  
    ans.sum = x.sum + y.sum;          
    ans.mx = max(x.rx + y.lx, max(x.mx, y.mx));  
    ans.lx = max(x.lx, x.sum + y.lx);  
    ans.rx = max(y.rx, y.sum + x.rx);  
    return ans;  
}   
void build(int num,int l,int r){  
    if(l == r){
        int x;   
        scanf("%d",&x);  
        tree[num] = node(x);  
        return;  
    }  
    int mid = (l+r)>> ;  
    build(num*,l,mid);  
    build(num*+,mid+,r);  
    tree[num] = update(tree[num*], tree[num*+]);  
} 
node modify(int pos,int val,int num,int l,int r)
{
    if(l ==pos && pos== r)
    {
        tree[num]=node(val);
        return tree[num];
    }
    int m=l+r>>;
    if(pos<=m) modify(pos,val,num*,l,m);
    else modify(pos,val,num*+,m+,r);
    tree[num]=update(tree[num*],tree[num*+]);   //update the new answer 
}
node query(int num,int l,int r){  
    if(ql <= l && r <= qr)  return tree[num];  
    node x(-INF), y(-INF);  
    x.sum=y.sum=;
    int mid = (l+r)>> ;  
    if (ql <= mid)  x = query(num*,l,mid);  
    if (qr > mid)   y = query(num*+,mid+,r); 
    return update(x,y);
}   
int main(){  
    int n,m,op;  
    while(scanf("%d", &n)!=EOF){ 
        build(,,n);
        scanf("%d",&m);  
        while(m--){  
            scanf("%d%d%d",&op,&ql,&qr);  
            if(op == ) modify(ql,qr,,,n);
            else printf("%d\n", query(,,n).mx);  
        }  
    }  
    return ;  
}  

           

原谅我这两篇写的不太认真。。。

应该还有后续GSS系列！