首页 > 其他分享 >区间最大子区间和——山海经题解

区间最大子区间和——山海经题解

时间:2024-02-18 12:22:17浏览次数:27  
标签:lid 山海经 rs 题解 ls ms 区间 rid id

区间最大子区间和

规定:
ls:区间靠左部分子区间最大和
rs:区间靠右部分子区间最大和
ms:区间子区间最大和
s:区间和

方程与数量关系如图所示,可以用动态规划解决
image

山海经题解

这题是上述方法在线段树中的应用

image

solution

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int lid(int id){
	return id<<1;
} 
int rid(int id){
	return id<<1|1;
}
int a[maxn],n,z,b,r,t,x,y,now,q,k,f,e,ans;
struct tree{
	int lid,rid;//子区间左边界、右边界
    int ms,ls,rs,s;//同上区间最大子区间和的定义
    int l,r,ml,mr;//区间左边界,右边界。最大子区间和左边界,右边界
}m[maxn*4+1];
void push(int id){//对上述一堆东西的更新维护
	m[id].s=m[lid(id)].s+m[rid(id)].s; 
	
	if(m[lid(id)].ls>=m[rid(id)].ls+m[lid(id)].s){m[id].ls=m[lid(id)].ls;m[id].rid=m[lid(id)].rid;}
	else{m[id].ls=m[rid(id)].ls+m[lid(id)].s;m[id].rid=m[rid(id)].rid;}
	
	if(m[rid(id)].rs>=m[rid(id)].s+m[lid(id)].rs){m[id].rs=m[rid(id)].rs;m[id].lid=m[rid(id)].lid;}
	else{m[id].rs=m[rid(id)].s+m[lid(id)].rs;m[id].lid=m[lid(id)].lid;}
	
	if(m[lid(id)].ms>=m[rid(id)].ms){m[id].ms=m[lid(id)].ms;m[id].ml=m[lid(id)].ml;m[id].mr=m[lid(id)].mr;}
	else{m[id].ms=m[rid(id)].ms;m[id].ml=m[rid(id)].ml;m[id].mr=m[rid(id)].mr;}
	
	if(m[id].ms>m[lid(id)].rs+m[rid(id)].ls) return;
	if(m[id].ms<m[lid(id)].rs+m[rid(id)].ls){m[id].ms=m[lid(id)].rs+m[rid(id)].ls;m[id].ml=m[lid(id)].lid;m[id].mr=m[rid(id)].rid;return;}
	
	if(m[id].ml<m[lid(id)].lid) return;
	if(m[id].ml>m[lid(id)].lid){m[id].ml=m[lid(id)].lid;m[id].mr=m[rid(id)].rid;return;}
	
	m[id].mr=min(m[id].mr,m[rid(id)].rid);
}
void build(int id,int l,int r){//建树
	m[id].l=l;
	m[id].r=r;
	if(l==r){
		m[id].ml=m[id].mr=m[id].lid=m[id].rid=l;
		m[id].ls=m[id].rs=m[id].s=m[id].ms=a[l];
		return; 
	}
	int mid=(l+r)>>1;
	build(lid(id),l,mid);
	build(rid(id),mid+1,r);
	push(id);
} 
tree find(int id,int s,int tt){
	int l=m[id].l,r=m[id].r;
	if(s<=l&&r<=tt) return m[id];
	int mid=(l+r)>>1;
	tree x, y, w;
    if(tt<=mid) return find(lid(id),s,tt);
    if(s>mid) return find(rid(id),s,tt);
   
    x=find(lid(id),s,tt);
    y=find(rid(id),s,tt);
    if(x.ls>=x.s+y.ls){w.ls=x.ls;w.rid=x.rid;w.l=x.l;}
    else{w.ls=x.s+y.ls;w.rid=y.rid;w.l=x.l;}
        
    if(y.rs>=x.rs+y.s){w.rs=y.rs;w.lid=y.lid;w.r=y.r;}
    else{w.rs=x.rs+y.s;w.lid=x.lid;w.r=y.r;}
        
    if(x.ms>=y.ms){w.ms=x.ms;w.ml=x.ml;w.mr=x.mr;}
    else{w.ms=y.ms;w.ml=y.ml;w.mr=y.mr;}
		
	if(w.ms>x.rs+y.ls)return w;
    if(w.ms<x.rs+y.ls){w.ms=x.rs+y.ls;w.ml=x.lid;w.mr=y.rid;return w;}
        
    if(w.ml<x.lid) return w;
    if(w.ml>x.lid){w.ml=x.lid;w.mr=y.rid;return w;}
        
	w.mr=min(w.mr,y.rid);
	
    return w;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
//		modify (1,i,a[i]); 
	} 
	if(n!=0) build(1,1,n); 
	for(int i=1;i<=q;i++){ 
		scanf("%d%d",&f,&e);
		tree mm=find(1,f,e);
		printf("%d %d %d\n",mm.ml,mm.mr,mm.ms);
	}
    return 0;
}

标签:lid,山海经,rs,题解,ls,ms,区间,rid,id
From: https://www.cnblogs.com/dfxjlsx/p/18019069

相关文章

  • 寒假训练——vj题解
    B-BM算日期M是一位数学高手,今天他迎来了Kita的挑战。Kita想让BM算出这几年内有多少个闰年。BM觉得这问题实在太简单了,于是Kita加大了难度。他先给出第一个年份,再给出一个整数。Kita要BM进行加法运算后得到第二个年份,然后算出这两个年份之间有多少个闰年。然......
  • ABC341G 题解
    blog。妈的,被trick干爆了。\(\textbf{Trick}\):将所有\(N_i=(i,\sum\limits_{j=1}^ia_j)\)视作一点,则区间\([l,r]\)的平均值为\((N_{l-1},N_r)\)的斜率。\(\textbf{Prove}\):由\(\text{slope}=\dfrac{y_2-y_1}{x_2-x_1}\)易证。根据这个trick,\(k\)的答案即为\(k......
  • luogu2119题解
    本题考察对于枚举的方式对程序的性能的提升。有一个小的优化,\(n\)的范围比\(m\)的范围小,由于我们不关心顺序,我们既可以在值域上枚举也可以在物品上枚举,这里为了优化在值域上枚举更好。最简单的枚举是直接枚举\(a,b,c,d\)或是枚举其中三个数枚举另一个,时间复杂度为\(O(n^4)......
  • P10171题解
    P10171[DTCPC2024]取模题目传送门题解不会多项式导致的,赛后秒过。一个显然的结论:如果原序列有相等的数答案为\(0\),其次大于\(4\times10^5\)的\(k\)均符合要求。问题在于小于\(4\times10^5\)的答案。赛时想了很多奇妙的算法,诸如根号分治、线段树维护余数等等。其......
  • CF1472C Long Jumps题解
    【题目分析】本题有两个方法,方法一:每一个位置可得的分分别求出,打擂找出最大(可得部分分)方法二:从后往前求可得的分数,以避免一些不必要的重复。【设计程序】方法一:#include<bits/stdc++.h>#include<iostream>#include<stdio.h>#include<cstdio>#include<queue>usingnames......
  • CF1196B Odd Sum Segments题解
    【问题分析】本题考了奇数。由此想到以下定律:奇数+偶数=奇数;奇数+奇数=偶数;偶数+偶数=偶数;所以偶数可以忽略不计,只有奇数可以对结果产生影响,所以我们只要注意奇数即可。经过思考可得奇数的个数至少为$k$个且比$k$多的个数为偶数,此时多出的奇数可组成偶数,对结果不产生......
  • P2036 [COCI2008-2009#2] PERKET题解
    【问题分析】分析题目可得此问题为01背包问题因此题数据较小所以可用枚举每一样物品选或不选的方法来写【设计程序】#include<bits/stdc++.h>#include<iostream>#include<stdio.h>#include<cstdio>#include<queue>usingnamespacestd;constintN=10+5;struct......
  • P1162 填涂颜色题解
    【问题分析】分析题目可得此问题为连通块问题因此题枚举被包围的‘0’较难所以可用枚举每一个不被包围的‘0’【设计程序】#include<bits/stdc++.h>#include<iostream>#include<stdio.h>#include<cstdio>#include<queue>usingnamespacestd;constintN=30+5;i......
  • P2249 【深基13.例1】查找题解
    【问题分析】本题有n个数(n>10^6)n很大,查找m个数(m≤10^5),数最大为(10^9)方法一:用顺序查找的话时间复杂度为:O(n*m)会超时,只能得部分分;方法二:用桶排时间复杂度为O(n)+O(m),但是因为数最大为(109)空间复杂度为:O(109);方法三:用二分查找,时间复杂度为:O(m*logn),空间复杂度为O(n)。综合以......
  • P8248 简单数列 题解
    首先,圈重点:$1\len\le500$所有元素在$1\sim4$之间任意连续的连续子串不相同只要输出一种答案即可于是我们可以得到的是:由第一点和第二点可以看出此题可以写搜索解决。由第三点我们可以得到一种剪枝方式,就是如果目前数字放入后会产生相同的连续的连续子串。由第四点......