/***********************************************************
When you are inspired by passion
and you want to live for the current moment
When your every thought and action
has the power to become the story of your future
When difficulties stand to demolish your Glory
Just remember that Life is a 'Golden adverse Story'
Withstand it to acheive your passion and dreams
more amazingly more easily.
Why then? When writing the story of your Life
You want to Let someone else hold your pen
huzaifa242©
***********************************************************/
#include <bits/stdc++.h>
using namespace std;
//#define int int64_t use for 64-bit integers
#define int int32_t //use for 32-bit integers
#define MAX 100005
#define x first
#define y second
//for 64-bit change 1e9 to 1e18
const int inf=1e9;
int seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l=0,int r=INT_MAX)
{return uniform_int_distribution<int>(l,r)(rng);}
template <typename T,typename G>
ostream& operator << (ostream& out, const pair<T,G> &a)
{return out<<"("<<a.x<<" , "<<a.y<<")";}
template <typename T>
ostream& operator << (ostream& out, const vector<T> &a)
{out<<"[";for(const auto &i:a)out<<i<<" , ";return out<<"]"<<endl;}
template <typename T>
ostream& operator << (ostream& out, const set<T> &a)
{out<<"{";for(const auto &i:a)out<<i<<" , ";return out<<"}"<<endl;}
template <typename T,typename G>
ostream& operator << (ostream& out, const map<T,G> &a)
{out<<"<";for(const auto &i:a)out<<i<<" , ";return out<<">"<<endl;}
template<typename T, size_t N>
typename enable_if<!is_same<typename remove_cv<T>::type, char>::value,
ostream&>::type operator<<(ostream& out, T(&a)[N])
{out<<'[';for(size_t i=0;i<N;++i)out<<a[i]<<" , ";out <<"]"<<endl;return out;}
class ConvexHull_trick_Semi{
private:
class line{
private:
int m,c;
long double xlft;
public:
explicit line(int _m=0,int _c=0){
m=_m;
c=_c;
xlft=-inf;
}
int getc() const
{ return c; }
int getm() const
{ return m; }
void setxlft(long double lf)
{ xlft=lf; }
long double getxlft() const
{ return xlft; }
int gety( int x) const
{ return m*x +c; }
bool isparallel(line ll) const
{ return m==ll.m; }
long double intersectX(line ll) const
{ return isparallel(ll)?inf:(1.0*(c-ll.c))/(ll.m-m); }
};
bool maxQ;
public:
vector<line> hull;
ConvexHull_trick_Semi(){}
ConvexHull_trick_Semi(bool mq){
maxQ=mq;
}
bool useless(line l1, line l2, line l3)
{ return l1.intersectX(l3) <= l1.intersectX(l2); }
void addline(int m,int c){
line ll;
if(maxQ)
ll=line(-m,-c);
else
ll=line(m,c);
while(hull.size()>=2 && useless(hull[hull.size()-2],hull[hull.size()-1],ll))
hull.pop_back();
if(hull.size()){
long double dst=hull.back().intersectX(ll);
ll.setxlft(dst);
}
hull.push_back(ll);
}
int query(int x){
int ll=0,rr=hull.size()-1,mm,aa=0;
while(ll<=rr){
mm=(ll+rr)/2;
if(hull[mm].getxlft()<= (1.0 * x)){
aa=mm;
ll=mm+1;
}else
rr=mm-1;
}
return (maxQ?-hull[aa].gety(x):hull[aa].gety(x));
}
};
/* It is assumed that B can take positive and negative values
If is non-negative change implementation of query in
convexhulltrick class.
*/
//each bucket stores a convex hull, lazy b, and lazy constant a-L*b
struct bkt{
ConvexHull_trick_Semi poly;
int b,c;
};
class sqrt_decomposition{
private:
int bksz,tbk,n;
//sqan is the array of buckets
vector<bkt> sqan;
//vals is the actual array on which we are operating
vector<int> vals;
public:
sqrt_decomposition(int size){
n=size;
bksz=sqrt(n);
tbk=(n%bksz==0?n/bksz:(n/bksz)+1);
sqan.resize(tbk);
vals.assign(n,0);
}
void sqan_init(){
int i;
for(i=0;i<tbk;i++){
sqan[i].poly=ConvexHull_trick_Semi(true);
sqan[i].b=0;
sqan[i].c=0;
}
for(i=0;i<n;i++){
sqan[i/bksz].poly.addline(i+1,vals[i]);
}
}
void update(int l, int r, int a, int b){
int fix=a-(l+1)*b;
int i,bs,be,ans,s,e;
bs=(l)/bksz+1;
be=(r)/bksz;
s=((l)/bksz)*bksz;
//l to starting of first bucket
sqan[bs-1].poly.hull.clear();
for(i=s;i<bs*bksz;i++){
vals[i]+=(sqan[bs-1].c + (i+1)*sqan[bs-1].b);
sqan[bs-1].c=0;
sqan[bs-1].b=0;
if(i<l){
sqan[bs-1].poly.addline(i+1,vals[i]);
}else{
vals[i]+=a+(i-l)*b;
sqan[bs-1].poly.addline(i+1,vals[i]);
}
}
//all the bucket jumps
for(i=bs;i<be;i++){
sqan[i].b+=b;
sqan[i].c+=fix;
}
e=min((be+1)*bksz,n);
//last bucket to r
sqan[be].poly.hull.clear();
for(i=be*bksz;i<e;i++){
vals[i]+=(sqan[be].c + (i+1)*sqan[be].b);
sqan[be].c=0;
sqan[be].b=0;
if(i<=r){
vals[i]+=a+(i-l)*b;
sqan[be].poly.addline(i+1,vals[i]);
}else{
sqan[be].poly.addline(i+1,vals[i]);
}
}
}
int query(int l,int r){
int i,bs,be,ans=INT_MIN,s,e;
bs=(l)/bksz+1;
be=(r)/bksz;
s=((l)/bksz)*bksz;
for(i=l;i<=min(bs*bksz-1,r);i++){
ans=max(ans,(i+1)*sqan[bs-1].b + vals[i] + sqan[bs-1].c);
}
for(i=bs;i<be;i++){
ans=max(ans,sqan[i].poly.query(sqan[i].b) + sqan[i].c);
}
e=min((be+1)*bksz,n);
for(i=max(be*bksz,l);i<=r;i++){
ans=max(ans,(i+1)*sqan[be].b + vals[i] + sqan[be].c);
}
return ans;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,q;
cin>>n>>q;
sqrt_decomposition sq(n);
sq.sqan_init();
while(q--){
int c;
cin>>c;
if(c==1){
int l,r,a,b;
cin>>l>>r>>a>>b;
sq.update(l-1,r-1,a,b);
}else{
int l,r;
cin>>l>>r;
int ans=sq.query(l-1,r-1);
cout<<ans<<"\n";
}
}
return 0;
}
LyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCglXaGVuIHlvdSBhcmUgaW5zcGlyZWQgYnkgcGFzc2lvbiAKCWFuZCB5b3Ugd2FudCB0byBsaXZlIGZvciB0aGUgY3VycmVudCBtb21lbnQKCglXaGVuIHlvdXIgZXZlcnkgdGhvdWdodCBhbmQgYWN0aW9uCgloYXMgdGhlIHBvd2VyIHRvIGJlY29tZSB0aGUgc3Rvcnkgb2YgeW91ciBmdXR1cmUKCglXaGVuIGRpZmZpY3VsdGllcyBzdGFuZCB0byBkZW1vbGlzaCB5b3VyIEdsb3J5CglKdXN0IHJlbWVtYmVyIHRoYXQgTGlmZSBpcyBhICdHb2xkZW4gYWR2ZXJzZSBTdG9yeScKCglXaXRoc3RhbmQgaXQgdG8gYWNoZWl2ZSB5b3VyIHBhc3Npb24gYW5kIGRyZWFtcwoJbW9yZSBhbWF6aW5nbHkgbW9yZSBlYXNpbHkuCgoJV2h5IHRoZW4/IFdoZW4gd3JpdGluZyB0aGUgc3Rvcnkgb2YgeW91ciBMaWZlCglZb3Ugd2FudCB0byBMZXQgc29tZW9uZSBlbHNlIGhvbGQgeW91ciBwZW4KCgkJCQkJaHV6YWlmYTI0MsKpCgoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8vI2RlZmluZSBpbnQgaW50NjRfdCB1c2UgZm9yIDY0LWJpdCBpbnRlZ2VycwojZGVmaW5lIGludCBpbnQzMl90IC8vdXNlIGZvciAzMi1iaXQgaW50ZWdlcnMKI2RlZmluZSBNQVggMTAwMDA1CiNkZWZpbmUgeCBmaXJzdCAKI2RlZmluZSB5IHNlY29uZAoKLy9mb3IgNjQtYml0IGNoYW5nZSAxZTkgdG8gMWUxOApjb25zdCBpbnQgaW5mPTFlOTsKCmludCBzZWVkOwptdDE5OTM3IHJuZyhzZWVkPWNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CmlubGluZSBpbnQgcm5kKGludCBsPTAsaW50IHI9SU5UX01BWCkKe3JldHVybiB1bmlmb3JtX2ludF9kaXN0cmlidXRpb248aW50PihsLHIpKHJuZyk7fQoKdGVtcGxhdGUgPHR5cGVuYW1lIFQsdHlwZW5hbWUgRz4Kb3N0cmVhbSYgb3BlcmF0b3IgPDwgKG9zdHJlYW0mIG91dCwgY29uc3QgcGFpcjxULEc+ICZhKSAKe3JldHVybiBvdXQ8PCIoIjw8YS54PDwiICwgIjw8YS55PDwiKSI7fQoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+Cm9zdHJlYW0mIG9wZXJhdG9yIDw8IChvc3RyZWFtJiBvdXQsIGNvbnN0IHZlY3RvcjxUPiAmYSkgCntvdXQ8PCJbIjtmb3IoY29uc3QgYXV0byAmaTphKW91dDw8aTw8IiAsICI7cmV0dXJuIG91dDw8Il0iPDxlbmRsO30KCnRlbXBsYXRlIDx0eXBlbmFtZSBUPgpvc3RyZWFtJiBvcGVyYXRvciA8PCAob3N0cmVhbSYgb3V0LCBjb25zdCBzZXQ8VD4gJmEpIAp7b3V0PDwieyI7Zm9yKGNvbnN0IGF1dG8gJmk6YSlvdXQ8PGk8PCIgLCAiO3JldHVybiBvdXQ8PCJ9Ijw8ZW5kbDt9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVCx0eXBlbmFtZSBHPgpvc3RyZWFtJiBvcGVyYXRvciA8PCAob3N0cmVhbSYgb3V0LCBjb25zdCBtYXA8VCxHPiAmYSkgCntvdXQ8PCI8Ijtmb3IoY29uc3QgYXV0byAmaTphKW91dDw8aTw8IiAsICI7cmV0dXJuIG91dDw8Ij4iPDxlbmRsO30KCnRlbXBsYXRlPHR5cGVuYW1lIFQsIHNpemVfdCBOPgp0eXBlbmFtZSBlbmFibGVfaWY8IWlzX3NhbWU8dHlwZW5hbWUgcmVtb3ZlX2N2PFQ+Ojp0eXBlLCBjaGFyPjo6dmFsdWUsCm9zdHJlYW0mPjo6dHlwZSBvcGVyYXRvcjw8KG9zdHJlYW0mIG91dCwgVCgmYSlbTl0pCntvdXQ8PCdbJztmb3Ioc2l6ZV90IGk9MDtpPE47KytpKW91dDw8YVtpXTw8IiAsICI7b3V0IDw8Il0iPDxlbmRsO3JldHVybiBvdXQ7fQoKY2xhc3MgQ29udmV4SHVsbF90cmlja19TZW1pewoJcHJpdmF0ZToKCWNsYXNzIGxpbmV7CgkJcHJpdmF0ZToKCQlpbnQgbSxjOwoJCWxvbmcgZG91YmxlIHhsZnQ7CgkJcHVibGljOgoJCWV4cGxpY2l0IGxpbmUoaW50IF9tPTAsaW50IF9jPTApewoJCQltPV9tOwoJCQljPV9jOwoJCQl4bGZ0PS1pbmY7CgkJfQoJCWludCBnZXRjKCkgY29uc3QKCQl7IHJldHVybiBjOyB9CgkJaW50IGdldG0oKSBjb25zdCAKCQl7IHJldHVybiBtOyB9CgkJdm9pZCBzZXR4bGZ0KGxvbmcgZG91YmxlIGxmKQoJCXsgeGxmdD1sZjsgfQoJCWxvbmcgZG91YmxlIGdldHhsZnQoKSBjb25zdAoJCXsgcmV0dXJuIHhsZnQ7IH0KCQlpbnQgZ2V0eSggaW50IHgpIGNvbnN0IAoJCXsgcmV0dXJuIG0qeCArYzsgfQoJCWJvb2wgaXNwYXJhbGxlbChsaW5lIGxsKSBjb25zdAoJCXsgcmV0dXJuIG09PWxsLm07IH0KCQlsb25nIGRvdWJsZSBpbnRlcnNlY3RYKGxpbmUgbGwpIGNvbnN0IAoJCXsgcmV0dXJuIGlzcGFyYWxsZWwobGwpP2luZjooMS4wKihjLWxsLmMpKS8obGwubS1tKTsgfQoJfTsKCWJvb2wgbWF4UTsKCXB1YmxpYzoKCXZlY3RvcjxsaW5lPiBodWxsOwoJQ29udmV4SHVsbF90cmlja19TZW1pKCl7fQoJQ29udmV4SHVsbF90cmlja19TZW1pKGJvb2wgbXEpewoJCW1heFE9bXE7Cgl9Cglib29sIHVzZWxlc3MobGluZSBsMSwgbGluZSBsMiwgbGluZSBsMykKCXsgcmV0dXJuIGwxLmludGVyc2VjdFgobDMpIDw9IGwxLmludGVyc2VjdFgobDIpOyB9Cgl2b2lkIGFkZGxpbmUoaW50IG0saW50IGMpewoJCWxpbmUgbGw7CgkJaWYobWF4USkKCQkJbGw9bGluZSgtbSwtYyk7CgkJZWxzZQoJCQlsbD1saW5lKG0sYyk7CgkJd2hpbGUoaHVsbC5zaXplKCk+PTIgJiYgdXNlbGVzcyhodWxsW2h1bGwuc2l6ZSgpLTJdLGh1bGxbaHVsbC5zaXplKCktMV0sbGwpKQoJCQlodWxsLnBvcF9iYWNrKCk7CgkJaWYoaHVsbC5zaXplKCkpewoJCQlsb25nIGRvdWJsZSBkc3Q9aHVsbC5iYWNrKCkuaW50ZXJzZWN0WChsbCk7IAoJCQlsbC5zZXR4bGZ0KGRzdCk7CgkJfQoJCWh1bGwucHVzaF9iYWNrKGxsKTsKCX0KCWludCBxdWVyeShpbnQgeCl7CgkJaW50IGxsPTAscnI9aHVsbC5zaXplKCktMSxtbSxhYT0wOwoJCXdoaWxlKGxsPD1ycil7CgkJCW1tPShsbCtycikvMjsKCQkJaWYoaHVsbFttbV0uZ2V0eGxmdCgpPD0gKDEuMCAqIHgpKXsKCQkJCWFhPW1tOwoJCQkJbGw9bW0rMTsKCQkJfWVsc2UKCQkJCXJyPW1tLTE7CgkJfQoJCXJldHVybiAobWF4UT8taHVsbFthYV0uZ2V0eSh4KTpodWxsW2FhXS5nZXR5KHgpKTsKCX0KfTsKCi8qICBJdCBpcyBhc3N1bWVkIHRoYXQgQiBjYW4gdGFrZSBwb3NpdGl2ZSBhbmQgbmVnYXRpdmUgdmFsdWVzCglJZiBpcyBub24tbmVnYXRpdmUgY2hhbmdlIGltcGxlbWVudGF0aW9uIG9mIHF1ZXJ5IGluIAoJY29udmV4aHVsbHRyaWNrIGNsYXNzLgoqLwoKLy9lYWNoIGJ1Y2tldCBzdG9yZXMgYSBjb252ZXggaHVsbCwgbGF6eSBiLCBhbmQgbGF6eSBjb25zdGFudCBhLUwqYgoKc3RydWN0IGJrdHsKCUNvbnZleEh1bGxfdHJpY2tfU2VtaSBwb2x5OwoJaW50IGIsYzsKfTsKY2xhc3Mgc3FydF9kZWNvbXBvc2l0aW9uewoJcHJpdmF0ZToKCWludCBia3N6LHRiayxuOwoJLy9zcWFuIGlzIHRoZSBhcnJheSBvZiBidWNrZXRzCgl2ZWN0b3I8Ymt0PiBzcWFuOwoJLy92YWxzIGlzIHRoZSBhY3R1YWwgYXJyYXkgb24gd2hpY2ggd2UgYXJlIG9wZXJhdGluZwoJdmVjdG9yPGludD4gdmFsczsKCXB1YmxpYzoKCXNxcnRfZGVjb21wb3NpdGlvbihpbnQgc2l6ZSl7CgkJbj1zaXplOwoJCWJrc3o9c3FydChuKTsKCQl0Yms9KG4lYmtzej09MD9uL2Jrc3o6KG4vYmtzeikrMSk7CgkJc3Fhbi5yZXNpemUodGJrKTsKCQl2YWxzLmFzc2lnbihuLDApOwoJfQoJdm9pZCBzcWFuX2luaXQoKXsKCQlpbnQgaTsKCQlmb3IoaT0wO2k8dGJrO2krKyl7CgkJCXNxYW5baV0ucG9seT1Db252ZXhIdWxsX3RyaWNrX1NlbWkodHJ1ZSk7CgkJCXNxYW5baV0uYj0wOwoJCQlzcWFuW2ldLmM9MDsKCQl9CgkJZm9yKGk9MDtpPG47aSsrKXsKCQkJc3FhbltpL2Jrc3pdLnBvbHkuYWRkbGluZShpKzEsdmFsc1tpXSk7CgkJfQoJfQoJdm9pZCB1cGRhdGUoaW50IGwsIGludCByLCBpbnQgYSwgaW50IGIpewoJCWludCBmaXg9YS0obCsxKSpiOwoJCWludCBpLGJzLGJlLGFucyxzLGU7CgkJYnM9KGwpL2Jrc3orMTsKCQliZT0ocikvYmtzejsKCQlzPSgobCkvYmtzeikqYmtzejsKCQkvL2wgdG8gc3RhcnRpbmcgb2YgZmlyc3QgYnVja2V0CgkJc3Fhblticy0xXS5wb2x5Lmh1bGwuY2xlYXIoKTsKCQlmb3IoaT1zO2k8YnMqYmtzejtpKyspewoJCQl2YWxzW2ldKz0oc3Fhblticy0xXS5jICsgKGkrMSkqc3Fhblticy0xXS5iKTsKCQkJc3Fhblticy0xXS5jPTA7CgkJCXNxYW5bYnMtMV0uYj0wOwoJCQlpZihpPGwpewoJCQkJc3Fhblticy0xXS5wb2x5LmFkZGxpbmUoaSsxLHZhbHNbaV0pOwoJCQl9ZWxzZXsKCQkJCXZhbHNbaV0rPWErKGktbCkqYjsKCQkJCXNxYW5bYnMtMV0ucG9seS5hZGRsaW5lKGkrMSx2YWxzW2ldKTsKCQkJfQoJCX0KCQkvL2FsbCB0aGUgYnVja2V0IGp1bXBzCgkJZm9yKGk9YnM7aTxiZTtpKyspewoJCQlzcWFuW2ldLmIrPWI7CgkJCXNxYW5baV0uYys9Zml4OyAKCQl9CgkJZT1taW4oKGJlKzEpKmJrc3osbik7CgkJLy9sYXN0IGJ1Y2tldCB0byByCgkJc3FhbltiZV0ucG9seS5odWxsLmNsZWFyKCk7CgkJZm9yKGk9YmUqYmtzejtpPGU7aSsrKXsKCQkJdmFsc1tpXSs9KHNxYW5bYmVdLmMgKyAoaSsxKSpzcWFuW2JlXS5iKTsKCQkJc3FhbltiZV0uYz0wOwoJCQlzcWFuW2JlXS5iPTA7CgkJCWlmKGk8PXIpewoJCQkJdmFsc1tpXSs9YSsoaS1sKSpiOwoJCQkJc3FhbltiZV0ucG9seS5hZGRsaW5lKGkrMSx2YWxzW2ldKTsKCQkJfWVsc2V7CgkJCQlzcWFuW2JlXS5wb2x5LmFkZGxpbmUoaSsxLHZhbHNbaV0pOwoJCQl9CgkJfQoJfQoJaW50IHF1ZXJ5KGludCBsLGludCByKXsKCQlpbnQgaSxicyxiZSxhbnM9SU5UX01JTixzLGU7CgkJYnM9KGwpL2Jrc3orMTsKCQliZT0ocikvYmtzejsKCQlzPSgobCkvYmtzeikqYmtzejsKCQlmb3IoaT1sO2k8PW1pbihicypia3N6LTEscik7aSsrKXsKCQkJYW5zPW1heChhbnMsKGkrMSkqc3Fhblticy0xXS5iICsgdmFsc1tpXSArIHNxYW5bYnMtMV0uYyk7CgkJfQoJCWZvcihpPWJzO2k8YmU7aSsrKXsKCQkJYW5zPW1heChhbnMsc3FhbltpXS5wb2x5LnF1ZXJ5KHNxYW5baV0uYikgKyBzcWFuW2ldLmMpOwoJCX0KCQllPW1pbigoYmUrMSkqYmtzeixuKTsKCQlmb3IoaT1tYXgoYmUqYmtzeixsKTtpPD1yO2krKyl7CgkJCWFucz1tYXgoYW5zLChpKzEpKnNxYW5bYmVdLmIgKyB2YWxzW2ldICsgc3FhbltiZV0uYyk7CgkJfQoJCXJldHVybiBhbnM7ICAgICAKCX0KfTsKCnNpZ25lZCBtYWluKCl7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoTlVMTCk7Y291dC50aWUoTlVMTCk7CgkjaWZuZGVmIE9OTElORV9KVURHRQoJCWZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKTsKCQlmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsgIAoJI2VuZGlmCglpbnQgbixxOwoJY2luPj5uPj5xOwoJc3FydF9kZWNvbXBvc2l0aW9uIHNxKG4pOwoJc3Euc3Fhbl9pbml0KCk7Cgl3aGlsZShxLS0pewoJCWludCBjOwoJCWNpbj4+YzsKCQlpZihjPT0xKXsKCQkJaW50IGwscixhLGI7CgkJCWNpbj4+bD4+cj4+YT4+YjsKCQkJc3EudXBkYXRlKGwtMSxyLTEsYSxiKTsKCQl9ZWxzZXsKCQkJaW50IGwscjsKCQkJY2luPj5sPj5yOwoJCQlpbnQgYW5zPXNxLnF1ZXJ5KGwtMSxyLTEpOwoJCQljb3V0PDxhbnM8PCJcbiI7CgkJfQoJfQoJcmV0dXJuIDA7Cn0K