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