제출 #482968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482968		K4YAN	Sterilizing Spray (JOI15_sterilizing)	C++17	75 / 100	1127 ms	102332 KiB

sterilizing

//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define piii pair<pii, int>
#define piiii pair<pii, pii>
#define piiiii pair<pii, piii>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const ll mxn = 1e5 + 16;
ll n, k, m, q, w;
ll fw[mxn];
vector<int> res, g;
set<int> s[3 * mxn];

struct segtree {

    int sz = 1;
    vector<ll> v;
    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, 0);
    }
    void add(int i, ll k, int x, int lx, int rx) {
        if(k > 0) {
            s[x].insert(i);
        }
        if(rx - lx == 1) {
            v[x] = k;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) add(i, k, 2 * x + 1, lx, m);
        else add(i, k, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void add(int i, ll k) {
        add(i, k, 0, 0, sz);
    }
    void edit(int i, ll k, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] /= k;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) edit(i, k, 2 * x + 1, lx, m);
        else edit(i, k, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void edit(int i, ll k) {
        edit(i, k, 0, 0, sz);
    }
    void rem(int i, int x, int lx, int rx) {
        s[x].erase(i);
        if(rx - lx == 1) {
            v[x] = 0;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) rem(i, 2 * x + 1, lx, m);
        else rem(i, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void rem(int i) {
        rem(i, 0, 0, sz);
    }
    void cal(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            for(auto it : s[x]) {
                res.push_back(it);
            }
            return;
        }
        int m = (lx + rx) >> 1;
        cal(l, r, 2 * x + 1, lx, m);
        cal(l, r, 2 * x + 2, m, rx);
    }
    void cal(int l, int r) {
        cal(l, r, 0, 0, sz);
    }
    ll ask(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return 0;
        if(l <= lx && rx <= r) {
            return v[x];
        }
        int m = (lx + rx) >> 1;
        ll a1 = ask(l, r, 2 * x + 1, lx, m);
        ll a2 = ask(l, r, 2 * x + 2, m, rx);
        return a1 + a2;
    }
    ll ask(int l, int r) {
        return ask(l, r, 0, 0, sz);
    } 

};
segtree st;

void input() {

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

}

void solve() {

    st.init(n);
    for(int i = 0; i < n; i++) {
        st.add(i, g[i]);
    }
    if(m == 1) {
        for(int i = 0; i < q; i++) {
            int si;
            cin >> si;
            if(si == 2) continue;
            if(si == 1) {
                ll a, b;
                cin >> a >> b;
                a--; g[a] = b;
                st.add(a, b);
            }
            if(si == 3) {
                int l, r;
                cin >> l >> r;
                l--;
                cout << st.ask(l, r) << "\n";
            }
        }
        return;
    }
    for(int i = 0; i < q; i++) {
        int si;
        cin >> si;
        if(si == 1) {
            ll a, b;
            cin >> a >> b;
            a--; g[a] = b;
            st.rem(a);
            st.add(a, b);
        }
        if(si == 2) {
            int l, r;
            cin >> l >> r;
            l--; res.clear();
            st.cal(l, r);
            for(auto it : res) {
                if(g[it] >= m) {
                    g[it] /= m;
                    st.edit(it, m);
                }
                else {
                    g[it] = 0;
                    st.rem(it);
                }
            }
        }
        if(si == 3) {
            int l, r;
            cin >> l >> r;
            l--;
            cout << st.ask(l, r) << "\n";
        }
    }

}

int main() {

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

    input(), solve();

    return 0;

}
/*
5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75