제출 #634868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634868		K4YAN	ZIGZAG (INOI20_zigzag)	C++17	0 / 100	865 ms	85580 KiB

Main

//Be Name Khoda

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define all(x) x.begin(), x.end()

const ll mxn = 3e5 + 16, INF = 1e16 + 16;
ll n, t, q, w;
vector<ll> g;
char c;

inline void input() {

    cin >> n >> t;
    for(int i = 0; i < n; i++) {
        cin >> q;
        g.push_back(q);
    }

}

struct item {
    ll sz, ans, L, R, bp, bs, kp, ks;
};
struct segtree {

    int sz = 1;
    item NE = {0, 0, 0, 0, 0, 0, 0, 0};
    vector<item> v;
    vector<ll> lz, ls;

    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, NE);
        lz.assign(2 * sz, 1);
        ls.assign(2 * sz, 0);
        return;
    }
    void shift(int x, int lx, int rx) {
        if(lz[x] == 0 && ls[x] == 0) return;
        ll a = lz[x], b = ls[x];
        lz[x] = ls[x] = 0;
        v[x].L += b, v[x].R += b;
        if(a) {
            v[x].L *= -1, v[x].R *= -1;
            swap(v[x].kp, v[x].bp);
            swap(v[x].ks, v[x].bs);
        }
        if(rx - lx == 1) return;
        if(lz[2 * x + 1]) ls[2 * x + 1] -= b;
        else ls[2 * x + 1] += b;
        if(lz[2 * x + 2]) ls[2 * x + 2] -= b;
        else ls[2 * x + 2] += b;
        lz[2 * x + 1] ^= a, lz[2 * x + 2] ^= a;
        return;
    }//Shift Vaghean doroste
    item merge(item a, item b) {
        if(a.sz == 0) return b;
        if(b.sz == 0) return a;
        ll s = a.sz + b.sz, L = a.L, R = b.R, ans = a.ans + b.ans, bp, bs, kp, ks;
        if(a.R == b.L) {
            kp = a.kp, ks = b.ks, bp = a.bp, bs = b.bs;
            q = max(a.ks, a.bs);
            if(q < a.sz) {
                ans += (q * (q - 1) / 2);
            }
            q = max(b.bp, b.kp);
            if(q < b.sz) {
                ans += (q * (q - 1) / 2);
            }
            return {s, ans, L, R, bp, bs, kp, ks};
        }
        if(a.R > b.L) {
            if(a.sz > a.bs) {
                if(b.kp < b.sz) {
                    q = a.bs + b.kp;
                    ans += (q * (q - 1) / 2);
                    bp = a.bp, bs = b.bs, kp = a.kp, ks = b.ks;
                    return {s, ans, L, R, bp, bs, kp, ks};
                } else {
                    bp = a.bp, kp = a.kp;
                    if(b.sz & 1) {
                        bs = 1, ks = b.sz + a.bs;
                    } else {
                        bs = b.sz + a.bs, ks = 1;
                    } return {s, ans, L, R, bp, bs, kp, ks};
                } ///okay
            }
            else if(a.sz == a.bs) {
                if(b.kp < b.sz) {
                    bs = b.bs, ks = b.ks;
                    if(a.sz & 1) {
                        bp = a.sz + b.kp, kp = 1;
                    } else {
                        kp = a.sz + b.kp, bp = 1;
                    } return {s, ans, L, R, bp, bs, kp, ks};
                } else if(b.kp == b.sz) {
                    if(a.sz & 1) {
                        kp = 1, bp = s;
                    } else {
                        kp = s, bp = 1;
                    } if(b.sz & 1) {
                        bs = 1, ks = s;
                    } else {
                    bs = s, ks = 1;
                    } return {s, ans, L, R, bp, bs, kp, ks};
                }// okay
            }
        }
        if(a.R < b.L) {
            if(b.sz > b.bp) {
                if(a.sz > a.ks) {
                    q = a.ks + b.bp;
                    ans += (q * (q - 1) / 2);
                    bp = a.bp, bs = b.bs, kp = a.kp, ks = b.ks;
                    return {s, ans, L, R, bp, bs, kp, ks};
                } else if(a.sz == a.ks) {
                    bs = b.bs, ks = b.ks;
                    if(a.sz & 1) {
                        bp = 1, kp = a.sz + b.bp;
                    } else {
                        bp = a.sz + b.bp, kp = 1;
                    } return {s, ans, L, R, bp, bs, kp, ks};
                }
            } else if(b.sz == b.bp) {
                if(a.sz > a.ks) { //sz, ans, L, R, bp, bs, kp, ks
                    kp = a.kp, bp = a.bp;
                    if(b.sz & 1) {
                        bs = b.sz + a.ks, ks = 1; 
                    } else {
                        ks = b.sz + a.ks, bs = 1;
                    } return {s, ans, L, R, bp, bs, kp, ks};
                } else if(a.sz == a.ks) {
                    if(b.sz & 1) {
                        bs = s, ks = 1;
                    } else {
                        ks = s, bs = 1;
                    } if(a.sz & 1) {
                        kp = s, bp = 1;
                    } else {
                        bp = s, kp = 1;
                    } return {s, ans, L, R, bp, bs, kp, ks};
                } 
            }
        }
        return NE;
    }
    void build(vector<ll> &g, int x, int lx, int rx) {
        if(rx - lx == 1) {
            if(lx < int(g.size())) {
                v[x] = {1, 0, g[lx], g[lx], 1, 1, 1, 1};
            } return;
        }
        int m = (lx + rx) >> 1;
        build(g, 2 * x + 1, lx, m), build(g, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return;
    }
    void build(vector<ll> & g) {
        build(g, 0, 0, sz);
        return;
    }
    void zarb(int l, int r, int x, int lx, int rx) {
        shift(x, lx, rx);
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            lz[x] = 1;
            shift(x, lx, rx);
            return;
        } int m = (lx + rx) >> 1;
        zarb(l, r, 2 * x + 1, lx, m);
        zarb(l, r, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return;
    }
    void zarb(int l, int r) {
        zarb(l, r, 0, 0, sz);
        return;
    }
    void jam(int l, int r, int q, int x, int lx, int rx) {
        shift(x, lx, rx);
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            ls[x] += q;
            shift(x, lx, rx);
            return;
        } int m = (lx + rx) >> 1;
        jam(l, r, q, 2 * x + 1, lx, m);
        jam(l, r, q, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return;
    }
    void jam(int l, int r, int q) {
        jam(l, r, q, 0, 0, sz);
        return;
    }
    item ask(int l, int r, int x, int lx, int rx) {
        shift(x, lx, rx);
        if(rx <= l || r <= lx) return NE;
        if(l <= lx && rx <= r) {
            return v[x];
        } int m = (lx + rx) >> 1;
        item ans = ask(l, r, 2 * x + 1, lx, m);
        ans = merge(ans, ask(l, r, 2 * x + 2, m, rx));
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return ans;
    } 
    item ask(int l, int r) {
        return ask(l, r, 0, 0, sz);
    }

}; segtree st;

inline void solve() {

    st.init(n);
    st.build(g);
    for(int i = 0; i < t; i++) {
        cin >> c;
        if(c == '*') {
            cin >> q >> w; q--;
            st.zarb(q, w);
        } else if(c == '+') {
            ll v;
            cin >> q >> w >> v; q--;
            st.jam(q, w, v);
        } else {
            cin >> q >> w; q--;
            item d;
            d = st.ask(q, w);
            ll ans = d.ans;
            q = max(d.bp, d.kp);
            w = max(d.bs, d.ks);
            if(q < d.sz) {
                ans += (q * (q - 1) / 2);
                ans += (w * (w - 1) / 2);
            } else {
                ans += (q * (q - 1) / 2);
            } ans += d.sz;
            cout << ans << "\n";
        }
    } return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

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