2020-2021:teams:legal_string:jxm2001:猫树
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:猫树 [2021/08/29 11:24] jxm2001 [算法实现] |
2020-2021:teams:legal_string:jxm2001:猫树 [2021/08/29 15:58] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 29: | 行 29: | ||
| 修改也可以考虑树状数组维护前缀和，不过这样貌似不如直接用线段树维护。 | 修改也可以考虑树状数组维护前缀和，不过这样貌似不如直接用线段树维护。 | ||
| - | ===== 算法模板 ===== | + | ===== 算法例题 ===== |
| - | ==== 区间最大子串和 ==== | + | ==== 例题一 ==== |
| [[https://www.luogu.com.cn/problem/SP1043|SPOJ1043]] | [[https://www.luogu.com.cn/problem/SP1043|SPOJ1043]] | ||
| + | |||
| + | 求区间最大子段和。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 84: | 行 86: | ||
| enter(Tree::query(l,r)); | enter(Tree::query(l,r)); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 例题二 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/SP2916|SPOJ2916]] | ||
| + | |||
| + | 求左端点位于 $[l_1,r_1]$，右端点位于 $[l_2,r_2]$ 的最大区间和。数据保证 $l_1\le l_2,r_1\le r_2$。 | ||
| + | |||
| + | 对于 $l_2\lt r_1$ 的情况显然很容易求得，否则分类讨论一下即可。需要维护区间和，区间最大子段和，区间最大前缀，最大后缀。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e4+5,MAXD=20; | ||
| + | namespace Tree{ | ||
| + | int n,a[MAXN<<1],lg2[MAXN<<1]; | ||
| + | struct Node{ | ||
| + | int sum,max_pre,max_suf,max_sum; | ||
| + | Node(int a=0){ | ||
| + | sum=max_pre=max_suf=max_sum=a; | ||
| + | } | ||
| + | Node operator + (const Node &b)const{ | ||
| + | Node c; | ||
| + | c.sum=sum+b.sum; | ||
| + | c.max_pre=max(max_pre,sum+b.max_pre); | ||
| + | c.max_suf=max(max_suf+b.sum,b.max_suf); | ||
| + | c.max_sum=max({max_sum,b.max_sum,max_suf+b.max_pre}); | ||
| + | return c; | ||
| + | } | ||
| + | }s[MAXD][MAXN<<1]; | ||
| + | void build(int L,int R,int d){ | ||
| + | if(L==R)return; | ||
| + | int M=L+R>>1; | ||
| + | s[d][M]=Node(a[M]); | ||
| + | for(int i=M-1;i>=L;i--) | ||
| + | s[d][i]=Node(a[i])+s[d][i+1]; | ||
| + | s[d][M+1]=Node(a[M+1]); | ||
| + | for(int i=M+2;i<=R;i++) | ||
| + | s[d][i]=s[d][i-1]+Node(a[i]); | ||
| + | build(L,M,d+1); | ||
| + | build(M+1,R,d+1); | ||
| + | } | ||
| + | void init(int _n){ | ||
| + | n=1; | ||
| + | while(n<_n)n<<=1; | ||
| + | _rep(i,2,n)lg2[i]=lg2[i>>1]+1; | ||
| + | build(1,n,0); | ||
| + | } | ||
| + | Node query(int L,int R){ | ||
| + | if(L==R)return Node(a[L]); | ||
| + | int d=lg2[n]-lg2[(L-1)^(R-1)]-1; | ||
| + | return s[d][L]+s[d][R]; | ||
| + | } | ||
| + | } | ||
| + | void solve(){ | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n) | ||
| + | Tree::a[i]=read_int(); | ||
| + | Tree::init(n); | ||
| + | int q=read_int(); | ||
| + | while(q--){ | ||
| + | int l1=read_int(),r1=read_int(),l2=read_int(),r2=read_int(); | ||
| + | if(r1<l2){ | ||
| + | int ans=Tree::query(l1,r1).max_suf+Tree::query(l2,r2).max_pre; | ||
| + | if(r1+1<=l2-1) | ||
| + | ans+=Tree::query(r1+1,l2-1).sum; | ||
| + | enter(ans); | ||
| + | } | ||
| + | else{ | ||
| + | int ans=Tree::query(l2,r1).max_sum; | ||
| + | if(r1!=r2) | ||
| + | ans=max(ans,Tree::query(l1,r1).max_suf+Tree::query(r1+1,r2).max_pre); | ||
| + | if(l1!=l2) | ||
| + | ans=max(ans,Tree::query(l1,l2-1).max_suf+Tree::query(l2,r2).max_pre); | ||
| + | enter(ans); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int main(){ | ||
| + | int T=read_int(); | ||
| + | while(T--) | ||
| + | solve(); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/猫树.1630207463.txt.gz · 最后更改: 2021/08/29 11:24 由 jxm2001
