JZTXT

GSS系列

发布时间 2023-03-22 21:08:47作者: Flandre_495

最近在做GSS系列，都是数据结构非常好的题，正适合本蒟蒻练习qwq

GSS1

最大子段和的经典题，区间的最大子段和考虑到三种情况，左区间的最大前缀，右区间的最大后缀，左区间最大后缀和右区间最大前缀拼接而成

不难想到用线段树记录区间最大前缀和prefix，区间最大后缀和suffix，区间最大子段和ans，再记录一下区间和sum来维护前缀后缀即可

ps:用结构体的方式写会简便很多，可以再用重载运算符来处理区间合并，码量会降不少www

my code 
#include<bits/stdc++.h>
#define lson (root<<1)
#define rson (root<<1|1)
using namespace std;
const int N=5e4+10;
int n,m,a[N];
#define seg segment_tree
struct segment_tree{
	int l,r,ans,sum,prefix,suffix;
	inline void init(int x){
		l=r=x;
		ans=sum=prefix=suffix=a[x];
	}
	friend seg operator + (const seg &ls,const seg &rs){
		seg rt;
		rt.l=ls.l,rt.r=rs.r;
		rt.sum=ls.sum+rs.sum;
		rt.prefix=max(ls.prefix,ls.sum+rs.prefix);
		rt.suffix=max(rs.suffix,rs.sum+ls.suffix);
		rt.ans=max({ls.ans,rs.ans,ls.suffix+rs.prefix});
		return rt;
	} 
}tr[N<<2];

inline void File(){
	freopen("GSS1.in","r",stdin);
	freopen("GSS1.out","w",stdout);
} 
 
inline void push_up(int root){
	tr[root]=tr[lson]+tr[rson];
}

inline void build(int root,int ll,int rr){
	if(ll==rr){
		tr[root].init(ll);
		return;
	}
	int mid=(ll+rr)>>1;
	build(lson,ll,mid);
	build(rson,mid+1,rr);
	push_up(root);
} 
#define l(x) tr[x].l
#define r(x) tr[x].r
inline segment_tree query(int root,int ll,int rr){
	if(ll<=l(root)&&rr>=r(root)){
		return tr[root];
	}	
	int mid=(l(root)+r(root))>>1;
	if(ll<=mid&&rr>mid){				
		return query(lson,ll,rr)+query(rson,ll,rr);	
	}
	else{	
		if(ll<=mid)return query(lson,ll,rr);
		if(rr>mid)return query(rson,ll,rr);
	}	
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}	
	build(1,1,n);
	scanf("%d",&m);
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);	
		printf("%d\n",query(1,l,r).ans);
	}
	return 0;
}

GSS3

同理GSS1，加上单点修改操作即可

my code 
#include<bits/stdc++.h>
#define lson (root<<1)
#define rson (root<<1|1)
using namespace std;
const int N=5e4+10;
int n,m,a[N];
#define seg segment_tree
struct segment_tree{
	int l,r,ans,sum,prefix,suffix;
	inline void init(int x){
		ans=sum=prefix=suffix=x;
	}
	friend seg operator + (const seg &ls,const seg &rs){
		seg rt;
		rt.l=ls.l,rt.r=rs.r;
		rt.sum=ls.sum+rs.sum;
		rt.prefix=max(ls.prefix,ls.sum+rs.prefix);
		rt.suffix=max(rs.suffix,rs.sum+ls.suffix);
		rt.ans=max({ls.ans,rs.ans,ls.suffix+rs.prefix});
		return rt;
	} 
}tr[N<<2];

inline void File(){
	freopen("GSS3.in","r",stdin);
	freopen("GSS3.out","w",stdout);
} 
#define l(x) tr[x].l
#define r(x) tr[x].r
inline void push_up(int root){
	tr[root]=tr[lson]+tr[rson];
}

inline void build(int root,int ll,int rr){
	l(root)=ll,r(root)=rr;
	if(ll==rr){
		tr[root].init(a[ll]);
		return;
	}
	int mid=ll+rr>>1;
	build(lson,ll,mid);
	build(rson,mid+1,rr);
	push_up(root);
} 

inline void modify(int root,int x,int val){
	if(l(root)==r(root)){
		tr[root].init(val);
		return;
	}
	int mid=l(root)+r(root)>>1;
	if(x<=mid)modify(lson,x,val);
	else modify(rson,x,val);
	push_up(root);
}

inline segment_tree query(int root,int ll,int rr){
	if(ll<=l(root)&&rr>=r(root)){
		return tr[root];
	}	
	int mid=l(root)+r(root)>>1;
	if(ll<=mid&&rr>mid){				
		return query(lson,ll,rr)+query(rson,ll,rr);	
	}
	else{	
		if(ll<=mid)return query(lson,ll,rr);
		if(rr>mid)return query(rson,ll,rr);
	}	
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}	
	build(1,1,n);
	scanf("%d",&m);
	int opt,l,r;
	while(m--){
		scanf("%d",&opt);
		switch(opt){
			case 0:
				scanf("%d%d",&l,&r);
				modify(1,l,r);
				break;
			case 1:				
				scanf("%d%d",&l,&r);	
				printf("%d\n",query(1,l,r).ans);
				break;
		}
	}
	return 0;
}

GSS4

看到了这题，我突然联想到了数列分块入门5，不觉得这两题有异曲同工之妙吗？（好吧其实就相当于一道题）

于是用分块打了，因为一个（正）数多次开方后的结果必定为1，（如果有0的话那就是0）

那么我们就把块中结果全是1或0的打上标记，下次修改的时候直接跳过即可，对于其他的情况就暴力开方修改

结果T掉了，换上了快读才AC，还是我太弱了qwq

my code 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
inline long long read(){
	long long x=0;char ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x;
}
inline void File(){
	freopen("GSS4.in","r",stdin);
	freopen("GSS4.out","w",stdout);
} 
bool tag[N];
int n,t;
long long a[N],L[N],R[N],pos[N],sum[N];
inline void pre_work(){
	t=sqrt(n);
	for(int i=1;i<=n;++i) L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n){t++;L[t]=R[t-1]+1;R[t]=n;}
	for(int i=1;i<=t;++i)
		for(int j=L[i];j<=R[i];++j)
			pos[j]=i,sum[i]+=a[j];
} 

inline void update(int x){
	tag[x]=true;
	for(int i=L[x];i<=R[x];++i){
		sum[x]-=a[i];
		a[i]=sqrt(a[i]);
		sum[x]+=a[i];
		if(a[i]>1)tag[x]=false;
	}
}

inline void change(int l,int r){
	if(pos[l]==pos[r]){		
		for(int i=l;i<=r;++i){
			sum[pos[l]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[l]]+=a[i];
		}
	}
	else{
		for(int i=pos[l]+1;i<=pos[r]-1;++i) if(!tag[i]) update(i);
		for(int i=l;i<=R[pos[l]];++i){
			sum[pos[l]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[l]]+=a[i];
		}
		for(int i=L[pos[r]];i<=r;++i){
			sum[pos[r]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[r]]+=a[i];
		}
	}
}

inline void ask(int l,int r){
	long long ans=0;
	if(pos[l]==pos[r]){
		for(int i=l;i<=r;++i) ans+=a[i]; 
	}
	else{
		for(int i=pos[l]+1;i<=pos[r]-1;++i) ans+=sum[i];
		for(int i=l;i<=R[pos[l]];++i) ans+=a[i];
		for(int i=L[pos[r]];i<=r;++i) ans+=a[i];
	}
	printf("%lld\n",ans);
}
int main(){
	for(int T=1,opt,l,r,c,m;(~scanf("%d",&n));++T){		
		memset(tag,0,sizeof(tag));
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=n;++i)a[i]=read(); pre_work();
		m=read();
		printf("Case #%d:\n",T);
		for(int i=1;i<=m;++i){
			opt=read();l=read();r=read(); if(l>r) swap(l,r);
			if(opt) ask(l,r);
			else change(l,r);
		}	
		printf("\n");		
	}
	return 0;
}

之后又调了一个线段树版本的，思路同理分块，遇到全为0/1的区间就跳过，会比分块快很多qaq

my code 
#include<bits/stdc++.h>
#define lson (root<<1)
#define rson (root<<1|1)
inline long long read(){
	long long x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x;
}

using namespace std;
const int N=1e5+10;
int n,m;
long long a[N];
struct segment_tree{
	int l,r;long long sum;bool tag;
	inline void check(long long x){
		sum=x;
		if(sum<=1)tag=true;
		else tag=false;
	}
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define sum(x) tr[x].sum
	#define tag(x) tr[x].tag
}tr[N<<2];

inline void File(){
	freopen("GSS4.in","r",stdin);
	freopen("GSS4.out","w",stdout);
} 

inline void push_up(int root){
	sum(root)=sum(lson)+sum(rson);
	tag(root)=(tag(lson)&&tag(rson));
}

inline void build(int root,int ll,int rr){
	l(root)=ll,r(root)=rr;
	if(l(root)==r(root)){
		tr[root].check(a[ll]);
		return;
	}
	int mid=ll+rr>>1;
	build(lson,ll,mid);
	build(rson,mid+1,rr);
	push_up(root);
} 

inline void modify(int root,int ll,int rr){
	if(tag(root))return;
	if(l(root)==r(root)){
		tr[root].check(sqrt(sum(root)));
		return;
	}
	int mid=l(root)+r(root)>>1;
	if(ll<=mid)modify(lson,ll,rr);
	if(rr>mid) modify(rson,ll,rr);
	push_up(root);
}

inline long long query(int root,int ll,int rr){
	if(ll<=l(root)&&rr>=r(root)){
		return sum(root);
	}	
	int mid=l(root)+r(root)>>1;
	long long ans=0;
	if(ll<=mid)ans+=query(lson,ll,rr);
	if(rr>mid)ans+=query(rson,ll,rr);
	return ans;
}

int main(){
	for(int T=1,m;(~scanf("%d",&n));++T){
		printf("Case #%d:\n",T);
		memset(a,0,sizeof(a));memset(tr,0,sizeof(tr));
		for(int i=1;i<=n;++i) a[i]=read(); 
		build(1,1,n);
		m=read();
		for(int i=1,opt,l,r;i<=m;++i){
			opt=read();l=read();r=read(); if(l>r) swap(l,r);
			if(opt) printf("%lld\n",query(1,l,r));
			else modify(1,l,r);	
		}
		printf("\n");
	}
	return 0;
}