#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ar array
const int N = 1e5 + 5;
const int inf = 1e9;
struct ST{
ar<int, 2> tree[N << 2];
int p[N << 2];
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x<<1][0] += p[x], p[x<<1] += p[x];
tree[x<<1|1][0] += p[x], p[x<<1|1] += p[x];
p[x] = 0;
}
void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x][0] += v;
p[x] += v;
return;
} int m = (lx + rx) >> 1;
push(x, lx, rx);
add(l, r, v, lx, m, x<<1);
add(l, r, v, m+1, rx, x<<1|1);
}
ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return {N, N};
if(lx >= l && rx <= r){
return tree[x];
}
push(x, lx, rx);
int m = (lx + rx) >> 1;
auto L = get(l, r, lx, m, x<<1), R = get(l, r, m+1, rx, x<<1|1);
if(L[0] == R[0]) return {L[0], L[1] + R[1]};
else return min(L, R);
}
void build(int lx = 0, int rx = N, int x = 1){
tree[x][1] = rx - lx + 1;
if(lx == rx) return;
int m = (lx + rx) >> 1;
build(lx, m, x<<1);
build(m+1, rx, x<<1|1);
}
}tree;
int a[N];
int pref[N], par[N][2], p2[N][2];
int st[N][20];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
tree.build();
int n; cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pref[i] = pref[i-1] + a[i];
}
a[0] = a[n+1] = inf * N;
for(int i=0;i<=n+1;i++) st[i][0] = a[i];
for(int j=1;j<20;j++){
for(int i=0;i+(1 << (j-1))<N;i++){
st[i][j] = max(st[i][j-1], st[i+(1 << (j-1))][j-1]);
}
}
auto get = [&](int l, int r){
int lg = __lg(r - l + 1);
return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
};
for(int i=1;i<=n;i++){
{ int l = 0, r = i;
while(l < r){
int m = (l + r + 1) >> 1;
if(get(m, i) > a[i]) l = m;
else r = m - 1;
} par[i][0] = l;
}
{ int l = 0, r = i;
while(l < r){
int m = (l + r + 1) >> 1;
if(get(m, i) >= a[i] * 2) l = m;
else r = m - 1;
} p2[i][0] = l;
}
{ int l = i, r = n + 1;
while(l < r){
int m = (l + r) >> 1;
if(get(i, m) > a[i]) r = m;
else l = m + 1;
} par[i][1] = l;
}
{ int l = i, r = n + 1;
while(l < r){
int m = (l + r) >> 1;
if(get(i, m) >= a[i] * 2) r = m;
else l = m + 1;
} p2[i][1] = l;
}
}
set<ar<int, 2>> ss;
auto del = [&](int l, int r){
tree.add(l, r, -1);
ss.erase({l, r});
};
auto add = [&](int l, int r){
tree.add(l, r, 1);
ss.insert({l, r});
};
auto check = [&](int l, int r){
if(a[r+1] > pref[r] - pref[l-1] && a[l-1] > pref[r] - pref[l-1]){
add(l, r);
return true;
} return false;
};
par[n+1][1] = N, par[0][0] = 0;
for(int i=1;i<=n;i++){
int j = par[i][1];
int mx = i;
while(j-1<=n-(i == 1)){
// cout<<mx<<" "<<j<<endl;
check(i, j-1);
if(p2[mx][1] == j){
mx = j;
j = par[j][1];
} else {
int v = j;
j = p2[mx][1];
mx = v;
}
}
}
// for(auto x : ss){
// cout<<x[0]<<" "<<x[1]<<"\n";
// }
// cout<<"\n";
int q; cin>>q;
while(q--){
int t; cin>>t;
if(t == 1){
assert(false);
} else {
int l, r; cin>>l>>r;
int L = l, R = r;
{
int j=par[l][1], mx = l;
while(j<=r){
if(pref[j-1] - pref[l-1] < a[j]) L = j;
if(p2[mx][1] == j){
mx = j;
j = par[j][1];
} else {
int v = j;
j = p2[mx][1];
mx = v;
}
}
}
{
int j=par[r][0], mx = r;
while(l <= j){
if(pref[r] - pref[j] < a[j]) R = j;
if(p2[mx][0] == j){
mx = j;
j = par[j][0];
} else {
int v = j;
j = p2[mx][0];
mx = v;
}
}
}
// cout<<L<<" "<<R<<"\n";
cout<<tree.get(L, R)[1]<<"\n";
}
}
}
/*
5
6 4 2 2 6
2
2 1 5
2 1 3
*/
Compilation message
fish2.cpp: In function 'int main()':
fish2.cpp:113:7: warning: variable 'del' set but not used [-Wunused-but-set-variable]
113 | auto del = [&](int l, int r){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
40652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
20092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
40652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
20092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
20092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
40652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
