#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
int N;
vll A;
int Q;
struct group
{
int i; //inclusive of the group, not the barrier.
ll Asum;
int winners;
};
struct info
{
int l;
int r;
ll Asum;
int winners;
vector<group> pref;
vector<group> suff;
info()
{
;
}
info(int i)
{
l = r = i;
Asum = A[i];
winners = 1;
}
};
void combine(info& res, const info& X, const info& Y) //!
{
// cerr << "combine called\n";
res.l = X.l;
res.r = Y.r;
res.Asum = X.Asum + Y.Asum;
res.winners = 0;
int Xs = sz(X.suff);
ll Xdp[1 + Xs];
Xdp[0] = A[X.r];
for(int i = 1; i <= Xs; i++)
Xdp[i] = max(Xdp[i-1], A[X.suff[i-1].i - 1] - X.suff[i-1].Asum);
int Ys = sz(Y.pref);
ll Ydp[1 + Ys];
Ydp[0] = A[Y.l];
for(int i = 1; i <= Ys; i++)
Ydp[i] = max(Ydp[i-1], A[Y.pref[i-1].i + 1] - Y.pref[i-1].Asum);
// cerr << "#\n";
int XYreach[1 + Xs];
int XXreach[1 + Xs];
int YXreach[1 + Ys];
int YYreach[1 + Ys];
int xi, yi;
yi = Ys;
for(xi = Xs; xi >= 0; xi--)
{
ll currsum = (xi == Xs ? X.Asum : X.suff[xi].Asum);
while(yi >= 0 && Ydp[yi] > currsum)
yi--;
ll Ygain;
if(yi == Ys)
Ygain = Y.Asum;
else if(yi == -1)
Ygain = 0;
else
Ygain = Y.pref[yi].Asum;
if(xi < Xs && currsum + Ygain >= A[X.suff[xi].i - 1])
{
XXreach[xi] = XXreach[xi+1];
XYreach[xi] = XYreach[xi+1];
}
else
{
XXreach[xi] = xi;
XYreach[xi] = yi;
}
}
// cerr << "#2\n";
xi = Xs;
for(yi = Ys; yi >= 0; yi--)
{
ll currsum = (yi == Ys ? Y.Asum : Y.pref[yi].Asum);
while(xi >= 0 && Xdp[xi] > currsum)
xi--;
ll Xgain;
if(xi == Xs)
Xgain = X.Asum;
else if(xi == -1)
Xgain = 0;
else
Xgain = X.suff[xi].Asum;
if(yi < Ys && currsum + Xgain >= A[Y.pref[yi].i + 1])
{
YYreach[yi] = YYreach[yi+1];
YXreach[yi] = YXreach[yi+1];
}
else
{
YYreach[yi] = yi;
YXreach[yi] = xi;
}
}
// cerr << "#3\n";
res.pref = X.pref;
int pi = sz(res.pref);
if(X.Asum < Ydp[0])
res.pref.push_back({X.r, X.Asum, 0});
for(int i = 0; i < sz(Y.pref); i++)
if(A[Y.pref[i].i + 1] > Y.pref[i].Asum + X.Asum)
res.pref.push_back({Y.pref[i].i, Y.pref[i].Asum + X.Asum, 0});
res.suff = Y.suff;
int si = sz(res.suff);
if(Y.Asum < Xdp[0])
res.suff.push_back({Y.l, Y.Asum, 0});
for(int i = 0; i < sz(X.suff); i++)
if(A[X.suff[i].i - 1] > X.suff[i].Asum + Y.Asum)
res.suff.push_back({X.suff[i].i, X.suff[i].Asum + Y.Asum, 0});
// cerr << "#4\n";
vpii newpref, newsuff;
for(xi = 0; xi <= Xs; xi++)
{
int xiwinners = (xi == Xs ? X.winners : X.suff[xi].winners);
if(XXreach[xi] == Xs && XYreach[xi] == Ys)
res.winners += xiwinners;
else if(XXreach[xi] == Xs)
{
newpref.push_back({XYreach[xi], xiwinners});
}
else if(XYreach[xi] == Ys)
newsuff.push_back({XXreach[xi], xiwinners});
}
// cerr << "#4-1\n";
for(yi = 0; yi <= Ys; yi++)
{
// cerr << "entered : " << yi << '\n';
int yiwinners = (yi == Ys ? Y.winners : Y.pref[yi].winners);
if(YXreach[yi] == Xs && YYreach[yi] == Ys)
res.winners += yiwinners;
else if(YXreach[yi] == Xs)
{
newpref.push_back({YYreach[yi], yiwinners});
}
else if(YYreach[yi] == Ys)
{
newsuff.push_back({YXreach[yi], yiwinners});
}
}
// cerr << "#5\n";
for(auto pr : newpref)
{
for(auto& respr : res.pref)
{
// assert(pr.first < sz(Y.pref));
if(pr.first == -1 && respr.i == X.r)
respr.winners += pr.second;
else if(pr.first != -1 && respr.i == Y.pref[pr.first].i)
respr.winners += pr.second;
}
}
// cerr << "hello\n";
for(auto sf : newsuff)
{
// cerr << sf.first << ' ' << sf.second << '\n';
for(auto& ressf : res.suff)
{
assert(sf.first < sz(X.suff));
// cerr << " " << ressf.i << ' ' << ressf.Asum << ' ' << ressf.winners << '\n';
// cerr << "sff = " << sf.first << '\n';
// cerr << X.suff[sf.first.i] << '\n';
if(sf.first == -1 && ressf.i == Y.l)
{
// cerr << "bye\n";
ressf.winners += sf.second;
// cerr << "bye done\n";
}
else if(sf.first != -1 && ressf.i == X.suff[sf.first].i)
{
// cerr << "bye2\n";
ressf.winners += sf.second;
}
}
}
// Y = info(1);
// return res;
// cerr << "combine end\n";
}
info combine(const info& A, const info& B)
{
info res;
combine(res, A, B);
return res;
}
struct segtree
{
info v;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
if(L == R)
v = info(L);
else
{
left = new segtree(L, (L+R)/2);
right = new segtree((L+R)/2+1, R);
combine(v, left->v, right->v);
}
}
void recompute(int I)
{
// cerr << "recompute : " << v.l << ' ' << v.r << ' ' << I << '\n';
if(v.l == v.r)
v = info(v.l);
else
{
if(I <= (v.l+v.r)/2)
left->recompute(I);
else
right->recompute(I);
// cerr << "###\n";
combine(v, left->v, right->v);
// cerr << "combine done\n";
}
// cerr << "done\n";
}
info range(int L, int R)
{
if(L <= v.l && v.r <= R)
return v;
else if(R <= (v.l+v.r)/2)
return left->range(L, R);
else if(L >= (v.l+v.r)/2+1)
return right->range(L, R);
else
return combine(left->range(L, R), right->range(L, R));
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
A = vll(1+N);
for(int i = 1; i <= N; i++)
cin >> A[i];
// cerr << "done\n";
segtree S(1, N);
// cerr << "done2\n";
cin >> Q;
for(int j = 1; j <= Q; j++)
{
int T;
cin >> T;
if(T == 1)
{
int X, Y;
cin >> X >> Y;
A[X] = Y;
S.recompute(X);
// cerr << "hello\n";
}
else
{
int L, R;
cin >> L >> R;
cout << S.range(L, R).winners << '\n';
}
}
}
Compilation message
fish2.cpp: In function 'void combine(info&, const info&, const info&)':
fish2.cpp:244:4: error: 'assert' was not declared in this scope
244 | assert(sf.first < sz(X.suff));
| ^~~~~~
fish2.cpp:4:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
3 | #include <algorithm>
+++ |+#include <cassert>
4 | using namespace std;
fish2.cpp:162:6: warning: unused variable 'pi' [-Wunused-variable]
162 | int pi = sz(res.pref);
| ^~
fish2.cpp:175:6: warning: unused variable 'si' [-Wunused-variable]
175 | int si = sz(res.suff);
| ^~
