SPOJ GSS 系列

SPOJ GSS系列是一系列序列维护的问题。
大部分用线段树，Splay等可以解决。

1043. GSS1

题意：给定长度为N的数串，M个询问查询[a,b]的的最大连续子段和。
线段树每个节点维护左端最大连续和，右端最大连续和，中间最大连续和。
就可以快速合并了。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[50005];
int sum[50000*4],ls[50000*4],rs[50000*4],mx[50000*4];
inline void up(int o){
	sum[o]=sum[o<<1]+sum[o<<1|1];
	ls[o]=max(ls[o<<1],sum[o<<1]+ls[o<<1|1]);
	rs[o]=max(rs[o<<1|1],sum[o<<1|1]+rs[o<<1]);
	mx[o]=max(max(mx[o<<1],mx[o<<1|1]),ls[o<<1|1]+rs[o<<1]);
}
void bd(int o,int l,int r){
	if(l==r){
        mx[o]=ls[o]=rs[o]=sum[o]=a[l];
	}else{
        int mid=(l+r)/2;
        bd(o<<1,l,mid);
        bd(o<<1|1,mid+1,r);
        up(o);
	}
	//printf("%d %d %d\n",l,r,mx[o]);
}
int _l,_r;
int lmx,mxx;
void ask(int o,int l,int r){
//	printf("# %d %d %d\n",o,l,r);
	if(_l<=l&&r<=_r){
        mxx=max(mxx,max(mx[o],lmx+ls[o]));
        lmx=max(0,max(sum[o]+lmx,rs[o]));
	}else{
        int mid=(l+r)>>1;
        if(_l<=mid) ask(o<<1,l,mid);
        if(_r>mid) ask(o<<1|1,mid+1,r);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	bd(1,1,n);
	scanf("%d",&m);
	for(int i=0,l,r;i<m;i++){
        scanf("%d%d",&l,&r);
        lmx=0;
        mxx=-0x3f3f3f3f;
        if(l>r) swap(l,r);
        _l=l,_r=r;
        ask(1,1,n);
        printf("%d\n",mxx);
	}
//	while(1);
	return 0;
}

1557. GSS2

题意与上一题相同，只是相同的数只算一次。
离线做。。类似tyvj cpu监控。
将所有查询按右端点排序。
维护所有前缀的后缀。
即固定右端点时不同左端点的序列和。
设一个位置x的数字a[x]上一次出现的位置是pos[x].
考虑右端点从r变到r+1时，以r+1结尾的序列只是把pos[r+1]…r+1加上了a[r+1]。
维护每个点的当前最大值，历史最大值即可。
对于询问(l,r)，(l,r)上的历史最大值即为答案。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,q,a[100005];
int pos[100005],last[200005];
const int zero=100000;
const int MAXN=100005*4;
int mx[MAXN],hmx[MAXN],tag[MAXN],htag[MAXN];
struct N{
	int l,r,id;
	friend bool operator < (const N&a,const N&b){
        return a.r<b.r;
	}
}Q[100005];
int ans[MAXN];
int _l,_r,_c;
void update(int o){
	mx[o]+=_c;
	hmx[o]=max(hmx[o],mx[o]);
	tag[o]+=_c;
	htag[o]=max(htag[o],tag[o]);
}
void pd(int o){
	if(htag[o]){
        hmx[o<<1]=max(hmx[o<<1],mx[o<<1]+htag[o]);
        hmx[o<<1|1]=max(hmx[o<<1|1],mx[o<<1|1]+htag[o]);
		
        htag[o<<1]=max(htag[o<<1],tag[o<<1]+htag[o]);
        htag[o<<1|1]=max(htag[o<<1|1],tag[o<<1|1]+htag[o]);
		
        htag[o]=0;
	}
	if(tag[o]){
        mx[o<<1]+=tag[o];
        mx[o<<1|1]+=tag[o];
		
        tag[o<<1]+=tag[o];
        tag[o<<1|1]+=tag[o];
        tag[o]=0;
	}
}
void up(int o){
	hmx[o]=max(hmx[o<<1],hmx[o<<1|1]);
	mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
void add(int o,int l,int r){
	if(_l<=l&&r<=_r){
        update(o);
	}else{
        int mid=(l+r)>>1;
        pd(o);
        if(_l<=mid) add(o<<1,l,mid);
        if(_r>mid)  add(o<<1|1,mid+1,r);
        up(o);
	}
}
void ask(int o,int l,int r){
	if(_l<=l&&r<=_r){
        _c=max(_c,hmx[o]);
	}else{
        int mid=(l+r)>>1;
        pd(o);
        if(_l<=mid) ask(o<<1,l,mid);
        if(_r>mid) ask(o<<1|1,mid+1,r);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
        if(last[a[i]+zero]) pos[i]=last[a[i]+zero];
        last[a[i]+zero]=i;
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q,Q+q);
	int k=0;
	for(int i=1;i<=n;i++){
        _l=pos[i]+1,_r=i,_c=a[i];
        add(1,1,n);
        while(k<q&&Q[k].r==i){
            _l=Q[k].l;
            _c=0;
            ask(1,1,n);
            ans[Q[k].id]=_c;
            k++;
        }
	}
	for(int i=0;i<q;i++) printf("%d\n",ans[i]);
//	while(1);
	return 0;
}

1716.GSS3

题意：GSS1支持修改。
反正也写线段树了，那就修改吧。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[50005];
int sum[50000*4],ls[50000*4],rs[50000*4],mx[50000*4];
inline void up(int o){
	sum[o]=sum[o<<1]+sum[o<<1|1];
	ls[o]=max(ls[o<<1],sum[o<<1]+ls[o<<1|1]);
	rs[o]=max(rs[o<<1|1],sum[o<<1|1]+rs[o<<1]);
	mx[o]=max(max(mx[o<<1],mx[o<<1|1]),ls[o<<1|1]+rs[o<<1]);
}
void bd(int o,int l,int r){
	if(l==r){
        mx[o]=ls[o]=rs[o]=sum[o]=a[l];
	}else{
        int mid=(l+r)/2;
        bd(o<<1,l,mid);
        bd(o<<1|1,mid+1,r);
        up(o);
	}
}
int _l,_r;
int lmx,mxx;
void ask(int o,int l,int r){
	if(_l<=l&&r<=_r){
        mxx=max(mxx,max(mx[o],lmx+ls[o]));
        lmx=max(0,max(sum[o]+lmx,rs[o]));
	}else{
        int mid=(l+r)>>1;
        if(_l<=mid) ask(o<<1,l,mid);
        if(_r>mid) ask(o<<1|1,mid+1,r);
	}
}
void mo(int o,int l,int r,int p,int to){
	if(l==r){
        mx[o]=ls[o]=rs[o]=sum[o]=to;
	}else{
        int mid=(l+r)>>1;
        if(p<=mid) mo(o<<1,l,mid,p,to);
        else mo(o<<1|1,mid+1,r,p,to);
        up(o);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	bd(1,1,n);
	scanf("%d",&m);
	for(int i=0,t,l,r;i<m;i++){
        scanf("%d%d%d",&t,&l,&r);
        if(t&1){
            lmx=0;
            mxx=-0x3f3f3f3f;
            if(l>r) swap(l,r);
            _l=l,_r=r;
            ask(1,1,n);
            printf("%d\n",mxx);
        }else{
            mo(1,1,n,l,r);
        }
	}
//	while(1);
	return 0;
}

2713.GSS4

题意：给你一个数列，需要完成区间求和，区间开平方。
开平方没什么性质。
只好暴力开了。
线段树维护一个tag。
当这个区间都开成1了就不用再开了。
就好了。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int n;
LL a[100005];
LL sum[100005*4];
bool tag[100005*4];
int _l,_r;LL _c;
void bd(int o,int l,int r){
	if(l==r){
        sum[o]=a[l];
        if(sum[o]<=1) tag[o]=1;
	}else{
        int mid=(l+r)/2;
        bd(o<<1,l,mid);bd(o<<1|1,mid+1,r);
        tag[o]=tag[o<<1]&tag[o<<1|1];
        sum[o]=sum[o<<1]+sum[o<<1|1];
	}
}
void ask(int o,int l,int r){
	if(_l<=l&&r<=_r){
        _c+=sum[o];
	}else{
        int mid=(l+r)>>1;
        if(_l<=mid) ask(o<<1,l,mid);
        if(_r>mid) ask(o<<1|1,mid+1,r);
	}
}
void mo(int o,int l,int r){
	if(tag[o]) return;
	if(_l<=l&&r<=_r){
        if(l==r){
            sum[o]=sqrt(sum[o]);
            if(sum[o]<=1) tag[o]=1;
        }else{
            int mid=(l+r)>>1;
            mo(o<<1,l,mid);
            mo(o<<1|1,mid+1,r);
            tag[o]=tag[o<<1]&tag[o<<1|1];
            sum[o]=sum[o<<1]+sum[o<<1|1];
        }
	}else{
        int mid=(l+r)>>1;
        if(_l<=mid) mo(o<<1,l,mid);
        if(_r>mid) mo(o<<1|1,mid+1,r);
        tag[o]=tag[o<<1]&tag[o<<1|1];
        sum[o]=sum[o<<1]+sum[o<<1|1];
	}
}
//#define lld I64d
int kase;
int main(){
	while(~scanf("%d",&n)){
        printf("Case #%d:\n",++kase);
        memset(tag,0,sizeof tag);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        bd(1,1,n);
        int m,t,l,r;
        scanf("%d",&m);
        while(m--){
            scanf("%d%d%d",&t,&l,&r);
            if(l>r) swap(l,r);
            if(t&1){
                _c=0;
                _l=l,_r=r;
                ask(1,1,n);
                printf("%lld\n",_c);
            }else{
                _l=l,_r=r;
                mo(1,1,n);
            }
        }
        puts("");
	}
	return 0;
}

2916.GSS5

题意：在GSS1的基础上。
增加了询问需要满足l在[x1,y1]之间，r在[x2,y2]之间。
好像讨论就可以了：

待填。

1043. GSS1#

1557. GSS2#

1716.GSS3#

2713.GSS4#

2916.GSS5#

1043. GSS1

1557. GSS2

1716.GSS3

2713.GSS4

2916.GSS5