顺便一提，实际上可以做到$o(n)$，将坏区间按照$a_{l-1}$和$a_{r+1}$的大小关系分类即可
关于Subtask4，考虑如下做法——
对于询问$[L,R]$，内部的坏区间分为两类：
1.以$L,R$为端点（因为$a_{L-1}$和$a_{R+1}$被看作$\infty$）
这类区间可以用$P$过程求出，并记其中最大的区间分别为$[L,L')$和$(R',R]$
2.$\subseteq [L,R]$的全局坏区间（显然$a_{L-1}$和$a_{R+1}$被看作$\infty$仍是坏区间）
由于$[L,L')$和$(R',R]$已经被覆盖，即仅需考虑还与$[L',R']$有交的（全局）坏区间
性质1：坏区间两两包含或相离
反证法，假设坏区间$[l_{1},r_{1}]$和$[l_{2},r_{2}]$满足$l_{1}
结合坏区间的条件，分析$a_{l_{2}-1}$和$a_{r_{1}+1}$的大小关系，显然矛盾
推论1：坏区间中与$[L',R']$有交的区间均包含$[L',R']$或被$[L',R']$包含
（其实并不能根据性质1直接得到，但证明类似）
根据推论1，答案即$[L',R']$（在所有坏区间中）覆盖次数最少的位置数（最大的鱼总可以存活）
使用线段树维护覆盖次数即可，时间复杂度为$o(n\log n\log A+m\log n)$，可以通过
对于Subtask6，考虑如下做法——
在带修改时，显然$P$过程仍可以实现，进而问题即维护覆盖次数（也即坏区间）
假设修改为$a_{x}=y$，暴力找出所有与$x$相关的坏区间，并依次执行删除-修改-加入即可
具体的，与$x$相关的坏区间分为两类：
1.以$x\pm 1$为左/右端点，这类区间可以用$P$过程求出（并需要判定）
2.包含$x$，用$P$过程分别求出以$x$为端点时的左右端点（不以$x$为端点条件更严）
性质2：包含$x$的坏区间仅有$o(\log A)$个
结合性质1，这些区间也相互包含，按长度排序后每次权值和乘2，即得证
根据性质2，暴力枚举这$o(\log^{2}A)$个区间，其中仅有$o(\log A)$个会修改覆盖次数
时间复杂度为$o(n\log n\log A+m\log n\log A+m\log^{2}A)$，可以通过
1 #include
2 using namespace std;
3 #define N 100005
4 #define ll long long
5 #define pii pair
6 #define fi first
7 #define se second
8 #define L (k<<1)
9 #define R (L+1)
10 #define mid (l+r>>1)
11 int n,m,p,x,y,a[N];ll s[N];vector<int>vl,vr;
12 namespace TA{
13 ll f[N];
14 int lowbit(int k){
15 return (k&(-k));
16 }
17 void update(int k,int x){
18 while (k<=n)f[k]+=x,k+=lowbit(k);
19 }
20 ll query(int k){
21 ll ans=0;
22 while (k)ans+=f[k],k^=lowbit(k);
23 return ans;
24 }
25 void build(){
26 for(int i=1;i<=n;i++)f[i]=s[i]-s[i^lowbit(i)];
27 }
28 };
29 namespace Left{
30 ll tag[N<<2],mn[N<<2];
31 void build(int k,int l,int r){
32 if (l==r){
33 mn[k]=s[l]-a[l+1];
34 if (l==n)mn[k]=-1e16;
35 return;
36 }
37 build(L,l,mid),build(R,mid+1,r);
38 mn[k]=min(mn[L],mn[R]);
39 }
40 void update(int k,int l,int r,int x,int y,int z){
41 if ((l>y)||(x>r))return;
42 if ((x<=l)&&(r<=y)){
43 tag[k]+=z,mn[k]+=z;
44 return;
45 }
46 update(L,l,mid,x,y,z),update(R,mid+1,r,x,y,z);
47 mn[k]=min(mn[L],mn[R])+tag[k];
48 }
49 int query(int k,int l,int r,int x,ll y){
50 if ((rreturn 0;
51 y-=tag[k];if (l==r)return l;
52 int ans=query(L,l,mid,x,y);
53 if (!ans)ans=query(R,mid+1,r,x,y);
54 return ans;
55 }
56 void update(int k,int x){
57 update(1,1,n,k,n,x),update(1,1,n,k-1,k-1,-x);
58 }
59 void find(int l){
60 vl.clear();
61 ll s=TA::query(l-1);
62 while (1){
63 l=query(1,1,n,l,s);
64 if (!l)break;vl.push_back(l++);
65 }
66 }
67 };
68 namespace Right{
69 ll tag[N<<2],mx[N<<2];
70 void build(int k,int l,int r){
71 if (l==r){
72 mx[k]=s[l-1]+a[l-1];
73 if (l==1)mx[k]=1e16;
74 return;
75 }
76 build(L,l,mid),build(R,mid+1,r);
77 mx[k]=max(mx[L],mx[R]);
78 }
79 void update(int k,int l,int r,int x,int y,int z){
80 if ((l>y)||(x>r))return;
81 if ((x<=l)&&(r<=y)){
82 tag[k]+=z,mx[k]+=z;
83 return;
84 }
85 update(L,l,mid,x,y,z),update(R,mid+1,r,x,y,z);
86 mx[k]=max(mx[L],mx[R])+tag[k];
87 }
88 int query(int k,int l,int r,int x,ll y){
89 if ((l>x)||(mx[k]<=y))return 0;
90 y-=tag[k];if (l==r)return l;
91 int ans=query(R,mid+1,r,x,y);
92 if (!ans)ans=query(L,l,mid,x,y);
93 return ans;
94 }
95 void update(int k,int x){
96 update(1,1,n,k+1,n,x),update(1,1,n,k+1,k+1,x);
97 }
98 void find(int r){
99 vr.clear();
100 ll s=TA::query(r);
101 while (1){
102 r=query(1,1,n,r,s);
103 if (!r)break;vr.push_back(r--);
104 }
105 }
106 };
107 namespace Seg{
108 int cnt[N],tag[N<<2];
109 pii f[N<<2];
110 pii merge(pii x,pii y){
111 pii ans=min(x,y);
112 if (x.fi==y.fi)ans.se=x.se+y.se;
113 return ans;
114 }
115 void build(int k,int l,int r){
116 if (l==r){
117 f[k]=make_pair(cnt[l],1);
118 return;
119 }
120 build(L,l,mid),build(R,mid+1,r);
121 f[k]=merge(f[L],f[R]);
122 }
123 void update(int k,int l,int r,int x,int y,int z){
124 if ((l>y)||(x>r))return;
125 if ((x<=l)&&(r<=y)){
126 tag[k]+=z,f[k].fi+=z;
127 return;
128 }
129 update(L,l,mid,x,y,z),update(R,mid+1,r,x,y,z);
130 f[k]=merge(f[L],f[R]),f[k].fi+=tag[k];
131 }
132 pii query(int k,int l,int r,int x,int y){
133 if ((l>y)||(x>r))return make_pair(1e8,0);
134 if ((x<=l)&&(r<=y))return f[k];
135 pii ans=merge(query(L,l,mid,x,y),query(R,mid+1,r,x,y));
136 ans.fi+=tag[k];return ans;
137 }
138 void build(){
139 for(int i=1;i<=n;i++){
140 Left::find(i);
141 ll S=s[i-1]+a[i-1];if (i==1)S=1e16;
142 for(int j:vl)
143 if (TA::query(j)1]--;
144 }
145 for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
146 build(1,1,n);
147 }
148 void update(int k,int p){
149 Left::find(k+1),Right::find(k-1);
150 ll S1=TA::query(k)+a[k];
151 for(int i:vl)
152 if (TA::query(i)1,1,n,k+1,i,p);
153 ll S2=TA::query(k-1)-a[k];
154 for(int i:vr)
155 if (S21))update(1,1,n,i,k-1,p);
156 Left::find(k),Right::find(k);
157 for(int i:vl)s[i]=TA::query(i);
158 for(int i:vr)s[i-1]=TA::query(i-1);
159 for(int i:vl)
160 for(int j:vr){
161 ll S=s[i]-s[j-1];
162 if (((i==n)||(S1]))&&((j==1)||(S1])))update(1,1,n,j,i,p);
163 }
164 }
165 };
166 void init(){
167 for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
168 TA::build(),Left::build(1,1,n),Right::build(1,1,n),Seg::build();
169 }
170 void update(int k,int x){
171 Seg::update(k,-1),a[k]+=x;
172 TA::update(k,x),Left::update(k,x),Right::update(k,x),Seg::update(k,1);
173 }
174 int query(int l,int r){
175 Left::find(l),Right::find(r);
176 if (vl[0]1;
177 if (vr[0]>l){
178 reverse(vr.begin(),vr.end());
179 r=(*upper_bound(vr.begin(),vr.end(),l))-1;
180 }
181 return Seg::query(1,1,n,l,r).se;
182 }
183 int main(){
184 scanf("%d",&n);
185 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
186 init();
187 scanf("%d",&m);
188 for(int i=1;i<=m;i++){
189 scanf("%d%d%d",&p,&x,&y);
190 if (p==1)update(x,y-a[x]);
191 if (p==2)printf("%d\n",query(x,y));
192 }
193 return 0;
194 }