Submission #72580808

---

Source Code Expand

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
typedef pair<int, ll> pii;

#define mid ((t[p].l + t[p].r) >> 1)
#define l(p) (p << 1)
#define r(p) (l(p) | 1)

const int N = 2e5 + 9;
int n, q;

struct tree{
    int l, r, len;
    int cnt;
    ll mx;
    pii tag;
}t[N << 2];

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    t[p].cnt = t[p].len = r - l + 1;
    if(l == r) return;
    build(l(p), l, mid);
    build(r(p), mid + 1, r);
}

void adds(int p, pii x){
    if(x.first){
        t[p].tag.first += x.first;
        t[p].tag.second = x.second;

        if(x.first % 2){
            t[p].cnt = t[p].len - t[p].cnt;
        }
        t[p].mx = x.second * (t[p].cnt > 0);
    }
    else{
        t[p].tag.second += x.second;
        t[p].mx += x.second * (t[p].cnt > 0);
    }
}

void pushdown(int p){
    adds(l(p), t[p].tag);
    adds(r(p), t[p].tag);
    t[p].tag = make_pair(0, 0);
}

void pushup(int p){
    t[p].cnt = t[l(p)].cnt + t[r(p)].cnt;
    t[p].mx = max(t[l(p)].mx, t[r(p)].mx);
}

void modify(int p, int l, int r, pii x){
    if(l <= t[p].l && r >= t[p].r){
        adds(p, x);
        return;
    }

    pushdown(p);
    if(l <= mid) modify(l(p), l, r, x);
    if(r > mid) modify(r(p), l, r, x);
    pushup(p);
}

ll query(int p, int l, int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].mx;
    }

    pushdown(p);
    ll ret = 0;
    if(l <= mid) ret = max(ret, query(l(p), l, r));
    if(r > mid) ret = max(ret, query(r(p), l, r));
    pushup(p);
    return ret;
}

int main(){
    /* freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout); */

    scanf("%d %d", &n, &q);
    build(1, 1, n);

    int op, l, r, x;
    for(int i = 1; i <= q; ++ i ){
        scanf("%d %d %d", &op, &l, &r);
        if(op == 1){
            scanf("%d", &x);
            modify(1, l, r, make_pair(0, x));
        }
        else if(op == 2){
            modify(1, l, r, make_pair(1, 0));
        }
        else{
            printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}

Submission Info

Judge Result