| 记录编号 |
452618 |
评测结果 |
AAAAAAAA |
| 题目名称 |
山海经 |
最终得分 |
100 |
| 用户昵称 |
 BaDBoY |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.788 s |
| 提交时间 |
2017-09-19 21:32:44 |
内存使用 |
16.63 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x7fffffff
int n,m;
struct node {
int sum,l,r,mid;
int l1,r1,l2,r2,l3,r3;
int ll,rr;
node() {
sum=l=r=mid=-inf;
}
} tree[4*100001],null;
int a[100005];
void pushup(int x) {
tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
if(tree[x<<1].l>=tree[x].l) {
tree[x].l=tree[x<<1].l;
tree[x].l1=tree[x<<1].l1;
tree[x].r1=tree[x<<1].r1;
}
if(tree[x<<1].sum>tree[x].l) {
tree[x].l=tree[x<<1].sum;
tree[x].l1=tree[x<<1].ll;
tree[x].r1=tree[x<<1].rr;
}
if(tree[x<<1].sum+tree[x<<1|1].l>tree[x].l) {
tree[x].l=tree[x<<1].sum+tree[x<<1|1].l;
tree[x].l1=tree[x<<1].ll;
tree[x].r1=tree[(x<<1|1)].r1;
}
if(tree[x<<1|1].sum+tree[x<<1].r>=tree[x].r) {
tree[x].r=tree[x<<1|1].sum+tree[x<<1].r;
tree[x].l2=tree[x<<1].l2;
tree[x].r2=tree[x<<1|1].rr;
}
if(tree[x<<1|1].sum>tree[x].r) {
tree[x].r=tree[x<<1|1].sum;
tree[x].l2=tree[x<<1|1].ll;
tree[x].r2=tree[x<<1|1].rr;
}
if(tree[x<<1|1].r>tree[x].r) {
tree[x].r=tree[x<<1|1].r;
tree[x].l2=tree[(x<<1|1)].l2;
tree[x].r2=tree[x<<1|1].r2;
}
if(tree[x<<1].mid>=tree[x].mid) {
tree[x].mid=tree[x<<1].mid;
tree[x].l3=tree[x<<1].l3;
tree[x].r3=tree[x<<1].r3;
}
//if(tree[x<<1|1].l<0) {
if(tree[x<<1].r>tree[x].mid) {
tree[x].mid=tree[x<<1].r;
tree[x].l3=tree[x<<1].l2;
tree[x].r3=tree[x<<1].r2;
}
//}
if(tree[x<<1|1].l+tree[x<<1].r>tree[x].mid) {
tree[x].mid=tree[x<<1|1].l+tree[x<<1].r;
tree[x].l3=tree[x<<1].l2;
tree[x].r3=tree[x<<1|1].r1;
}
//if(tree[x<<1].r<0) {
if(tree[x<<1|1].l>tree[x].mid) {
tree[x].mid=tree[x<<1|1].l;
tree[x].l3=tree[x<<1|1].l1;
tree[x].r3=tree[x<<1|1].r1;
}
//}
if(tree[x<<1|1].mid>tree[x].mid) {
tree[x].mid=tree[x<<1|1].mid;
tree[x].l3=tree[x<<1|1].l3;
tree[x].r3=tree[x<<1|1].r3;
}
}
void build(int i,int le,int ri) {
if(le==ri) {
tree[i].sum=tree[i].l=tree[i].r=tree[i].mid=a[le];
tree[i].ll=tree[i].rr=le;
tree[i].l1=tree[i].r1=tree[i].l2=tree[i].r2=tree[i].l3=tree[i].r3=le;
return ;
}
tree[i].ll=le;
tree[i].rr=ri;
int mid=le+ri>>1;
build(i<<1,le,mid);
build(i<<1|1,mid+1,ri);
pushup(i);
}
node query(int i,int L,int R,int l,int r) {
if(l>r) {
return null;
}
if(l<=L&&R<=r) {
return tree[i];
}
int mid=L+R>>1;
node ans1,ans2;
if(l<=mid) {
ans1=query(i<<1,L,mid,l,r);
}
if(r>mid) {
ans2=query(i<<1|1,mid+1,R,l,r);
}
node ans;
if(ans1.sum<=-2147483645&&ans2.sum<=-2147483645) {
return ans1;
}
if(ans1.sum<=-2147483645) {
return ans2;
}
if(ans2.sum<=-2147483645) {
return ans1;
}
ans.sum=ans1.sum+ans2.sum;
if(ans1.l>=ans.l) {
ans.l=ans1.l;
ans.l1=ans1.l1;
ans.r1=ans1.r1;
}
if(ans1.sum>ans.l) {
ans.l=ans1.sum;
ans.l1=ans1.ll;
ans.r1=ans1.rr;
}
if(ans1.sum+ans2.l>ans.l) {
ans.l=ans1.sum+ans2.l;
ans.l1=ans1.ll;
ans.r1=ans2.r1;
}
if(ans2.sum+ans1.r>=ans.r) {
ans.r=ans2.sum+ans1.r;
ans.l2=ans1.l2;
ans.r2=ans2.rr;
}
if(ans2.sum>ans.r) {
ans.r=ans2.sum;
ans.l2=ans2.ll;
ans.r2=ans2.rr;
}
if(ans2.r>ans.r) {
ans.r=ans2.r;
ans.l2=ans2.l2;
ans.r2=ans2.r2;
}
if(ans1.mid>=ans.mid) {
ans.mid=ans1.mid;
ans.l3=ans1.l3;
ans.r3=ans1.r3;
}
//if(ans2.l<0) {
if(ans1.r>ans.mid) {
ans.mid=ans1.r;
ans.l3=ans1.l2;
ans.r3=ans1.r2;
}
//}
if(ans2.l+ans1.r>ans.mid) {
ans.mid=ans2.l+ans1.r;
ans.l3=ans1.l2;
ans.r3=ans2.r1;
}
//if(ans1.r<0) {
if(ans2.l>ans.mid) {
ans.mid=ans2.l;
ans.l3=ans2.l1;
ans.r3=ans2.r1;
}
//}
if(ans2.mid>ans.mid) {
ans.mid=ans2.mid;
ans.l3=ans2.l3;
ans.r3=ans2.r3;
}
ans.ll=min(ans1.ll,ans2.ll);
ans.rr=max(ans1.rr,ans2.rr);
return ans;
}
int Main() {
freopen("hill.in","r",stdin);
freopen("hill.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
build(1,1,n);
for(int i=1,a,b; i<=m; i++) {
scanf("%d%d",&a,&b);
node ans=query(1,1,n,a,b);
if(ans.l>=ans.sum&&ans.l>=ans.r&&ans.l>=ans.mid) {
printf("%d %d %d\n",ans.l1,ans.r1,ans.l);
continue;
}
if(ans.sum>=ans.l&&ans.sum>=ans.r&&ans.sum>=ans.mid) {
printf("%d %d %d\n",ans.ll,ans.rr,ans.sum);
continue;
}
if(ans.mid>=ans.sum&&ans.mid>=ans.l&&ans.mid>=ans.r) {
printf("%d %d %d\n",ans.l3,ans.r3,ans.mid);
continue;
}
if(ans.r>=ans.sum&&ans.r>=ans.l&&ans.r>=ans.mid) {
printf("%d %d %d\n",ans.l2,ans.r2,ans.r);
continue;
}
//cout<<ans.l<<" "<<ans.sum<<" "<<ans.r<<" "<<ans.mid<<endl;
}
//print(1);
return 0;
}
int heh=Main();
int main() {
;
}