Codevs 3981 动态最大子段和
程序员文章站
2022-03-20 16:55:10
[TOC] 题目 "戳" 思路 求$bss$的板子 详细讲解 $\text{To be continued}$ $Code$ cpp include include include include include define MAXN 200000 using namespace std; lon ......
目录
题目
思路
求$bss$的板子
详细讲解
$\text{to be continued}$
$code$
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdio> #define maxn 200000 using namespace std; long long n,m; struct node{ int l,r; long long w,lmax,rmax,maxx; void clear(){ lmax=rmax=maxx=w=-0x7fffffff; } }tree[maxn*4]; inline long long read(){ long long x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } void build(int l,int r,int now){ tree[now].l=l,tree[now].r=r; if(tree[now].l==tree[now].r){ tree[now].w=read(); tree[now].lmax=tree[now].rmax=tree[now].maxx=tree[now].w; return; } int mid=(tree[now].l+tree[now].r)>>1; build(l,mid,now<<1),build(mid+1,r,now<<1|1); tree[now].w=tree[now<<1].w+tree[now<<1|1].w; tree[now].maxx=max(tree[now<<1].maxx,tree[now<<1|1].maxx); tree[now].maxx=max(tree[now].maxx,tree[now<<1].rmax+tree[now<<1|1].lmax); tree[now].lmax=max(tree[now<<1].lmax,tree[now<<1].w+tree[now<<1|1].lmax); tree[now].rmax=max(tree[now<<1|1].rmax,tree[now<<1|1].w+tree[now<<1].rmax); } node ask_range(long long x,long long y,int now){ if(tree[now].l>=x&&tree[now].r<=y){ return tree[now]; } int mid=(tree[now].l+tree[now].r)>>1; if(y<=mid) return ask_range(x,y,now<<1); if(x>mid) return ask_range(x,y,now<<1|1); node lans,rans,ans; lans.clear(),rans.clear(),ans.clear(); lans=ask_range(x,y,now<<1); rans=ask_range(x,y,now<<1|1); ans.w=lans.w+rans.w; ans.maxx=max(lans.maxx,rans.maxx); ans.maxx=max(ans.maxx,lans.rmax+rans.lmax); ans.lmax=max(lans.lmax,lans.w+rans.lmax); ans.rmax=max(rans.rmax,rans.w+lans.rmax); return ans; } int main(){ n=read(); build(1,n,1); m=read(); long long ans,x,y; while(m--){ x=read(),y=read(); ans=ask_range(x,y,1).maxx; printf("%lld\n",ans); } return 0; }