文章目录

这个

$GSS$系列全部是跟子段有关的数据结构菜题。

于是来水一篇博客。

GSS1

题意简述：求不带修的最大子段和。

---

思路：直接线段树走一发。

代码：

#include
    
     #define ri register intusing namespace std;const int N=5e4+5;int n,a[N];inline int max(const int&a,const int&b){
    return a>b?a:b;}inline int max(const int&a,const int&b,const int&c){
    return a>b?(a>c?a:c):(b>c?b:c);}namespace SGT{
    	#define lc (p<<1)	#define rc (p<<1|1)	#define mid (T[p].l+T[p].r>>1)	struct Val{
    		int ls,rs,ms,sum;		inline void init(const int&x){
    ls=rs=ms=sum=x;}	};	inline Val operator+(const Val&a,const Val&b){
    return (Val){
    max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}	struct Node{
    int l,r;Val val;}T[N<<2];	inline void pushup(int p){
    T[p].val=T[lc].val+T[rc].val;}	inline void build(int p,int l,int r){
    		T[p].l=l,T[p].r=r;		if(l==r)return T[p].val.init(a[l]);		build(lc,l,mid),build(rc,mid+1,r),pushup(p);	}	inline Val query(int p,int ql,int qr){
    		if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;		if(qr<=mid)return query(lc,ql,qr);		if(ql>mid)return query(rc,ql,qr);		return query(lc,ql,qr)+query(rc,ql,qr);	}}inline int read(){
    	int ans=0;	bool f=1;	char ch=getchar();	while(!isdigit(ch)){
    if(ch=='-')f^=1;ch=getchar();}	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return f?ans:-ans;}int main(){
    	n=read();	for(ri i=1;i<=n;++i)a[i]=read();	SGT::build(1,1,n);	for(ri tt=read(),x;tt;--tt)x=read(),cout<
     
      <<'\n';	return 0;}
     
    

---

GSS2

唯一感觉有点思维难度的题。

题意简述：求不带修的最大子段和，对于一个子段里面同一个数值只能产生一次贡献。

---

思路：

考虑离线询问。

我们对于第$i$次询问$(l,r)$把它扔进一个用$vector$储存的$qry$数组中，即qryr.push_back(l,i)qry_r.push\_back(l,i)qryr​.push_back(l,i)，然后我们从左往右加点。

当处理到这个询问的时候，相当于只用问对于所有下标在$[l,r]$之间的点，以它们为左端点开始向右延伸的最大子段的最大值是多少。

这个东西怎么维护？

我们用增量构造法，考虑把前面的在$i-1$结尾的所有子段即$[1,i-1],[2,i-1],...,[i-1,i-1]$这些子段同时加上一个aia_iai​去更新$1$~$i-1$处的答案。

这样我们实际上对于一个点$i$只需要维护两个东西：

1. $Sum(i,now)$，这个$Sum$的求法是题意的求法，即相同的值只算一次。
2. $hisSum(i,now)=max(Sum(i,i),Sum(i,i+1),..,Sum(i,now))$
   考虑每次加一个值aia_iai​对于前面所有点的贡献。
   记preipre_iprei​表示上一个aia_iai​出现的位置，那么对于那些下标在[1,prei][1,pre_i][1,prei​]之间的点它们的$Sum$和$hisSum$是不变的（因为加上这个值的贡献会扣掉preipre_iprei​那个位置的贡献）
   而对于[prei+1,i−1][pre_i+1,i-1][prei​+1,i−1]的点它们的$Sum$全部会加上$Sum$。
   于是用线段树更新[prei+1,i−1][pre_i+1,i-1][prei​+1,i−1]的和以及历史和最值即可。
   代码：

#include
    
     #define ri register intusing namespace std;typedef long long ll;inline int read(){
    	int ans=0;	bool f=1;	char ch=getchar();	while(!isdigit(ch)){
    if(ch=='-')f^=1;ch=getchar();}	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return f?ans:-ans;}const int N=1e5+5;int n,a[N],pre[N],m;ll ans[N];struct qry{
    int l,id;};vector
     
      q[N];map
      
       mp;namespace SGT{
    	#define lc (p<<1)	#define rc (p<<1|1)	#define mid (T[p].l+T[p].r>>1)	struct Tag{
    ll add,hadd;};	struct Val{
    ll sum,hsum;};	const Tag tag_empty=(Tag){
    0ll,0ll};	struct Node{
    int l,r;ll mx;Val val;Tag tag;}T[N<<2];	inline Val operator+(const Val&a,const Val&b){
    return (Val){
    max(a.sum,b.sum),max(a.hsum,b.hsum)};}	inline Val operator+(const Val&a,const Tag&b){
    return (Val){
    a.sum+b.add,max(a.hsum,a.sum+b.hadd)};}	inline void operator+=(Val&a,const Tag&b){
    a=a+b;}	inline Tag operator+(const Tag&a,const Tag&b){
    return (Tag){
    a.add+b.add,max(a.hadd,a.add+b.hadd)};}	inline void operator+=(Tag&a,const Tag&b){
    a=a+b;}	inline bool operator==(const Tag&a,const Tag&b){
    return a.add==b.add&&a.hadd==b.hadd;}	inline void pushup(int p){
    T[p].val=T[lc].val+T[rc].val;}	inline void pushnow(int p,Tag v){
    T[p].val+=v,T[p].tag+=v;}	inline void pushdown(int p){
    		if(T[p].tag==tag_empty)return;		pushnow(lc,T[p].tag),pushnow(rc,T[p].tag);		T[p].tag=tag_empty;	}	inline void build(int p,int l,int r){
    		T[p].l=l,T[p].r=r,T[p].tag=tag_empty;		if(T[p].l==T[p].r){
    T[p].val=(Val){
    a[l],a[l]};return;}		build(lc,l,mid),build(rc,mid+1,r),pushup(p);	}	inline void update(int p,int ql,int qr,int v){
    		if(ql>qr)return;		if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,(Tag){
    v,v});		pushdown(p);		if(qr<=mid)update(lc,ql,qr,v);		else if(ql>mid)update(rc,ql,qr,v);		else update(lc,ql,qr,v),update(rc,ql,qr,v);		pushup(p);	}	inline ll query(int p,int ql,int qr){
    		if(ql<=T[p].l&&T[p].r<=qr)return T[p].val.hsum;		pushdown(p);		if(qr<=mid)return query(lc,ql,qr);		if(ql>mid)return query(rc,ql,qr);		return max(query(lc,ql,qr),query(rc,ql,qr));	}	#undef lc	#undef rc	#undef mid}int main(){
    	n=read();	for(ri i=1;i<=n;++i)a[i]=read(),pre[i]=mp[a[i]+100001],mp[a[i]+100001]=i;	SGT::build(1,1,n);	m=read();	for(ri l,r,i=1;i<=m;++i)l=read(),r=read(),q[r].push_back((qry){
    l,i});	for(ri i=1;i<=n;++i){
    		SGT::update(1,pre[i]+1,i-1,a[i]);		for(ri j=0;j
      
     
    

---

GSS3

题意简述：单点修改维护最大子段和。

---

思路：直接上线段树即可。

代码：

#include
    
     #define ri register intusing namespace std;const int N=5e4+5;int n,a[N];inline int max(const int&a,const int&b){
    return a>b?a:b;}inline int max(const int&a,const int&b,const int&c){
    return a>b?(a>c?a:c):(b>c?b:c);}namespace SGT{
        #define lc (p<<1)    #define rc (p<<1|1)    #define mid (T[p].l+T[p].r>>1)    struct Val{
            int ls,rs,ms,sum;        inline void init(const int&x){
    ls=rs=ms=sum=x;}    };    inline Val operator+(const Val&a,const Val&b){
    return (Val){
    max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}    struct Node{
    int l,r;Val val;}T[N<<2];    inline void pushup(int p){
    T[p].val=T[lc].val+T[rc].val;}    inline void build(int p,int l,int r){
            T[p].l=l,T[p].r=r;        if(l==r)return T[p].val.init(a[l]);        build(lc,l,mid),build(rc,mid+1,r),pushup(p);    }    inline void update(int p,int k,int v){
        	if(T[p].l==T[p].r)return T[p].val.init(v);    	update(k<=mid?lc:rc,k,v),pushup(p);	}    inline Val query(int p,int ql,int qr){
            if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;        if(qr<=mid)return query(lc,ql,qr);        if(ql>mid)return query(rc,ql,qr);        return query(lc,ql,qr)+query(rc,ql,qr);    }}inline int read(){
        int ans=0;    bool f=1;    char ch=getchar();    while(!isdigit(ch)){
    if(ch=='-')f^=1;ch=getchar();}    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return f?ans:-ans;}int main(){
        n=read();    for(ri i=1;i<=n;++i)a[i]=read();    SGT::build(1,1,n);    for(ri tt=read(),op,x,y;tt;--tt){
        	op=read(),x=read(),y=read();    	if(!op)SGT::update(1,x,y);    	else cout<
     
      <<'\n';	}    return 0;}
     
    

---

GSS4

题意简述：支持区间开方，区间求和。

---

思路：线段树套路题，区间最大值大于$1$递归修改否则直接返回。

每个数被开方log(logn)log(log_n)log(logn​)次之后就没了。

代码：

#include
    
     #define ri register intusing namespace std;typedef long long ll;const int N=1e5+5;int n;ll a[N];inline ll read(){
    	ll ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}namespace SGT{
    	#define lc (p<<1)	#define rc (p<<1|1)	#define mid (T[p].l+T[p].r>>1)	struct Node{
    int l,r;ll mx,sum;}T[N<<2];	inline void pushup(int p){
    		T[p].mx=max(T[lc].mx,T[rc].mx);		T[p].sum=T[lc].sum+T[rc].sum;	}	inline void build(int p,int l,int r){
    		T[p].l=l,T[p].r=r;		if(l==r){
    T[p].sum=T[p].mx=a[l];return;}		build(lc,l,mid),build(rc,mid+1,r),pushup(p);	}	inline void update(int p,int ql,int qr){
    		if(T[p].mx<2)return;		if(T[p].l==T[p].r){
    T[p].sum=T[p].mx=sqrt(T[p].mx);return;}		if(qr<=mid)update(lc,ql,qr);		else if(ql>mid)update(rc,ql,qr);		else update(lc,ql,qr),update(rc,ql,qr);		pushup(p);	}	inline ll query(int p,int ql,int qr){
    		if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;		if(qr<=mid)return query(lc,ql,qr);		if(ql>mid)return query(rc,ql,qr);		return query(lc,ql,qr)+query(rc,ql,qr);	}	#undef lc	#undef rc 	#undef mid}int main(){
    	int cas=0;	while(~scanf("%d",&n)){
    		++cas;		printf("Case #%d:\n",cas);		for(ri i=1;i<=n;++i)a[i]=read();		SGT::build(1,1,n);		for(ri tt=read(),op,l,r;tt;--tt){
    			op=read(),l=read(),r=read();			if(l>r)swap(l,r);			if(!op)SGT::update(1,l,r);			else cout<
     
      <<'\n';		}		puts("");	}	return 0;}
     
    

---

GSS5

题意简述：

求左端点在$[l1,r1]$，右端点在$[l2,r2]$之间的最大子段和。

---

思路：直接分$[l1,r1],[l2,r2]$是否相交讨论一下，之后就是最大子段和问题了。

不相交$\Rightarrow [l1,r1]$中最大后缀和+sumr1+1,l2−1+[l2,r2]+sum_{r1+1,l2-1}+[l2,r2]+sumr1+1,l2−1​+[l2,r2]中最大前缀和。

相交$\Rightarrow$讨论$l1$与$l2$关系，$r1$与$r2$关系更新答案。

代码：

#include
    
     #define lc (p<<1)#define rc (p<<1|1)#define mid (T[p].l+T[p].r>>1)#define N 10005using namespace std;inline int read(){
    	int ans=0,w=1;	char ch=getchar();	while(!isdigit(ch)){
    if(ch=='-')w=-1;ch=getchar();}	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans*w;}int n,m,a[N],T_T;struct Node{
    int l,r,ls,rs,ms,sum;}T[N<<2];inline Node operator+(const Node&a,const Node&b){
    	Node ret;	ret.l=a.l,ret.r=b.r,ret.sum=a.sum+b.sum;	ret.ls=max(a.ls,a.sum+b.ls);	ret.rs=max(b.rs,b.sum+a.rs);	ret.ms=max(max(a.ms,b.ms),a.rs+b.ls);	return ret;}inline void build(int p,int l,int r){
    	T[p].l=l,T[p].r=r;	if(l==r){
    T[p].ls=T[p].rs=T[p].ms=T[p].sum=a[l];return;}	build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc];}inline Node query(int p,int ql,int qr){
    	if(ql>T[p].r||qr
     
      mid)return query(rc,ql,qr);	return query(lc,ql,mid)+query(rc,mid+1,qr);}int main(){
    	T_T=read();	while(T_T--){
    		n=read();		for(int i=1;i<=n;++i)a[i]=read();		build(1,1,n),m=read();		while(m--){
    			int l1=read(),r1=read(),l2=read(),r2=read();			if(r1
      
       r1)ans=max(ans,query(1,l1,r1).rs+query(1,r1,r2).ls-a[r1]);				printf("%d\n",ans);			}		}	}		return 0;}
      
     
    

---

GSS6

题意简述：支持在序列中插入，删除，修改某个数的值，询问最大子段和。

---

思路：把最大子段和的求法搬上$fhq\_treap$即可。

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;inline int read(){
    	int ans=0;	bool f=1;	char ch=getchar();	while(!isdigit(ch)){
    if(ch=='-')f=0;ch=getchar();}	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return f?ans:-ans;}typedef long long ll;typedef pair
     
       pii;const int N=2e5+5;int n;char s[2];inline int max(const ll&a,const ll&b){
    return a>b?a:b;}inline int max(const ll&a,const ll&b,const ll&c){
    return a>b?(a>c?a:c):(b>c?b:c);}namespace Bst{
    	#define lc (son[p][0])	#define rc (son[p][1])	struct Val{
    		ll ls,rs,ms,sum;		inline void init(const ll&x){
    ls=rs=ms=sum=x;}	};	inline Val operator+(const Val&a,const Val&b){
    return (Val){
    max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}	int rt=0,tot=0,son[N][2],siz[N],rd[N],val[N];	Val f[N];	inline int build(int v){
    return val[++tot]=v,rd[tot]=rand(),siz[tot]=1,son[tot][0]=son[tot][1]=0,f[tot].init(v),tot;}	inline void pushup(int p){
    		siz[p]=siz[lc]+1+siz[rc];		f[p].init(val[p]);		if(lc)f[p]=f[lc]+f[p];		if(rc)f[p]=f[p]+f[rc];	}	inline int merge(int a,int b){
    		if(!a||!b)return a+b;		if(rd[a]>rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a;		return son[b][0]=merge(a,son[b][0]),pushup(b),b;	}	inline pii split(int p,int k){
    		if(!p)return pii(0,0);		pii tmp;		if(siz[lc]>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p);		return tmp=split(rc,k-siz[lc]-1),rc=tmp.fi,pushup(p),pii(p,tmp.se);	}	inline void insert(int id,int v){
    		pii x=split(rt,id-1);		rt=merge(merge(x.fi,build(v)),x.se);	}	inline void delet(int id){
    		pii x=split(rt,id-1),y=split(x.se,1);		rt=merge(x.fi,y.se);	}	inline void update(int id,int v){
    		pii x=split(rt,id-1),y=split(x.se,1);		val[y.fi]=v,f[y.fi].init(v);		rt=merge(merge(x.fi,y.fi),y.se);	}	inline void query(int l,int r){
    		pii x=split(rt,l-1),y=split(x.se,r-l+1);		cout<
      
       <<'\n';		rt=merge(x.fi,merge(y.fi,y.se));	}	#undef lc	#undef rc}int main(){
    	srand(time(NULL));	n=read();	for(ri i=1;i<=n;++i)Bst::insert(i,read());	for(ri p,x,tt=read();tt;--tt){
    		scanf("%s",s);		if(s[0]=='I')p=read(),x=read(),Bst::insert(p,x);		if(s[0]=='D')p=read(),Bst::delet(p);		if(s[0]=='R')p=read(),x=read(),Bst::update(p,x);		if(s[0]=='Q')p=read(),x=read(),Bst::query(p,x);	}	return 0;}
      
     
    

---

GSS7

题意简述：支持给一棵树路径赋值，求最大子路径。

---

思路：最大子段和搬上树链剖分即可，注意合并时候的顺序这点小细节就很简单了。

代码：

#include
    
     #define ri register intusing namespace std;const int N=1e5+5,inf=1e9;int n,tot=0,a[N],num[N],dep[N],top[N],fa[N],hson[N],siz[N],pred[N];vector
     
      e[N];void dfs1(int p){
    	siz[p]=1;	for(ri i=0,v;i
      
       siz[hson[p]])hson[p]=v;	}}void dfs2(int p,int tp){
    	top[p]=tp,pred[num[p]=++tot]=p;	if(!hson[p])return;	dfs2(hson[p],tp);	for(ri i=0,v;i
       
        b?a:b;}inline int max(const int&a,const int&b,const int&c){
    return a>b?(a>c?a:c):(b>c?b:c);} namespace SGT{
    	#define lc (p<<1)	#define rc (p<<1|1)	#define mid (T[p].l+T[p].r>>1)	struct Val{
    int ls,rs,ms,sum;};	inline Val operator+(const Val&a,const Val&b){
    return (Val){
    max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}	struct Node{
    		int l,r,cov;Val val;		inline void init(const int&x){
    			val.sum=(r-l+1)*x;			if(x>0)val.ls=val.rs=val.ms=val.sum;			else val.ls=val.rs=val.ms=x;		}	}T[N<<2];	inline void pushup(int p){
    T[p].val=T[lc].val+T[rc].val;}	inline void pushnow(int p,int v){
    T[p].init(v),T[p].cov=v;}	inline void pushdown(int p){
    if(inf^T[p].cov)pushnow(lc,T[p].cov),pushnow(rc,T[p].cov),T[p].cov=inf;}	inline void build(int p,int l,int r){
    		T[p].l=l,T[p].r=r,T[p].cov=inf;		if(l==r)return T[p].init(a[pred[l]]);		build(lc,l,mid),build(rc,mid+1,r),pushup(p);	}	inline void update(int p,int ql,int qr,int v){
    		if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);		pushdown(p);		if(qr<=mid)update(lc,ql,qr,v);		else if(ql>mid)update(rc,ql,qr,v);		else update(lc,ql,qr,v),update(rc,ql,qr,v);		pushup(p); 	}	inline Val query(int p,int ql,int qr){
    		if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;		pushdown(p);		if(qr<=mid)return query(lc,ql,qr);		if(ql>mid)return query(rc,ql,qr);		return query(lc,ql,qr)+query(rc,ql,qr);	}	inline int query(int p,int k){
    		if(T[p].l==T[p].r)return T[p].val.sum;		pushdown(p);		return query(k<=mid?lc:rc,k);	}	#undef lc	#undef rc	#undef mid}inline void update(int x,int y,int v){
    	while(top[x]^top[y]){
    		if(dep[top[x]]
       
      
     
    

---

GSS8

题意简述：支持给一个序列插入，删除，修改某个数的值。

支持查询f(l,r,k)=∑i=lrai(i−l+1)k,0≤k≤10f(l,r,k)=\sum_{i=l}^ra_i(i-l+1)^k,0\le k\le10f(l,r,k)=∑i=lr​ai​(i−l+1)k,0≤k≤10

---

思路：

显然除了查询外的都是fhqtreapfhq_treapfhqt​reap常规操作。

然后只用考虑如何维护答案，由于每次的$k$一样，因此我们每个$treap$节点 对于$k=0\to 10$都维护一个答案。

考虑合并$a,b$的答案。

$a$对于答案的贡献就是本身， 但是$b$不太一样。

本来假设是∑(x+t)k→∑(x+t+siza)k\sum(x+t)^k\rightarrow\sum(x+t+siz_a)^k∑(x+t)k→∑(x+t+siza​)k我们发现sizasiz_asiza​是定值，于是可以将$x+t$看成$y$，我们已经知道y0,y1,...,y10y^0,y^1,...,y^10y0,y1,...,y10了，于是可以二项式展开(y+siza)k=∑i=0kCkiyisizak−i(y+siz_a)^k=\sum_{i=0}^kC_k^iy^isiz_a^{k-i}(y+siza​)k=∑i=0k​Cki​yisizak−i​，我们每次预处理一个siza0→10siz_a^{0\rightarrow10}siza0→10​转移即可。

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;typedef unsigned int ll;typedef pair
     
       pii;inline ll read(){
    	ll ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}const int N=2e5+5;int n;ll pmul[11],C[11][11];inline void init(){
    	for(ri i=0;i<=10;++i){
    		C[i][0]=C[i][i]=1;		for(ri j=1;j
      
       rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a;		return son[b][0]=merge(a,son[b][0]),pushup(b),b;	}	inline pii split(int p,int k){
    		if(!p)return pii(0,0);		pii tmp;		if(val[lc].siz>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p);		return tmp=split(rc,k-val[lc].siz-1),rc=tmp.fi,pushup(p),pii(p,tmp.se);	}	inline void insert(int id,ll v){
    		pii x=split(rt,id-1);		rt=merge(x.fi,merge(build(v),x.se));	}	inline void delet(int id){
    		pii x=split(rt,id-1),y=split(x.se,1);		rt=merge(x.fi,y.se);	}	inline void update(int id,ll v){
    		pii x=split(rt,id-1),y=split(x.se,1);		val[y.fi].init(a[y.fi]=v),rt=merge(x.fi,merge(y.fi,y.se));	}	inline void query(int l,int r,int k){
    		pii x=split(rt,l-1),y=split(x.se,r-l+1);		cout<
       
        <<'\n';		rt=merge(x.fi,merge(y.fi,y.se));	}	#undef lc	#undef rc}char s[5];int main(){
    	srand(time(NULL));	n=read(),init();	for(ri i=1;i<=n;++i)Bst::insert(i,read());	for(ri l,r,x,tt=read();tt;--tt){
    		scanf("%s",s);		if(s[0]=='Q')l=read()+1,r=read()+1,Bst::query(l,r,read());		if(s[0]=='I')x=read()+1,Bst::insert(x,read());		if(s[0]=='D')x=read()+1,Bst::delet(x);		if(s[0]=='R')x=read()+1,Bst::update(x,read());	}	return 0;}