Submission #1152084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152084		Zero_OP	Fish 2 (JOI22_fish2)	C++20	100 / 100	1707 ms	20588 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];

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;
    }

    void debug(int id, int l, int r){
        if(l == r){
            cout << st[id].mn << ' ';
            if(r == N) cout << '\n';
        } else{
            int mid = l + r >> 1;
            down(id);
            debug(id << 1, l, mid);
            debug(id << 1 | 1, mid + 1, r);
        }
    }
} 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] = max(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;

set<pair<int, int>> segs;

void add_segment(int l, int r){
    // cout << "insert : " << l << ' ' << r << '\n';
    // assert(r-l > 1);
    // segs.insert({l, r});
    MinCount.update(1, 1, N, l+1, r-1, +1); 
}

void erase_segment(int l, int r){
    // cout << "erase : " << l << ' ' << r << '\n';
    // assert(r-l > 1);
    // segs.erase({l, r});
    MinCount.update(1, 1, N, l+1, r-1, -1);
}

void debug_segs(){
    for(auto [l, r] : segs) cout << dbg(l) << ' ' << dbg(r) << '\n';
}

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

void extract_left_endpoint(int L, vpi& result){
    if(L+2 > N+1) return;
    int R = L+2;
    ll fixed_sum = Fenwick.queryPrefix(L);
    while(true){
        if(bad(L, R)) result.eb(L, R);
        if(R == N+1) break;
        //pref[R-1] - pref[L] < a[R] 
        R = TreeRightEndpoint.find_next(R+1, N, fixed_sum);
    }
}

void extract_right_endpoint(int R, vpi& result){
    if(R-2 < 0) return;
    int L = R-2;
    ll fixed_sum = Fenwick.queryPrefix(R-1);
    while(true){
        if(bad(L, R)) result.eb(L, R);
        if(L == 0) break;
        //pref[R-1] - pref[L] > a[L]
        L = TreeLeftEndpoint.find_next(1, L-1, fixed_sum);
    }
}

void extract_include_point_segments(int i, vpi& result){
    if(i-1 < 0 || i+1 > N+1) return;
    int L = i-1, R = i+1;
    while(true){
        if(bad(L, R)) result.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));
        else R = TreeRightEndpoint.find_next(R+1, N, Fenwick.queryPrefix(L));
    }
}

void update(int i, int x){
    vpi segments;
    extract_left_endpoint(i-1, segments);
    extract_right_endpoint(i-1, segments);
    extract_left_endpoint(i+1, segments);
    extract_right_endpoint(i+1, segments);
    extract_left_endpoint(i, segments);
    extract_right_endpoint(i, segments);
    extract_include_point_segments(i, segments);
    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;

    extract_left_endpoint(i-1, segments);
    extract_right_endpoint(i-1, segments);
    extract_left_endpoint(i+1, segments);
    extract_right_endpoint(i+1, segments);
    extract_left_endpoint(i, segments);
    extract_right_endpoint(i, segments);
    extract_include_point_segments(i, segments);
    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)); 
        //pref[r] - pref[R-1] < a[R-1] <=> pref[r] < a[R-1] + pref[R-1]
        if(nxt < l) break;
        R = nxt;
    }

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

    // cout << dbg(L) << dbg(R) << '\n';
    // MinCount.debug(1, 1, N);
    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])
        vpi cur; 
        extract_left_endpoint(i, cur);
        for(auto [l, r] : cur) add_segment(l, r);       
    }

    // ROF(j, N+2, 2){
    //     //finding all i that min(a[i], a[j]) > sum[i+1, j-1]
    //     //<=> pref[j-1] - pref[i] < min(a[i], a[j])
    //     //<=> pref[j-1] - pref[i] < a[i]
    //     //<=> pref[j-1] < a[i] + pref[i]
    //     int i = j - 2;

    //     while(true){
    //         if(pref[j-1] - pref[i] < min(a[i], a[j])) add_segment(i, j);
    //         if(i < 1) break;
    //         i = TreeLeftEndpoint.find_next(1, i-1, pref[j-1]);
    //     }
    // }

    // sort(all(segments));
    // for(auto [l, r] : segments) cout << l << ' ' << r << '\n';
    
    cin >> Q;
    while(Q--){
        int t;
        cin >> t;
        if(t == 1){
            int x, y;
            cin >> x >> y;
            update(x, y);
            // debug_segs();
            // cout << "_~~_~_~_~__~_~_~_~_~_~_~_~~_~_~_~\n";
        } else{
            int l, r;
            cin >> l >> r;
            // debug_segs();
            cout << query(l, r) << '\n';
            // cout << "_~~_~_~_~__~_~_~_~_~_~_~_~~_~_~_~\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;
}

/*

Ý tưởng : 
a[0] = a[N+1] = \infty
Xét tất cả các đoạn [l, r] thỏa :
- min(a[l-1], a[r+1]) > pref[r] - pref[l-1] (*) : Do những vị trí trong [l, r] không thể sống sót

Tính chất của điều kiện (*) : 
- Chỉ có nhiều nhất N đoạn thỏa mãn 
- Với hai đoạn thẳng bất kỳ, chúng chỉ có thể không giao nhau hoặc bao nhau
- Với mỗi vị trí i, số lượng đoạn thẳng [l, r] có thể chứa i nhiều nhất là \log_2(10^9)

Giờ đưa hết các đoạn thẳng thỏa mãn (*) vào tập S để xử lý truy vấn, cập nhật

Cập nhật vị trí i thành giá trị x : 
- Ta chỉ cần quan tâm các đoạn [l, r] có đầu mút là i-1/i/i+1 : 
    + Ta xóa hết các đoạn hiện tại chứa i
    + Ta cập nhật lại các CTDl rồi xử lý lại, bước thêm những đoạn có chứa i
- Dùng một cây BIT xử lý bước tính tổng nhanh

Truy vấn đoạn [l, r] : 
- Ta sẽ tìm vị trí l' và r' : 
    + l' là vị trí trái nhất mà a[l'] > sum[l...l'-1] (nếu không có thì sẽ là l)
    + r' là vị trí phải nhất mà a[r'] > sum[r'+1...r] (nếu không có thì sẽ là r)
- Đếm số vị trí j trong đoạn [l', r'] mà không có đoạn nào thuộc S phủ lên j

*/

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