最近在做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;
}