#include <bits/stdc++.h>
//#define home
#ifndef home
#include "weirdtree.h"
#endif // home
using namespace std;
const long long oo = LLONG_MAX;
struct node
{
long long sum,Max1,fr,Max2;
};
int n,q;
int v[300005];
node ai[1200005];
long long lazy[1200005];
node Merge(node st, node dr)
{
node rez;
rez.sum = st.sum + dr.sum;
if(st.Max1==dr.Max1)
{
rez.Max1 = st.Max1;
rez.fr = st.fr + dr.fr;
rez.Max2 = max(st.Max2,dr.Max2);
return rez;
}
if(st.Max1 > dr.Max1)
{
rez.Max1 = st.Max1;
rez.fr = st.fr;
rez.Max2 = max(st.Max2,dr.Max1);
return rez;
}
rez.Max1 = dr.Max1;
rez.fr = dr.fr;
rez.Max2 = max(dr.Max2,st.Max1);
return rez;
}
void propag(int nod)
{
if(lazy[nod]==oo)
{
return;
}
if(ai[nod*2].Max1 > lazy[nod])
{
ai[nod*2].sum -= (ai[nod*2].Max1 - lazy[nod]) * ai[nod*2].fr;
ai[nod*2].Max1 = lazy[nod];
lazy[nod*2] = min(lazy[nod*2],lazy[nod]);
}
if(ai[nod*2+1].Max1 > lazy[nod])
{
ai[nod*2+1].sum -= (ai[nod*2+1].Max1 - lazy[nod]) * ai[nod*2+1].fr;
ai[nod*2+1].Max1 = lazy[nod];
lazy[nod*2+1] = min(lazy[nod*2+1],lazy[nod]);
}
lazy[nod] = oo;
}
void update_poz(int poz, long long val, int nod, int a, int b)
{
if(a==b)
{
ai[nod].sum = val;
ai[nod].Max1 = val;
ai[nod].fr = 1;
ai[nod].Max2 = INT_MIN;
return;
}
int mij = (a + b) >> 1;
propag(nod);
if(poz<=mij)
{
update_poz(poz,val,nod*2,a,mij);
}
else
{
update_poz(poz,val,nod*2+1,mij+1,b);
}
ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
}
void update(int ua, int ub, long long val, int nod, int a, int b)
{
if(ai[nod].Max1 < val)
{
return;
}
if(ua<=a && ub>=b && val > ai[nod].Max2)
{
ai[nod].sum -= (ai[nod].Max1 - val) * ai[nod].fr;
ai[nod].Max1 = val;
lazy[nod] = min(lazy[nod],val);
return;
}
propag(nod);
int mij = (a + b) >> 1;
if(ua<=mij)
{
update(ua,ub,val,nod*2,a,mij);
}
if(ub>mij)
{
update(ua,ub,val,nod*2+1,mij+1,b);
}
ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
}
node query(int qa, int qb, int nod, int a, int b)
{
if(qa<=a && qb>=b)
{
return ai[nod];
}
int mij = (a + b) >> 1;
propag(nod);
if(qa<=mij && qb>mij)
{
return Merge(query(qa,qb,nod*2,a,mij),query(qa,qb,nod*2+1,mij+1,b));
}
if(qa<=mij)
{
return query(qa,qb,nod*2,a,mij);
}
return query(qa,qb,nod*2+1,mij+1,b);
}
void preset(int nod, int a, int b)
{
lazy[nod] = oo;
ai[nod].fr = 0;
ai[nod].Max1 = 0;
ai[nod].Max2 = INT_MIN;
ai[nod].sum = 0;
if(a==b)
{
return;
}
int mij = (a + b) >> 1;
preset(nod*2,a,mij);
preset(nod*2+1,mij+1,b);
}
void cut(int l, int r, int k)
{
while(k > 0)
{
node val = query(l,r,1,1,n);
if((val.Max1 - val.Max2) * val.fr <= k)
{
k -= (val.Max1 - val.Max2) * val.fr;
update(l,r,val.Max2,1,1,n);
continue;
}
long long dif = k / val.fr;
k = k % val.fr;
if(val.Max1 - dif <= 0)
{
update(l,r,0,1,1,n);
break;
}
update(l,r,val.Max1-dif,1,1,n);
val = query(l,r,1,1,n);
if(k)
{
int st = l;
int dr = r;
int poz = 0;
while(st<=dr)
{
int mij = (st + dr) >> 1;
node aux = query(l,mij,1,1,n);
if(aux.Max1==val.Max1 && aux.fr>=k)
{
poz = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
update(l,poz,val.Max1-1,1,1,n);
k = 0;
}
}
}
void magic(int poz, int val)
{
update_poz(poz,val,1,1,n);
}
long long inspect(int l, int r)
{
return query(l,r,1,1,n).sum;
}
void initialize(int N, int Q, int *h)
{
n = N;
q = Q;
preset(1,1,n);
for(int i=1;i<=n;i++)
{
update_poz(i,h[i],1,1,n);
}
}
#ifdef home
signed main()
{
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
cin>>n>>q;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
initialize(n,q,v);
for(int i=1; i<=q; i++)
{
int tip;
cin>>tip;
if(tip==1)
{
int l,r,k;
cin>>l>>r>>k;
cut(l,r,k);
}
else if(tip==2)
{
int poz,val;
cin>>poz>>val;
magic(poz,val);
}
else
{
int l,r;
cin>>l>>r;
cout<<inspect(l,r)<<'\n';
}
}
return 0;
}
#endif // home
Compilation message
/usr/bin/ld: /tmp/ccuMUXjU.o: in function `main':
grader.cpp:(.text.startup+0xe2): undefined reference to `initialise(int, int, int*)'
collect2: error: ld returned 1 exit status
