spoj 1716. Can you answer these queries III
spoj 에서 문 제 를 풀 때 누군가가 이 문 제 를 제출 하 는 것 을 보 았 습 니 다. 이름 을 보면 데이터 구조의 문제 가 분명 하 다 는 것 을 알 수 있 습 니 다. 그리고 문 제 는 간단 합 니 다........................................................................................[ l , r ] max(sum[ i]) - min(sum[j ]) i, j 는 [l, r] 구간 내 에 있 지만 i < j 는 욕심 이 적용 되 지 않 을 수도 있 습 니 다. 그리고 걸 렸 습 니 다...........................................................
남 의 코드 를 보고 알았어 요. http://blog.csdn.net/gotoac/article/details/7623857
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50010;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
ll lsum[maxn<<2],msum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];
struct Node{
ll lsum,msum,rsum,sum;
};
void pushup(int rt)
{
int ls=rt<<1,rs=rt<<1|1;
lsum[rt]=max(lsum[ls],sum[ls]+lsum[rs]);
msum[rt]=max(max(msum[ls],msum[rs]),rsum[ls]+lsum[rs]);
rsum[rt]=max(rsum[rs],sum[rs]+rsum[ls]);
sum[rt]=sum[ls]+sum[rs];
}
void build(int l,int r,int rt)
{
if(l==r){
scanf("%lld",&sum[rt]);
lsum[rt]=rsum[rt]=msum[rt]=sum[rt];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,ll val,int l,int r,int rt)
{
if(l==r) {
lsum[rt]=msum[rt]=rsum[rt]=sum[rt]=val;
return;
}
int m=(l+r)>>1;
if(p<=m) update(p,val,lson);
else update(p,val,rson);
pushup(rt);
}
Node query(int L,int R,int l,int r,int rt)
{
Node ret;
if(L<=l&&R>=r){
ret.lsum=lsum[rt],
ret.msum=msum[rt],
ret.rsum=rsum[rt],
ret.sum=sum[rt];
return ret;
}
int m=(l+r)>>1;
if(R<=m) return query(L,R,lson);
if(L>m) return query(L,R,rson);
Node ret1=query(L,R,lson);
Node ret2=query(L,R,rson);
ret.lsum=max(ret1.lsum,ret1.sum+ret2.lsum);
ret.msum=max(max(ret1.msum,ret2.msum),ret1.rsum+ret2.lsum);
ret.rsum=max(ret2.rsum,ret2.sum+ret1.rsum);
ret.sum=ret1.sum+ret2.sum;
return ret;
}
int main()
{
int n,m,l,r,cmd;
while(scanf("%d",&n)==1)
{
build(1,n,1);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&cmd,&l,&r);
if(cmd==0) update(l,r,1,n,1);
else printf("%d
",query(l,r,1,n,1).msum);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.