제출 #1151323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151323		Zero_OP	Fish 2 (JOI22_fish2)	C++20	31 / 100	489 ms	38812 KiB

fish2

//https://codeforces.com/blog/entry/101003?#comment-898608
#include <bits/stdc++.h>

using namespace std;

//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)

//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

//binary search
#define lwb lower_bound
#define upb upper_bound

//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 1e5 + 5;
const ll inf = 1e15 + 100;

int N, Q;
ll a[MAX];
ll pref[MAX];
set<int> left_endpoint[MAX], right_endpoint[MAX];

struct FenwickTree{
    const int offset = 0;
    vl bit;
    void init(int n){
        bit = vl(n+1, 0);
    }

    void update(int i, ll v){
        i += offset;
        for(; i < sz(bit); i += i & (-i)) bit[i] += v;
    }

    ll queryPrefix(int i){
        ll sum = 0;
        i += offset;
        for(; i > 0; i -= i & (-i)) sum += bit[i];
        return sum;
    }

    ll query(int l, int r){
        return queryPrefix(r) - queryPrefix(l-1);
    }
} Fenwick;

struct SegmentTreeMinCount{
    struct Node{
        int mn, cnt;
        Node() : mn(0), cnt(0) {}
        Node(int mn, int cnt) : mn(mn), cnt(cnt) {}

        friend Node operator + (const Node& a, const Node& b){
            if(a.mn == b.mn) return Node(a.mn, a.cnt + b.cnt);
            else return (a.mn < b.mn ? a : b);
        }
    };
    
    vector<Node> st;
    vi lazy;
    int N;
    SegmentTreeMinCount(int n) : N(n), st(n << 2), lazy(n << 2) {}
    
    void apply(int id, int delta){
        st[id].mn += delta;
        lazy[id] += delta;
    }

    void down(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }
    
    void build(int id, int l, int r){
        st[id].cnt = r - l + 1;
        if(l < r){
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
        }
    }

    void update(int id, int l, int r, int u, int v, int delta){
        if(u <= l && r <= v) apply(id, delta);
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, delta);
            if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, delta);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    Node query(int id, int l, int r, int u, int v){
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        down(id);
        if(u > mid)  return query(id << 1 | 1, mid + 1, r, u, v);
        if(mid >= v) return query(id << 1, l, mid, u, v);
        return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
    }

    int count_min(int l, int r){
        Node cur = query(1, 1, N, l, r);
        return cur.cnt;
    }
} MinCount(0);

struct SegmentTreeRightEndpoint{
    vl st, lazy;
    void init(int n){
        st.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
    }

    void apply(int id, ll val){
        st[id] += val;
        lazy[id] += val;
    }

    void down(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }

    void build(int id, int l, int r){
        if(l == r){
            //pref[j-1] - pref[i] < a[j]
            //<=> pref[j-1] - a[j] < pref[i]
            st[id] = pref[l-1] - a[l];
        } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
    }

    void update(int id, int l, int r, int u, int v, ll delta){
        if(u <= l && r <= v) apply(id, delta);
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, delta);
            if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, delta);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
    }

    int find_next(int id, int l, int r, int u, int v, ll s){
        if(v < l || u > r) return -1;
        if(st[id] >= s) return -1;

        if(u <= l && r <= v){
            while(l < r){
                int mid = l + r >> 1;
                down(id);
                if(st[id << 1] < s) id = id << 1, r = mid;
                else id = id << 1 | 1, l = mid + 1;
            }
            return l;
        } else{
            int mid = l + r >> 1;
            down(id);
            int go = find_next(id << 1, l, mid, u, v, s);
            if(go != -1) return go;
            return find_next(id << 1 | 1, mid + 1, r, u, v, s);
        }
    }

    int find_next(int l, int r, ll s){
        if(l > r) return N+1;
        int R = find_next(1, 1, N, l, r, s);
        if(R == -1) return N+1;
        return R;
    }
} TreeRightEndpoint;

struct SegmentTreeLeftEndpoint{ 
    vl st, lazy;
    void init(int n){
        st.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
    }

    void apply(int id, ll val){
        st[id] += val;
        lazy[id] += val;
    }

    void down(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }

    void build(int id, int l, int r){
        if(l == r){
            //pref[j-1] - pref[i] < a[i]
            //pref[j] < pref[i] + a[i]
            st[id] = pref[l] + a[l];
        } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    void update(int id, int l, int r, int u, int v, ll delta){
        if(u <= l && r <= v) apply(id, delta);
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, delta);
            if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, delta);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
    }

    int find_next(int id, int l, int r, int u, int v, ll s){
        if(v < l || u > r) return -1;
        if(st[id] <= s) return -1;
        
        if(u <= l && r <= v){
            while(l < r){
                int mid = l + r >> 1;
                down(id);
                if(st[id << 1 | 1] > s) id = id << 1 | 1, l = mid + 1;
                else  id = id << 1, r = mid;
            }
            return l; 
        } else{
            int mid = l + r >> 1;
            down(id);
            int go = find_next(id << 1 | 1, mid + 1, r, u, v, s);
            if(go != -1) return go;
            return find_next(id << 1, l, mid, u, v, s);
        }
    }

    int find_next(int l, int r, ll s){
        if(l > r) return 0;
        int L = find_next(1, 1, N, l, r, s);
        if(L == -1) L = 0;
        return L;
    }
} TreeLeftEndpoint;

void add_segment(int l, int r){
    assert(r-l > 1);
    MinCount.update(1, 1, N, l+1, r-1, +1); 
    left_endpoint[l].insert(r);
    right_endpoint[r].insert(l);
}

void erase_segment(int l, int r){
    assert(r-l > 1);
    MinCount.update(1, 1, N, l+1, r-1, -1);
    left_endpoint[l].erase(r);
    right_endpoint[r].erase(l);
}

bool bad(int l, int r){
    assert(r-l > 1);
    return min(a[l], a[r]) > Fenwick.query(l+1, r-1);
}

void update(int i, int x){
    vpi segments;
    int l = i-1, r = i+1;
    while(true){
        if(bad(l, r)) segments.eb(l, r);
        if(l == 0 && r == N+1) break;
        if(a[l] < a[r]) l = TreeLeftEndpoint.find_next(1, l-1, Fenwick.queryPrefix(r-1)); //can't extend right
        else r = TreeRightEndpoint.find_next(r+1, N, Fenwick.queryPrefix(l)); //can't extend left
    }

    for(auto r : left_endpoint[i-1]) segments.eb(i-1, r);
    for(auto l : right_endpoint[i+1]) segments.eb(l, i+1);
    sort(all(segments)); compact(segments);
    for(auto [l, r] : segments) erase_segment(l, r);
    segments.clear();

    Fenwick.update(i, -a[i] + x);
    TreeLeftEndpoint.update(1, 1, N, i, N, -a[i] + x);
    TreeLeftEndpoint.update(1, 1, N, i, i, -a[i] + x);
    if(i < N) TreeRightEndpoint.update(1, 1, N, i+1, N, -a[i] + x);
    TreeRightEndpoint.update(1, 1, N, i, i, +a[i] - x);

    a[i] = x;

    l = i-1, r = i+1;
    while(true){
        if(bad(l, r)) {
            segments.eb(l, r);
        }
        if(l == 0 && r == N+1) break;
        if(a[l] < a[r]) l = TreeLeftEndpoint.find_next(1, l-1, Fenwick.queryPrefix(r-1)); //can't extend right
        else r = TreeRightEndpoint.find_next(r+1, N, Fenwick.queryPrefix(l)); //can't extend left
    }

    r = i+1;
    while(true){
        if(bad(i-1, r)) segments.eb(i-1, r);
        if(r == N+1) break;
        r = TreeRightEndpoint.find_next(r+1, N, Fenwick.queryPrefix(i-1));
    }

    l = i-1;
    while(true){
        if(bad(l, i+1)) segments.eb(l, i+1);
        if(l == 0) break;
        l = TreeLeftEndpoint.find_next(1, l-1, Fenwick.queryPrefix(i));
    }

    sort(all(segments)); compact(segments);
    for(auto [l, r] : segments) add_segment(l, r);
}

ll query(int l, int r){
    int R = r;
    while(true){
        int nxt = TreeLeftEndpoint.find_next(1, R-1, Fenwick.queryPrefix(r)); 
        if(nxt < l) break;
        R = nxt;
    }

    int L = l;
    while(true){
        int nxt = TreeRightEndpoint.find_next(L+1, N, Fenwick.queryPrefix(l-1));
        if(nxt > r) break;
        L = nxt;
    }

    int result = MinCount.count_min(L, R);
    return result;
}

void testcase(int ntestcase){
    cin >> N;
    a[0] = a[N+1] = inf;

    FOR(i, 1, N+1) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }

    Fenwick.init(N);
    TreeLeftEndpoint.init(N);
    TreeRightEndpoint.init(N);
    MinCount = SegmentTreeMinCount(N);

    FOR(i, 1, N+1) Fenwick.update(i, +a[i]);
    TreeLeftEndpoint.build(1, 1, N);
    TreeRightEndpoint.build(1, 1, N);
    MinCount.build(1, 1, N);

    FOR(i, 0, N){
        //finding all j that min(a[i], a[j]) > sum[i+1, j-1]
        //<=> pref[j-1] - pref[i] < min(a[i], a[j])
        int j = i+2;
        while(true){
            if(pref[j-1] - pref[i] < min(a[i], a[j])) add_segment(i, j);
            if(j > N) break;
            j = TreeRightEndpoint.find_next(j+1, N, pref[i]);
        }
    }

    cin >> Q;
    while(Q--){
        int t;
        cin >> t;
        if(t == 1){
            int x, y;
            cin >> x >> y;
            update(x, y);
        } else{
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("main.out", "w", stdout);
#endif // LOCAL

    int T = 1;
//    cin >> T;
    FOR(i, 0, T) testcase(i);

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17