#pragma once
#include"../basic/template.hpp"classSegTreeBeats{unsignedintn;std::vector<lint>width,min[2],minc,max[2],maxc,sum,lazy;voideval(intk){if(n-1<=k)return;if(lazy[k]){update_node_add(2*k+1,lazy[k]);update_node_add(2*k+2,lazy[k]);lazy[k]=0;}if(max[0][k]<max[0][2*k+1]){update_node_max(2*k+1,max[0][k]);}if(min[0][k]>min[0][2*k+1]){update_node_min(2*k+1,min[0][k]);}if(max[0][k]<max[0][2*k+2]){update_node_max(2*k+2,max[0][k]);}if(min[0][k]>min[0][2*k+2]){update_node_min(2*k+2,min[0][k]);}}voidcombine(intk){sum[k]=sum[2*k+1]+sum[2*k+2];if(min[0][2*k+1]<min[0][2*k+2]){min[0][k]=min[0][2*k+1];minc[k]=minc[2*k+1];min[1][k]=std::min(min[1][2*k+1],min[0][2*k+2]);}elseif(min[0][2*k+1]>min[0][2*k+2]){min[0][k]=min[0][2*k+2];minc[k]=minc[2*k+2];min[1][k]=std::min(min[0][2*k+1],min[1][2*k+2]);}else{min[0][k]=min[0][2*k+1];minc[k]=minc[2*k+1]+minc[2*k+2];min[1][k]=std::min(min[1][2*k+1],min[1][2*k+2]);}if(max[0][2*k+1]>max[0][2*k+2]){max[0][k]=max[0][2*k+1];maxc[k]=maxc[2*k+1];max[1][k]=std::max(max[1][2*k+1],max[0][2*k+2]);}elseif(max[0][2*k+1]<max[0][2*k+2]){max[0][k]=max[0][2*k+2];maxc[k]=maxc[2*k+2];max[1][k]=std::max(max[0][2*k+1],max[1][2*k+2]);}else{max[0][k]=max[0][2*k+1];maxc[k]=maxc[2*k+1]+maxc[2*k+2];max[1][k]=std::max(max[1][2*k+1],max[1][2*k+2]);}}voidupdate_node_max(intk,lintx){sum[k]+=(x-max[0][k])*maxc[k];if(max[0][k]==min[0][k])min[0][k]=x;elseif(max[0][k]==min[1][k])min[1][k]=x;max[0][k]=x;}voidupdate_node_min(intk,lintx){sum[k]+=(x-min[0][k])*minc[k];if(min[0][k]==max[0][k])max[0][k]=x;elseif(min[0][k]==max[1][k])max[1][k]=x;min[0][k]=x;}voidupdate_node_add(intk,lintx){min[0][k]+=x;if(min[1][k]!=LINF)min[1][k]+=x;max[0][k]+=x;if(max[1][k]!=-LINF)max[1][k]+=x;sum[k]+=x*width[k];lazy[k]+=x;}public:SegTreeBeats(unsignedintsize,lintdef=0){*this=SegTreeBeats(std::vector<lint>(size,def));}SegTreeBeats(std::vector<lint>initvec){n=1;while(n<initvec.size())n*=2;width.resize(2*n-1);min[0].resize(2*n-1);min[1].resize(2*n-1,LINF);minc.resize(2*n-1);max[0].resize(2*n-1);max[1].resize(2*n-1,-LINF);maxc.resize(2*n-1);sum.resize(2*n-1);lazy.resize(2*n-1);for(inti=n-1;i<n-1+initvec.size();i++){min[0][i]=max[0][i]=sum[i]=initvec[i-n+1];minc[i]=maxc[i]=1;}for(inti=n-2;i>=0;i--){combine(i);}width[0]=n;REP(i,2*n-2)width[i]=width[(i-1)/2]/2;}voidupdate_chmin(inta,intb,lintx,intk=0,intl=0,intr=-1){if(r==-1)r=n;if(b<=l||r<=a||max[0][k]<=x)return;if(a<=l&&r<=b&&max[1][k]<x){update_node_max(k,x);return;}eval(k);update_chmin(a,b,x,2*k+1,l,(l+r)/2);update_chmin(a,b,x,2*k+2,(l+r)/2,r);combine(k);}voidupdate_chmax(inta,intb,lintx,intk=0,intl=0,intr=-1){if(r==-1)r=n;if(b<=l||r<=a||x<=min[0][k])return;if(a<=l&&r<=b&&x<min[1][k]){update_node_min(k,x);return;}eval(k);update_chmax(a,b,x,2*k+1,l,(l+r)/2);update_chmax(a,b,x,2*k+2,(l+r)/2,r);combine(k);}voidupdate_add(inta,intb,lintx,intk=0,intl=0,intr=-1){if(r==-1)r=n;if(b<=l||r<=a)return;if(a<=l&&r<=b){update_node_add(k,x);return;}eval(k);update_add(a,b,x,2*k+1,l,(l+r)/2);update_add(a,b,x,2*k+2,(l+r)/2,r);combine(k);}voidupdate(inta,intb,lintx){update_chmin(a,b,x);update_chmax(a,b,x);}lintquery_sum(inta,intb,intk=0,intl=0,intr=-1){if(r==-1)r=n;if(b<=l||r<=a)return0;if(a<=l&&r<=b)returnsum[k];eval(k);lintvl=query_sum(a,b,2*k+1,l,(l+r)/2);lintvr=query_sum(a,b,2*k+2,(l+r)/2,r);returnvl+vr;}lintquery_min(inta,intb,intk=0,intl=0,intr=-1){if(r==-1)r=n;if(b<=l||r<=a)returnLINF;if(a<=l&&r<=b)returnmin[0][k];eval(k);lintvl=query_min(a,b,2*k+1,l,(l+r)/2);lintvr=query_min(a,b,2*k+2,(l+r)/2,r);returnstd::min(vl,vr);}lintquery_max(inta,intb,intk=0,intl=0,intr=-1){if(r==-1)r=n;if(b<=l||r<=a)return-LINF;if(a<=l&&r<=b)returnmax[0][k];eval(k);lintvl=query_max(a,b,2*k+1,l,(l+r)/2);lintvr=query_max(a,b,2*k+2,(l+r)/2,r);returnstd::max(vl,vr);}};/**
* @title Segment Tree Beats
*/