This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q;
ll a[maxn], pref[maxn];
void input()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
cin >> q;
a[0] = 1e9 + 10;
a[n + 1] = 1e9 + 10;
}
vector < pair < int, int > > ranges;
void get_ranges()
{
for (int i = 1; i <= n; i ++)
pref[i] = pref[i - 1] + a[i];
pref[n + 1] = pref[n];
ranges.clear();
stack < int > st;
st.push(0);
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
if (pref[i - 1] - pref[st.top()] < a[i])
ranges.push_back({st.top() + 1, i - 1});
st.push(i);
}
while(!st.empty())
st.pop();
st.push(n + 1);
for (int i = n; i > 0; i --)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
if (pref[st.top() - 1] - pref[i] < a[i])
ranges.push_back({i + 1, st.top() - 1});
st.push(i);
}
}
int b[maxn];
struct node
{
int cnt, mx;
node(int _cnt = 0, int _mx = 1e9 + 10)
{
cnt = _cnt;
mx = _mx;
}
};
node tree[4 * maxn];
node merge_node(node lf, node rf)
{
if (lf.cnt == -1 || rf.mx < lf.mx)
return rf;
if (rf.cnt == -1 || lf.mx < rf.mx)
return lf;
return node(lf.cnt + rf.cnt, lf.mx);
}
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root].mx = b[left];
tree[root].cnt = 1;
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return node(-1, 1e9 + 10);
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_node(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
ll values[maxn];
struct segment_tree
{
ll tree[4 * maxn], lazy[4 * maxn];
void build_tree(int root, int left, int right)
{
lazy[root] = 0;
if (left == right)
{
tree[root] = values[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
void push_lazy(int root, int left, int right)
{
tree[root] += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void update_range(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] += val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
ll walk_left(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft || tree[root] <= val)
return n + 1;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (tree[root * 2] > val)
return walk_left(root * 2, left, mid, qleft, qright, val);
return walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
return min(walk_left(root * 2, left, mid, qleft, qright, val),
walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
ll walk_right(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft || tree[root] <= val)
return 0;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (tree[root * 2 + 1] > val)
return walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val);
return walk_right(root * 2, left, mid, qleft, qright, val);
}
return max(walk_right(root * 2, left, mid, qleft, qright, val),
walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
};
segment_tree left_tree, right_tree;
void solve_query(int left, int right)
{
//for (pair < int, int > cur : ranges)
// cout << cur.first << " : " << cur.second << endl;
/**int lb = left, rb = right;
for (int i = left; i <= right; i ++)
{
//if (a[i] > pref[i - 1] - pref[left - 1])
// lb = max(lb, i);
if (a[i] > pref[right] - pref[i])
rb = min(rb, i);
}*/
int lb = left_tree.walk_right(1, 1, n, left, right, - pref[left - 1]);
int rb = right_tree.walk_left(1, 1, n, left, right, pref[right]);
/**cout << lb << " " << a[left + 2] - pref[left + 1] << " " << " " << -pref[left - 1] << endl;
for (int i = 1; i <= n; i ++)
cout << pref[i] << " ";
cout << endl;*/
/**int minx = 1e9;
for (int i = lb; i <= rb; i ++)
minx = min(minx, b[i]);
int ans = 0;
for (int i = lb; i <= rb; i ++)
if (b[i] == minx)
ans ++;*/
cout << query(1, 1, n, lb, rb).cnt << endl;
}
void restructure()
{
get_ranges();
for (int i = 1; i <= n; i ++)
b[i] = 0;
for (pair < int, int > cur : ranges)
for (int i = cur.first; i <= cur.second; i ++)
b[i] ++;
build_tree(1, 1, n);
for (int i = 1; i <= n; i ++)
{
values[i] = a[i] - pref[i - 1];
}
left_tree.build_tree(1, 1, n);
for (int i = 1; i <= n; i ++)
{
values[i] = a[i] + pref[i];
}
right_tree.build_tree(1, 1, n);
}
void simulate()
{
restructure();
for (int i = 1; i <= q; i ++)
{
int type;
cin >> type;
if (type == 1)
{
int idx;
ll x;
cin >> idx >> x;
a[idx] = x;
restructure();
}
else
{
int l, r;
cin >> l >> r;
solve_query(l, r);
}
}
}
void solve()
{
input();
simulate();
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
speed();
solve();
return 0;
}
/*
12
32 32 4 1 1 1 1 4 4 16 32 128
1
2 8 10
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |