제출 #795846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795846		MISM06	ZIGZAG (INOI20_zigzag)	C++14	100 / 100	946 ms	149444 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < int , pii > piii;
typedef pair < ll , ll > pll;
typedef pair < ll , pll > plll;
#define pb  push_back
#define all(x)  x.begin(), x.end()
#define sze     size()
#define F first
#define S second
#define kids    int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1;
#define wall__ cout << "________________________________________\n";

const ll N = 3e5 + 10, mod = 1e9 + 7;

struct node {
    ll ans, vl, vr, pre[2], suf[2], pis[2], sis[2], t, len;
    node () {
        ans = 0; vl = 0; vr = 0; pre[0] = pre[1] = 0; suf[0] = suf[1] = 0; pis[0] = pis[1] = 0; sis[0] = sis[1] = 0; t = 1;
        len = 0;
    }
    void set_len (int x) {
        len = x; t = len % 2; t ^= 1;
    }
    void merge (node x, node y) {
        len = x.len + y.len;
        set_len(len);
        vl = x.vl; vr = y.vr;
        ans = x.ans + y.ans;
        if (x.vr < y.vl) ans += x.suf[0] * y.pre[0];
        if (x.vr > y.vl) ans += x.suf[1] * y.pre[1];
        
        pre[0] = x.pre[0];
        
        pre[1] = x.pre[1];
        
        suf[0] = y.suf[0];
        
        suf[1] = y.suf[1];

        if (x.vr > y.vl) {
            if (x.t == 0) pre[0] += y.pre[1] * x.pis[0];
            
            if (x.t == 1) pre[1] += y.pre[1] * x.pis[1];
            
            if (y.t == 0) suf[0] += y.sis[0] * x.suf[1];
            
            if (y.t == 1) suf[1] += y.sis[1] * x.suf[1];
        } else if (x.vr < y.vl) {
            if (x.t == 1) pre[0] += y.pre[0] * x.pis[0];
            
            if (x.t == 0) pre[1] += y.pre[0] * x.pis[1];
            
            if (y.t == 1) suf[0] += y.sis[0] * x.suf[0];
            
            if (y.t == 0) suf[1] += y.sis[1] * x.suf[0];
        }
        
        pis[0] = pis[1] = 0; sis[0] = sis[1] = 0;
        if (x.vr > y.vl) {
            if (x.pis[0] && x.t == 0 && y.pis[1]) pis[0] = 1;
            if (x.pis[1] && x.t == 1 && y.pis[1]) pis[1] = 1;
            if (y.sis[0] && y.t == 0 && x.sis[1]) sis[0] = 1;
            if (y.sis[1] && y.t == 1 && x.sis[1]) sis[1] = 1;
        } else if (x.vr < y.vl) {
            if (x.pis[0] && x.t == 1 && y.pis[0]) pis[0] = 1;
            if (x.pis[1] && x.t == 0 && y.pis[0]) pis[1] = 1;
            if (y.sis[0] && y.t == 1 && x.sis[0]) sis[0] = 1;
            if (y.sis[1] && y.t == 0 && x.sis[0]) sis[1] = 1;
        }
    }
    void relax (ll x, ll y) {
        if (x == -1) {
            swap(pre[0], pre[1]);
            swap(suf[0], suf[1]);
            vl *= -1ll;
            vr *= -1ll;
            swap(sis[0], sis[1]);
            swap(pis[1], pis[0]);
        }
        vl += y;
        vr += y;
    }
    
    void make (ll x) {
        set_len(1);
        vl = x; vr = x;
        pre[0] = pre[1] = 1;
        suf[0] = suf[1] = 1;
        ans = 1;
        pis[0] = pis[1] = 1;
        sis[0] = sis[1] = 1;
    }
};

int n, a[N];
struct segtree {
    node seg[N << 2];
    ll la1[N << 2], la2[N << 2];
    void build (int v = 1, int tl = 1, int tr = n) {
        la1[v] = 1; la2[v] = 0;
        if (tl == tr) {
            seg[v].make(a[tl]);
            return;
        } kids;
        build(cl, tl, mid);
        build(cr, mid + 1, tr);
        seg[v].merge(seg[cl], seg[cr]);
    }
    void shift (int v, int tl, int tr) {
        seg[v].relax(la1[v], la2[v]);
        int cl = v << 1, cr = v << 1 | 1;
        if (tl != tr) {
            la1[cl] *= la1[v];
            la2[cl] *= la1[v];
            la2[cl] += la2[v];
            la1[cr] *= la1[v];
            la2[cr] *= la1[v];
            la2[cr] += la2[v];
        }
        la1[v] = 1;
        la2[v] = 0;
    }
    void upd (int s, ll val, int l, int r, int v = 1, int tl = 1, int tr = n) {
        shift(v, tl, tr);
        if (l > r) return;
        if (l == tl && r == tr) {
            if (s == 0) la2[v] += val;
            else la1[v] *= -1ll;
            shift(v, tl, tr);
            return;
        } kids
        upd(s, val, l, min(r, mid), cl, tl, mid);
        upd(s, val, max(l, mid + 1), r, cr , mid + 1, tr);
        seg[v].merge(seg[cl], seg[cr]);
    }
    node ask (int l, int r, int v = 1, int tl = 1, int tr = n) {
        shift(v, tl, tr);
        if (l == tl && r == tr) return seg[v];
        kids
        if (r <= mid) return ask(l, r, cl, tl, mid);
        else if (l > mid) return ask(l, r, cr, mid + 1, tr);
        else {
            node res;
            res.merge(ask(l, mid, cl, tl, mid), ask(mid + 1, r, cr, mid + 1, tr));
            return res;
        }
    }
} f;

void solve () {
    
    int q; cin >> n >> q;
    for (int i =1 ; i <= n; i++) cin >> a[i];
    f.build();
    while(q--) {
        char t; cin >> t; int l, r; cin >> l >> r;
        if (t == '?') {
            cout << f.ask(l, r).ans << '\n';
        } else if (t == '+') {
            ll x; cin >> x;
            f.upd(0, x, l, r);
        } else {
            f.upd(1, 0, l, r);
        }
    }
    
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
/*
11 1
1 2 3 4 3 4 3 4 3 4 5
? 1 11
*/

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15