# Cod sursa(job #2759715)

Utilizator Data 19 iunie 2021 23:39:31 Arbori de intervale 100 cpp-64 done Arhiva educationala 3.81 kb
``````#include <bits/stdc++.h>
#define pb push_back
#define int long long int
#define double long double
#define cin fin
#define cout fout
using namespace std;

ifstream fin("arbint.in");
ofstream fout("arbint.out");
template <class T>
class arbint
{
vector<T> lazy;
vector<T> tree;
const int NMAX;
T getmax( const T& val1, const T& val2)
{
if( val1>val2)
return val1;
return val2;
}
public:

arbint(int value): NMAX(4*value+9)
{
lazy.resize(NMAX);
tree.resize(NMAX);
}
void updateRangeUtil(int si, int ss, int se, int us,
int ue, const T& diff)
{
if (lazy[si] != 0)
{
tree[si] +=   lazy[si];
if (ss != se)
{
lazy[si * 2 ] += lazy[si];
lazy[si * 2 + 1] += lazy[si];
}
lazy[si] = 0;
}

if (ss > se || ss > ue || se < us)
return;
if (ss >= us && se <= ue)
{
tree[si] +=  diff;
if (ss != se)
{
lazy[si * 2 ] += diff;
lazy[si * 2 + 1] += diff;
}
return;
}

int mid = (ss + se) / 2;
updateRangeUtil(si * 2 , ss, mid, us, ue, diff);
updateRangeUtil(si * 2 + 1, mid + 1, se, us, ue, diff);
tree[si] = getmax(tree[si * 2 ] , tree[si * 2 + 1]);
}
void updateRange(int n, int us, int ue, const T& diff)
{
updateRangeUtil(1, 1, n , us, ue, diff);
}
T getMaxUtil(int ss, int se, int qs, int qe, int si)
{
if (lazy[si] != 0)
{
tree[si] +=  lazy[si];
if (ss != se)
{
lazy[si * 2 ] += lazy[si];
lazy[si * 2 + 1] += lazy[si];
}

lazy[si] = 0;
}

if (ss > se || ss > qe || se < qs)
return 0;

if (ss >= qs && se <= qe)
return tree[si];

int mid = (ss + se) / 2;
return getmax( getMaxUtil(ss, mid, qs, qe, 2 * si ) ,
getMaxUtil(mid + 1, se, qs, qe, 2 * si + 1) );
}
T getMax(int n, int qs, int qe)
{
if (qs < 1 || qe > n  || qs > qe)
{
printf("Invalid Input");
return -1;
}

return getMaxUtil(1, n , qs, qe, 1);
}
void constructSTUtil(const vector<T>& arr, int ss, int se, int si)
{
if (ss > se)
return;
if (ss == se)
{
tree[si] = arr[ss];
return;
}

int mid = (ss + se) / 2;
constructSTUtil(arr, ss, mid, si * 2 );
constructSTUtil(arr, mid + 1, se, si * 2 + 1);

tree[si] = getmax( tree[si * 2 ] , tree[si * 2 + 1]);
}

void constructST(const vector<T>& arr, int n)
{
constructSTUtil(arr, 1, n , 1);
}
/*usage
vector<int>sol;
sol.push_back(0);
sol.push_back(numere);

arbint<int>a(sol.size()-1 + LAMBDA);
a.constructST(sol,sol.size()-1);
a.getMax(sol.size()-1,st,dr);

*/
};
int32_t main()
{
vector < arbint<int> > v;
vector< int> sol={0};
int n,m,i;
cin>>n>>m;
for(i=1;i<=n;i++)
{
int x;
cin>>x;
sol.push_back(x);

}
arbint<int> a(n);
a.constructST(sol,n);
v.push_back(a);
for(i=1;i<=m;i++)
{
int c,x,y;
cin>>c>>x>>y;
if(c==0)
{
cout<<v[0].getMax(n,x,y)<<'\n';
}
else
{
int value;
value= v[0].getMax(n,x,x);
v[0].updateRange(n,x,x, y-value);
}
}
return 0;
}``````