#include <bits/stdc++.h>
using namespace std;
bool st3;
int n,q;
long long arr[100005];
struct node{
int s,e,m;
pair<long long,int> val;
node *l,*r;
node(int S, int E){
s=S; e=E; m=(s+e)/2;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
val=max(l->val,r->val);
}
else val={arr[s],s};
}
pair<long long,int> query(int S, int E){
if(S<=s&&e<=E) return val;
if(E<=m) return l->query(S,E);
else if(S>m) return r->query(S,E);
else return max(l->query(S,m),r->query(m+1,E));
}
} *root;
vector<pair<int,int> > bad;
pair<int,int> nxt[2][100005];
pair<pair<int,int>,int> twok[2][20][100005];
long long pref[100005];
void recons(){
pref[0]=0;
for(int i=1; i<=n; i++) pref[i]=pref[i-1]+arr[i];
bad.clear();
vector<pair<long long,int> > mono={{1e9,0}};
for(int i=1; i<=n; i++){
while(!mono.empty()&&mono.back().first<arr[i]){
if(mono.back().second<i-1&&pref[i-1]-pref[mono.back().second]<min(arr[i],mono.back().first)){
bad.push_back({mono.back().second+1,i-1});
}
mono.pop_back();
}
if(mono.back().second<i-1&&pref[i-1]-pref[mono.back().second]<min(arr[i],mono.back().first)){
bad.push_back({mono.back().second+1,i-1});
}
mono.push_back({arr[i],i});
}
while(!mono.empty()){
if(mono.back().second<n&&pref[n]-pref[mono.back().second]<mono.back().first){
bad.push_back({mono.back().second+1,n});
}
mono.pop_back();
}
//for(auto i:bad) cout << i.first << ' ' << i.second << '\n';
for(int i=0; i<=n; i++) nxt[0][i]=nxt[1][i]={-1,-1};
for(auto i:bad){
if(i.first>1){
if(nxt[0][i.first-1].first==-1||nxt[0][i.first-1].second<i.second) nxt[0][i.first-1]=i;
}
if(i.second<n){
if(nxt[1][i.second+1].first==-1||nxt[1][i.second+1].first>i.first) nxt[1][i.second+1]=i;
}
}
pair<int,int> cur={-1,-1};
for(int i=1; i<=n; i++){
if(nxt[1][i].first==-1) nxt[1][i]=cur;
else cur=nxt[1][i];
}
cur={-1,-1};
for(int i=n; i>0; i--){
if(nxt[0][i].first==-1) nxt[0][i]=cur;
else cur=nxt[0][i];
}
if(!st3){
for(int i=0; i<2; i++) for(int j=0; j<20; j++) for(int k=0; k<=n; k++) twok[i][j][k]={{-1,-1},-1};
for(int i=1; i<=n; i++){
twok[0][0][i]={nxt[0][i],nxt[0][i].second-nxt[0][i].first+1};
twok[1][0][i]={nxt[1][i],nxt[1][i].second-nxt[1][i].first+1};
}
for(int i=0; i<19; i++){
for(int j=1; j<=n; j++){
if(twok[0][i][j].first.first!=-1){
twok[0][i+1][j].first=twok[0][i][twok[0][i][j].first.second+1].first;
twok[0][i+1][j].second=twok[0][i][j].second+twok[0][i][twok[0][i][j].first.second+1].second;
}
if(twok[1][i][j].first.first!=-1){
twok[1][i+1][j].first=twok[1][i][twok[1][i][j].first.first-1].first;
twok[1][i+1][j].second=twok[1][i][j].second+twok[1][i][twok[1][i][j].first.first-1].second;
}
}
}
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=1; i<=n; i++) cin >> arr[i];
cin >> q;
if(q<=1000) st3=true;
else{
st3=false;
root=new node(1,n);
}
recons();
while(q--){
int cmd;
cin >> cmd;
if(cmd==1){
int x;
long long y;
cin >> x >> y;
arr[x]=y;
recons();
}
else{
int a,b;
cin >> a >> b;
if(!st3){
int big=root->query(a,b).second;
int tbad=0;
int cur=big;
for(int i=19; i>=0; i--){
if(twok[0][i][cur].first.first!=-1&&twok[0][i][cur].first.second<=b){
tbad+=twok[0][i][cur].second;
cur=twok[0][i][cur].first.second+1;
}
}
if(twok[0][0][cur].first.first!=-1&&twok[0][0][cur].first.first<=b){
assert(twok[0][0][cur].first.second>b);
tbad+=b-twok[0][0][cur].first.first+1;
}
cur=big;
for(int i=19; i>=0; i--){
if(twok[1][i][cur].first.first!=-1&&twok[1][i][cur].first.first>=a){
tbad+=twok[1][i][cur].second;
cur=twok[1][i][cur].first.first-1;
}
}
if(twok[1][0][cur].first.first!=-1&&twok[1][0][cur].first.second>=a){
assert(twok[0][0][cur].first.first<a);
tbad+=twok[1][0][cur].first.second-a+1;
}
cout << b-a+1-tbad << '\n';
}
else{
int wall=a;
for(int i=a; i<=b; i++){
if(arr[i]-pref[i-1]+pref[a-1]>0) wall=i;
}
a=wall;
wall=b;
for(int i=b; i>=a; i--){
if(arr[i]-pref[b]+pref[i]>0) wall=i;
}
b=wall;
pair<long long,int> big={-1,-1};
for(int i=a; i<=b; i++) big=max(big,make_pair(arr[i],i));
int tbad=0;
int cur=big.second;
while(cur<=b){
if(nxt[0][cur].first==-1) break;
if(nxt[0][cur].second<=b){
tbad+=nxt[0][cur].second-nxt[0][cur].first+1;
cur=nxt[0][cur].second+1;
}
else if(nxt[0][cur].first<=b){
tbad+=b-nxt[0][cur].first+1;
break;
}
else break;
}
cur=big.second;
while(cur>=a){
if(nxt[1][cur].first==-1) break;
if(nxt[1][cur].first>=a){
tbad+=nxt[1][cur].second-nxt[1][cur].first+1;
cur=nxt[1][cur].first-1;
}
else if(nxt[1][cur].second>=a){
tbad+=nxt[1][cur].second-a+1;
break;
}
else break;
}
cout << b-a+1-tbad << '\n';
}
}
}
}
# | 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... |