#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
ll x[100005];
struct SegTree
{
struct Node
{
ll ans=0, sum=0, len;
vector <pair<ll, pll>> pre, suf;
Node(){}
Node(ll x)
{
ans=1, sum=x, len=1;
pre.pb({0, {x, 0}});
suf.pb({0, {x, 0}});
}
};
Node Merge(Node a, Node b)
{
Node ans;
ans.sum=a.sum+b.sum, ans.len=a.len+b.len;
ans.pre=vector <pair<ll, pll>> (a.pre.begin(), a.pre.end());
ans.suf=vector <pair<ll, pll>> (b.suf.begin(), b.suf.end());
ll resa=a.ans, resb=b.ans, reqa=0, reqb=0;
for (pair<ll, pll> p:a.suf)
reqb=max(reqb, p.se.fi-p.fi);
for (pair<ll, pll> p:b.pre)
reqa=max(reqa, p.se.fi-p.fi);
for (pair<ll, pll> p:b.pre)
if (a.sum+p.fi<p.se.fi)
ans.pre.pb({a.sum+p.fi, {p.se.fi, (p.fi>=reqb?p.se.se:0)+(resa?a.ans:0)}}), resa=0;
for (pair<ll, pll> p:a.suf)
if (p.fi+b.sum<p.se.fi)
ans.suf.pb({p.fi+b.sum, {p.se.fi, (p.fi>=reqa?p.se.se:0)+(resb?b.ans:0)}}), resb=0;
if (resa)
{
ll lo=0, ptra=0, ptrb=0;
while (ptra<a.suf.size())
{
while (1)
{
if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
ptra++;
else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
ptrb++;
else break;
}
if (ptra==a.suf.size())
{
if (ptrb==b.pre.size())
for (ll i=lo; i<ptra; i++)
resa+=a.suf[i].se.se;
break;
}
ptra++, lo=ptra;
}
}
if (resb)
{
ll lo=0, ptra=0, ptrb=0;
while (ptrb<b.pre.size())
{
while (1)
{
if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
ptra++;
else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
ptrb++;
else break;
}
if (ptrb==b.pre.size())
{
if (ptra==a.suf.size())
for (ll i=lo; i<ptrb; i++)
resb+=b.pre[i].se.se;
break;
}
ptrb++, lo=ptrb;
}
}
ans.ans=resa+resb;
return ans;
}
void build(ll i, ll Start, ll End)
{
if (Start==End)
{
St[i]=Node(x[Start]);
return;
}
ll mid=(Start+End)/2;
build(i*2, Start, mid);
build(i*2+1, mid+1, End);
St[i]=Merge(St[i*2], St[i*2+1]);
}
ll n;
vector <Node> St;
SegTree (ll n): n(n)
{
St.resize(n*4+1);
build(1, 1, n);
}
void update(ll i, ll Start, ll End, ll idx, ll x)
{
if (Start>idx || End<idx)
return;
if (Start==End)
{
St[i]=Node(x);
return;
}
ll mid=(Start+End)/2;
update(i*2, Start, mid, idx, x);
update(i*2+1, mid+1, End, idx, x);
St[i]=Merge(St[i*2], St[i*2+1]);
}
Node query(ll i, ll Start, ll End, ll l, ll r)
{
if (Start>=l && End<=r)
return St[i];
ll mid=(Start+End)/2;
if (mid<l) return query(i*2+1, mid+1, End, l, r);
if (mid+1>r) return query(i*2, Start, mid, l, r);
return Merge(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n; cin >> n;
for (ll i=1; i<=n; i++)
cin >> x[i];
SegTree A(n);
ll q; cin >> q;
for (ll i=1; i<=q; i++)
{
ll t, a, b; cin >> t >> a >> b;
if (t==1) A.update(1, 1, n, a, b);
else cout << A.query(1, 1, n, a, b).ans << "\n";
}
}
Compilation message
fish2.cpp: In member function 'SegTree::Node SegTree::Merge(SegTree::Node, SegTree::Node)':
fish2.cpp:49:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | while (ptra<a.suf.size())
| ~~~~^~~~~~~~~~~~~
fish2.cpp:53:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
| ~~~~^~~~~~~~~~~~~
fish2.cpp:53:66: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:55:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
| ~~~~^~~~~~~~~~~~~
fish2.cpp:55:71: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:59:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (ptra==a.suf.size())
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:61:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if (ptrb==b.pre.size())
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:72:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | while (ptrb<b.pre.size())
| ~~~~^~~~~~~~~~~~~
fish2.cpp:76:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
| ~~~~^~~~~~~~~~~~~
fish2.cpp:76:66: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:78:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
| ~~~~^~~~~~~~~~~~~
fish2.cpp:78:71: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:82:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if (ptrb==b.pre.size())
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:84:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (ptra==a.suf.size())
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
53404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
53404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
53404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
