首页 > 其他分享 >[COGS 755]山海经：线段树

[COGS 755]山海经：线段树

时间：2024-02-20 17:48:20浏览次数：27  
标签：755 COGS ans1 线段 sum2 int ans lright ans2


这是一道美妙的线段树板子，能够有效地提升我们的读题，理解，思考和代码能力；
综上，这是一道大模拟
显然，对于这道题的数据范围，直接暴力是行不通的，只能拿30分：

30分暴力 
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int inf=0x7fffffff;
struct tree{
	int l,r,maxn,minn,sum,lazy;
}t[N<<2];
int a[N],n,m;
string ask;
int x,y;
void update(int x){
	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
	t[x].maxn=max(t[x<<1].maxn,t[x<<1|1].maxn);
	t[x].minn=min(t[x<<1].minn,t[x<<1|1].minn);
}
void build(int k,int l,int r){
	t[k].l=l;
	t[k].r=r;
	if(l==r){
		t[k].maxn=t[k].sum=t[k].minn=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	update(k);
}
void add(int k,int p,int val){
	int l=t[k].l,r=t[k].r;
	if(l==r){
		t[k].sum+=val;
		t[k].maxn=val;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)add(k<<1,p,val);
	else add(k<<1|1,p,val);
	update(k);
}
int getsum(int k,int l,int r){
	int kl=t[k].l,kr=t[k].r;
	if(l<=kl&&kr<=r){
		return t[k].sum;
	}
	int mid=(kl+kr)>>1;
	int res=0;
	if(l<=mid)res+=getsum(k<<1,l,r);
	if(r>mid)res+=getsum(k<<1|1,l,r);
	return res;
}
int getmax(int k,int l,int r){
	int kl=t[k].l,kr=t[k].r;
	if(l<=kl&&kr<=r){
		return t[k].maxn;
	}
	int mid=(kl+kr)>>1;
	int res=-inf;
	if(l<=mid)res=max(res,getmax(k<<1,l,r));
	if(r>mid)res=max(res,getmax(k<<1|1,l,r));
	return res;
}
int getmin(int k,int l,int r){
	int kl=t[k].l,kr=t[k].r;
	if(l<=kl&&kr<=r){
		return t[k].minn;
	}
	int mid=(kl+kr)>>1;
	int res=inf;
	if(l<=mid)res=min(res,getmin(k<<1,l,r));
	if(r>mid)res=min(res,getmin(k<<1|1,l,r));
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		cin>>x>>y;
		int ans=-inf,ii,jj;
		for(int i=x;i<=y;i++){
			for(int j=i;j<=y;j++){
				if(getsum(1,i,j)>ans){
					ans=getsum(1,i,j);
					ii=i;jj=j;
				}
			}
		}
		cout<<ii<<" "<<jj<<" "<<ans<<endl;
	}
	return 0;
}

所以，我们就需要去维护一下最大子区间。
对于一个子区间，它与原区间的关系有以下三种：

left---l 子区间1 l------mid----------------right
left--------------------mid--l 子区间2 l----right
left----------l 子区间3 mid l----------------right

前两种情况简单，可以直接由子区间转移而来；
而对于第三种，我们可以将其从 mid 处分割成两个区间，将其转化为左子区间的最大后缀和 + 右子区间的最大前缀和；
所以我们还要多维护两个变量。
并且，由于要输出路径，所以我们还要维护四个变量，即：
取到左子区间的最大后缀和时的左节点编号；
取到右子区间的最大前缀和时的右节点编号；
取到最大值时的两端节点编号。

总计十个变量：

struct tree{
	int l,r；//维护区间的左右端点
	int sum;//区间的满意值之和
	int lmax,rleft;//最大左子区间后缀和及取到时左节点编号
	int rmax,lright;//最大右子区间前缀和及取到时右节点编号
	int maxn,mleft,mright;//最大子区间的满意值之和，左端点，右端点
}t[N<<2];
初始化 
void build(int k,int l,int r){
	t[k].l=l;
	t[k].r=r;
	if(l==r){
		t[k]={l,r,a[l],a[l],l,a[l],l,a[l],l,l};
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
Pushup 函数 
	void pushup(int k){
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;//更改区间和
	
	int sum1=0,sum2=0,sum3=0;//临时变量，用于比较
	
	sum1=t[k<<1].lmax;//左儿子
	sum2=t[k<<1].sum+t[k<<1|1].lmax;//右儿子
	t[k].lmax=max(sum1,sum2);
	if(sum1>=sum2)t[k].lright=t[k<<1].lright;//大于等于，满足字典序输出
	else t[k].lright=t[k<<1|1].lright;
	
	sum1=t[k<<1|1].sum+t[k<<1].rmax;//左儿子
	sum2=t[k<<1|1].rmax;//右儿子
	t[k].rmax=max(sum1,sum2);
	if(sum1>=sum2)t[k].rleft=t[k<<1].rleft;//大于等于，满足字典序输出
	else t[k].rleft=t[k<<1|1].rleft;
	
	sum1=t[k<<1].maxn;//左儿子
	sum2=t[k<<1].rmax+t[k<<1|1].lmax;//横跨左右区间
	sum3=t[k<<1|1].maxn;//右儿子
	
	int ans=max({sum1,sum2,sum3});
	t[k].maxn=ans;
	
	if(sum1==ans){
		t[k].mleft=t[k<<1].mleft;
		t[k].mright=t[k<<1].mright;
	}
	else if(sum2==ans){
		t[k].mleft=t[k<<1].rleft;
		t[k].mright=t[k<<1|1].lright;
	}
	else{
		t[k].mleft=t[k<<1|1].mleft;
		t[k].mright=t[k<<1|1].mright;
	}
}
Query函数 
tree query(int l,int r,int k){//思想与方式与上面基本一致，不再赘述
	if(t[k].l>=l&&t[k].r<=r)return t[k];
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=r)return query(l,r,k<<1);
	else if(l>mid)return query(l,r,k<<1|1);
	else{
		tree ans1,ans2,ans;
		ans1=query(l,mid,k<<1);
		ans2=query(mid+1,r,k<<1|1);
		
		ans.l=ans1.l;
		ans.r=ans2.r;
		ans.sum=ans1.sum+ans2.sum;
		
		int sum1=0,sum2=0,sum3=0;
		
		sum1=ans1.lmax;
		sum2=ans1.sum+ans2.lmax;
		ans.lmax=max(sum1,sum2);
		if(sum1>=sum2)ans.lright=ans1.lright;
		else ans.lright=ans2.lright;
		
		sum1=ans2.sum+ans1.rmax;
		sum2=ans2.rmax;
		ans.rmax=max(sum1,sum2);
		if(sum1>=sum2)ans.rleft=ans1.rleft;
		else ans.rleft=ans2.rleft;
		
		sum1=ans1.maxn;
		sum2=ans2.lmax+ans1.rmax;
		sum3=ans2.maxn;
		
		int fmax=max({sum1,sum2,sum3});
		ans.maxn=fmax;
		
		if(fmax==sum1){
			ans.mleft=ans1.mleft;
			ans.mright=ans1.mright;
		}
		else if(fmax==sum2){
			ans.mleft=ans1.rleft;
			ans.mright=ans2.lright;
		}
		else{
			ans.mleft=ans2.mleft;
			ans.mright=ans2.mright;
		}
		return ans;
	}
}
完整代码 
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int inf=0x7fffffff;
struct tree{
	int l,r,sum;
	int lmax,rleft;
	int rmax,lright;
	int maxn,mleft,mright;
}t[N<<2];
int a[N],n,m;
int x,y;
void pushup(int k){
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
	
	int sum1=0,sum2=0,sum3=0;
	
	sum1=t[k<<1].lmax;
	sum2=t[k<<1].sum+t[k<<1|1].lmax;
	t[k].lmax=max(sum1,sum2);
	if(sum1>=sum2)t[k].lright=t[k<<1].lright;
	else t[k].lright=t[k<<1|1].lright;
	
	sum1=t[k<<1|1].sum+t[k<<1].rmax;
	sum2=t[k<<1|1].rmax;
	t[k].rmax=max(sum1,sum2);
	if(sum1>=sum2)t[k].rleft=t[k<<1].rleft;
	else t[k].rleft=t[k<<1|1].rleft;
	
	sum1=t[k<<1].maxn;
	sum2=t[k<<1].rmax+t[k<<1|1].lmax;
	sum3=t[k<<1|1].maxn;
	
	int ans=max({sum1,sum2,sum3});
	t[k].maxn=ans;
	
	if(sum1==ans){
		t[k].mleft=t[k<<1].mleft;
		t[k].mright=t[k<<1].mright;
	}
	else if(sum2==ans){
		t[k].mleft=t[k<<1].rleft;
		t[k].mright=t[k<<1|1].lright;
	}
	else{
		t[k].mleft=t[k<<1|1].mleft;
		t[k].mright=t[k<<1|1].mright;
	}
}
void build(int k,int l,int r){
	t[k].l=l;
	t[k].r=r;
	if(l==r){
		t[k]={l,r,a[l],a[l],l,a[l],l,a[l],l,l};
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
tree query(int l,int r,int k){
	if(t[k].l>=l&&t[k].r<=r)return t[k];
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=r)return query(l,r,k<<1);
	else if(l>mid)return query(l,r,k<<1|1);
	else{
		tree ans1,ans2,ans;
		ans1=query(l,mid,k<<1);
		ans2=query(mid+1,r,k<<1|1);
		
		ans.l=ans1.l;
		ans.r=ans2.r;
		ans.sum=ans1.sum+ans2.sum;
		
		int sum1=0,sum2=0,sum3=0;
		
		sum1=ans1.lmax;
		sum2=ans1.sum+ans2.lmax;
		ans.lmax=max(sum1,sum2);
		if(sum1>=sum2)ans.lright=ans1.lright;
		else ans.lright=ans2.lright;
		
		sum1=ans2.sum+ans1.rmax;
		sum2=ans2.rmax;
		ans.rmax=max(sum1,sum2);
		if(sum1>=sum2)ans.rleft=ans1.rleft;
		else ans.rleft=ans2.rleft;
		
		sum1=ans1.maxn;
		sum2=ans2.lmax+ans1.rmax;
		sum3=ans2.maxn;
		
		int fmax=max({sum1,sum2,sum3});
		ans.maxn=fmax;
		
		if(fmax==sum1){
			ans.mleft=ans1.mleft;
			ans.mright=ans1.mright;
		}
		else if(fmax==sum2){
			ans.mleft=ans1.rleft;
			ans.mright=ans2.lright;
		}
		else{
			ans.mleft=ans2.mleft;
			ans.mright=ans2.mright;
		}
		return ans;
	}
}
int main(){
	cin>>n>>m;
	tree ans;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		cin>>x>>y;
		ans=query(x,y,1);
		cout<<ans.mleft<<" "<<ans.mright<<" "<<ans.maxn<<endl;
	}
	return 0;
}

运行结果：
image

标签：755,COGS,ans1,线段,sum2,int,ans,lright,ans2
From： https://www.cnblogs.com/LBTL/p/18023647

相关文章

  • 三哼经（山海经） 线段树
    关于这道题，网上的题解基本都是什么求最大连续子段和，还有什么最大前缀、最大后缀，看了半天也是实在看不明白，便找了个题解，开始给题解写注释（众所周知题解里基本没有注释doge），写了一下午加一晚上，倒是差不多明白了，又肝了0.3坤天终于把三哼经拿下了。题目巴拉巴拉说了一堆没用的的话，让......
  • 线段树-山海经 题解
    《最痛苦的一集》从开始的找维护变量到依据i比较依据y比较最后发现问题出在没初始化(如果不将答案赋值为极小值那么它最小值就是0因此wa了无数遍下面是思路首先要维护的变量有：\(区间的左右边界\,l,\,r\)\(区间的答案\,ans\)\(含左端点最大值\,lans\,和含右端点最......
  • 线段树
    线段树算是树状数组的进阶版了，树状数组能做的，线段树也肯定能做，它做不了的，线段树也能做。但确实线段树的代码量也很让人挠头，基本原理不再解释。先看一下基础的模板吧单点修改和区间查询点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=300000;intn......
  • "山海经“ 讲解----线段树
    ”山海经“--线段树讲解1、题面：http://cogs.pro/cogs/problem/problem.php?pid=7752、题目大意及分析：i：大概就是说给了你一段[1,n]的区间，并给了每个区间的权值，下面会有m个问题，每个问题给你一段[1,n]的子区间[i,j]，问你在这段区间上的任意一端子区间和最大是多少，并且要求输出这......
  • 线段树的各种板板~(*^▽^*)
    $\color{purple}{板板}$#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineinf0x3f#defineINF0x3f3f3f3f#definemst(a,b)memset(a,b,sizeof(a))#defineElaina0#definelid(id<<1)#definerid(id<<1|1)//即ridco......
  • 线段树模板
    开局宏定义：#include<bits/stdc++.h>#defineintlonglong#definelson(now<<1)//现结点的左孩子#definerson(now<<1|1)//右孩子usingnamespacestd;结构体定义：structNode{intl,r;//表示左右区间intmax,sum;//其他数据域}tree[N<<2]//=N*......
  • 线段树（板子）
    线段树单点修改，单点，区间查询区间修改，单点，区间查询单点修改普通线段树code#definels(rt<<1)#definers(rt<<1|1)#definellllonglongconstintN=1000001;intn,m;inta[N];structT{ intl,r,data;}tr[N<<2];voidpushup(intrt){ tr[rt].da......
  • 线段树-基础模版
    线段树模版一埋头扎进线段树一上午感觉很神奇几个函数就能把它完整的复现下来这里有几张基础概念的图对着代码来想还是很好理解的最后是整理了能够处理总和最大值和最小值的线段树模版code：$\LARGE\color{purple}{代码在这里}$#include<bits/stdc++.h>usingnames......
  • 树状数组及线段树详解
    本文章是作者调了3个多小时后，感触颇深，历经1个多小时写出来的，不喜勿喷相关内容可参考模板总结中的树状数组及线段树；进入正题树状数组所谓树状数组，即像树的数组，一般应用于求多次前缀和以及区间前缀和的问题中；其根据节点编号的二进制数的末尾0的个数划分层次，每个节点的管辖......
  • 线段树进阶
    线段树进阶动态开点定义动态存储数据的线段树，可以优化空间复杂度实现为了避免\(N<<1\)，不再使用完全二叉树存储，而记录左右儿子\(ls,rs\)此外需要\(tot\)记录已经开了多少点在递归时要记录点的左右区间，确保开点时能知道区间大小voidmodify(int&p,intL,intR,intl,i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99