不是,为什么开O2就死呢???
题目连接:https://www.acwing.com/problem/content/description/1272/
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1e10
#define N 100010
#define ls u<<1
#define rs ls|1
struct Node{
ll l,r;
ll sum,add,mx;
}tr[N<<2];
ll n,m;
ll a[N];
void pushup(ll u){
tr[u].sum=tr[ls].sum+tr[rs].sum;
tr[u].mx=max(tr[ls].mx,tr[rs].mx);
}
void pushdown(ll u){
if(tr[u].add){
tr[ls].add+=tr[u].add;
tr[rs].add+=tr[u].add;
tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[u].add;
tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[u].add;
tr[ls].mx+=tr[u].add;
tr[rs].mx+=tr[u].add;
tr[u].add=0;
}
}
void build(ll u,ll l,ll r){
if(l==r)tr[u]={l,r,a[l],0,a[l]};
else{
ll mid=l+r>>1;
tr[u]={l,r};
build(ls,l,mid),build(rs,mid+1,r);
pushup(u);
}
}
ll querySum(ll u,ll l,ll r){
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
else{
pushdown(u);
ll mid=tr[u].l+tr[u].r>>1;
ll sum=0;
if(l<=mid)sum+=querySum(ls,l,r);
if(r>mid)sum+=querySum(rs,l,r);
return sum;
}
}
ll queryMx(ll u,ll l,ll r){
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].mx;
else{
pushdown(u);
ll mid=tr[u].l+tr[u].r>>1;
ll mx=-inf;
if(l<=mid)mx=max(mx,queryMx(ls,l,r));
if(r>mid)mx=max(mx,queryMx(rs,l,r));
return mx;
}
}
ll modify(ll u,ll l,ll r,ll w){
// cout<<u<<" "<<l<<" "<<r<<" "<<w<<endl;
if(l<=tr[u].l&&tr[u].r<=r){
tr[u].add+=w;
tr[u].sum+=(tr[u].r-tr[u].l+1)*w;
tr[u].mx+=w;
}else{
pushdown(u);
ll mid=tr[u].l+tr[u].r>>1;
if(l<=mid)modify(ls,l,r,w);
if(r>mid)modify(rs,l,r,w);
pushup(u);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
build(1,1,n);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)modify(1,i,i,a[i]);
while(m--){
int l,r;
cin>>l>>r;
cout<<queryMx(1,l,r)<<'\n';
}
return 0;
}