//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
*/
