#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;
for (pair<ll, pll> p:b.pre)
if (a.sum+p.fi<p.se.fi)
resa=0, ans.pre.pb({a.sum+p.fi, {p.se.fi, p.se.se+a.len}});
for (pair<ll, pll> p:a.suf)
if (p.fi+b.sum<p.se.fi)
resb=0, ans.suf.pb({p.fi+b.sum, {p.se.fi, p.se.se+b.len}});
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())
resa+=a.suf.back().se.se-(lo==0?0:a.suf[lo-1].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())
resb+=b.pre.back().se.se-(lo==0?0:b.pre[lo-1].se.se);
break;
}
ptrb++, lo=ptrb;
}
}
ans.ans=resa+resb;
// if (a.len!=0 && b.len!=0)
// {
// cout << a.len << " " << b.len << " " << a.ans << " " << b.ans << " " << a.sum << " " << b.sum << "\n";
// for (pair<ll, pll> i:a.suf) cout << i.fi << " " << i.se.fi << " " << i.se.se << "\n";
// for (pair<ll, pll> i:b.pre) cout << i.fi << " " << i.se.fi << " " << i.se.se << "\n";
// cout << "ans " << resa << " " << resb << "\n";
// }
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:45: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]
45 | while (ptra<a.suf.size())
| ~~~~^~~~~~~~~~~~~
fish2.cpp:49: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]
49 | 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:49: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]
49 | 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:51: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]
51 | 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:51: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]
51 | 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: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]
55 | if (ptra==a.suf.size())
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:57: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]
57 | if (ptrb==b.pre.size())
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:67: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]
67 | while (ptrb<b.pre.size())
| ~~~~^~~~~~~~~~~~~
fish2.cpp:71: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]
71 | 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:71: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]
71 | 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:73: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]
73 | 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:73: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]
73 | 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:77: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]
77 | if (ptrb==b.pre.size())
| ~~~~^~~~~~~~~~~~~~
fish2.cpp:79: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]
79 | if (ptra==a.suf.size())
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
464 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
89 ms |
53564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
464 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
89 ms |
53564 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 |
Incorrect |
89 ms |
53564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
464 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
