#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define f first
#define s second
#define endl '\n'
#define vec vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define m_p make_pair
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
auto rng=bind(uniform_int_distribution<int>(0,1e9),mt19937(time(0)));
template<class T>bool umin(T &a,const T &b) {return (a>b?a=b,1:0);}
template<class T>bool umax(T &a,const T &b) {return (a<b?a=b,1:0);}
template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=1e5+1;
struct tr{
array<int,3> pref,suf;///mx,mn,size
int sz,ans;
tr(){
sz=0;ans=0;
for(int i=0;i<3;i++) pref[i]=suf[i]=0;
}
};
bool can(int x,int y,int a,int b){
return max(x,a)-min(y,b)>x-y+a-b;
}
tr mg(const tr &a,const tr &b){
tr c;
c.ans=a.ans+b.ans;
c.sz=a.sz+b.sz;
c.pref=a.pref;
c.suf=a.suf;
if(can(a.suf[0],a.suf[1],b.pref[0],b.pref[1])){
c.ans-=b.pref[0]-b.pref[1];
c.ans-=b.suf[0]-b.suf[1];
c.ans+=max(a.suf[0],b.pref[0])-min(a.suf[1],b.pref[1]);
// cerr<<"HERE" <<endl;
if(a.suf[2]==a.sz){
c.pref[0]=max(a.pref[0],b.pref[0]);
c.pref[1]=min(a.pref[1],b.pref[1]);
c.pref[2]=a.pref[2]+b.pref[2];
}
if(b.pref[2]==b.sz){
c.suf[0]=max(a.suf[0],b.suf[0]);
c.suf[1]=min(a.suf[1],b.suf[1]);
c.suf[2]=a.suf[2]+b.suf[2];
}
}
return c;
}
tr t[4*N];
void add(int id,int x,int v,int tl,int tr){
if(tl==tr){
for(int i=0;i<2;i++) t[v].pref[i]=t[v].suf[i]=x;
t[v].pref[2]=t[v].suf[2]=1;
t[v].sz=1;
return;
}
int tm=(tl+tr)>>1;
if(tm>=id) add(id,x,2*v,tl,tm);
else add(id,x,2*v+1,tm+1,tr);
t[v]=mg(t[2*v],t[2*v+1]);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,q;
cin>>n>>q;
vec<int>a;
for(int i=0;i<n;i++){
int x;cin>>x;add(i,x,1,0,n-1);
a.pb(x);
}
while(q--){
int l,r,x;
cin>>l>>r>>x;--l;--r;
for(int j=l;j<=r;j++){
add(j,a[j]+x,1,0,n-1);
a[j]+=x;
}
cout<<t[1].ans<<endl;
}
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
25272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
25272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
25272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
