舅舅孩子!!!小白广公园打死都调不粗来!

P4513 小白逛公园

E17bits @ 2019-09-04 17:39:06

rt

#include <bits/stdc++.h>
#define N 1000005
#define def3 int o, int l, int r
#define go3 1, 1, n
#define gol ls, l, mid
#define gor rs, mid+1, r
#define ls (o<<1)
#define rs (o<<1|1)
#define mid ((l+r)>>1)
using namespace std;

int read() {
    int ret=0, f=1;
    char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) {
        ret=(ret<<3)+(ret<<1)+ch-48;
        ch=getchar();
    }
    return ret*f;
}

int n, m, x, y, cnt;
int a[500005];
int t[N<<1], lm[N<<1], rm[N<<1], mm[N<<1];

inline void up(int o) {
    t[o]=t[ls]+t[rs];
    lm[o]=max(lm[ls], t[ls]+lm[rs]);
    rm[o]=max(rm[rs], t[rs]+rm[ls]);
    mm[o]=max(max(mm[ls], mm[rs]), rm[ls]+lm[rs]);
}

void build(def3) {
    if(l==r) {
        t[o]=lm[o]=rm[o]=mm[o]=a[l];
        return;
    }
    build(gol);
    build(gor);
    up(o);
}

void change(def3) {
    if(l==x && r==x) {
        t[o]=lm[o]=rm[o]=mm[o]=y;
        return;
    }
    if(x<=mid) change(gol);
    else change(gor);
    up(o);
}

int ask(def3) {
    if(x<=l && r<=y) return o;
    if(y<=mid) return ask(gol);
    if(mid<x) return ask(gor);
    int ols=ask(gol), ors=ask(gor);
    lm[++cnt]=max(lm[ols], t[ols]+lm[ors]);
    rm[cnt]=max(rm[ors], t[ors]+rm[ols]);
    mm[cnt]=max(max(mm[ols], mm[ors]), rm[ols]+lm[ors]);
    return cnt;
}

inline void ready() {
    cnt=n;
    n=read();
    m=read();
    for(register int i=1; i<=n; ++i)
        a[i]=read();
    build(go3);
}

inline void solve() {
    for(register int i=1, pd; i<=m; ++i) {
        pd=read();
        x=read();
        y=read();
        if(pd==1) {
            if(x>y) x^=y^=x^=y;
            int p=ask(go3);
            printf("%d\n", mm[p]);
        }
        else change(go3);
    }
}

int main() {
    ready();
    solve();
    return 0;
}

by Mr_H @ 2019-09-04 17:40:02

码风引起不适


by 咸鱼小白 @ 2019-09-04 17:45:34

救救孩子,救救错别字(雾)


by _FILARET_ @ 2019-09-04 17:46:57

码风引起严重不适


by pzc2004 @ 2019-09-04 17:49:02

码风引起严重不适


by pzc2004 @ 2019-09-04 17:49:32

头像极度危险


by By_Ha @ 2019-09-04 19:29:35

我当时的对拍https://www.luogu.org/paste/14th2rvd

一点小细节自己改


by By_Ha @ 2019-09-04 19:30:02

头像致远星


|