int dp[21][__];
void rmq(int n)
{
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<(j-1))<=n;i++)
dp[j][i]=min(dp[j-1][i],dp[j-1][i+(1<<(j-1))]);
}
int findmin(int l,int r)
{
int k=(int)log2(r-l+1);
return min(dp[k][l],dp[k][r-(1<<k)+1]);
}
rmq(n);
struct SegmentTree
{
static const int __=100005;
ll val;int n,ql,qr;
struct node
{
ll val,st,ad;
node() {}
void set(ll v,ll s,ll a)
{
val=v,st=s,ad=a;
}
//改
void putset(int tl,int tr,ll v)
{
set((tr-tl+1)*v,v,0);
}
//改
void putadd(int tl,int tr,ll v)
{
val+=v*(tr-tl+1);
if(st)st+=v;
else ad+=v;
}
}t[__<<2];
//改
void pushup(int x,int tl,int tm,int tr)
{
t[x].val=t[x<<1].val+t[x<<1|1].val;
}
void build(int _n){n=_n;build(1,1,n);}
void build(int x,int tl,int tr)
{
if(tl==tr)t[x].set(a[tl],0,0);
else
{
int tm=(tl+tr)>>1;
build(x<<1,tl,tm);
build(x<<1|1,tm+1,tr);
pushup(x,tl,tm,tr);
}
}
void pushdown(int x,int tl,int tm,int tr)
{
if(t[x].st)
{
t[x<<1].putset(tl,tm,t[x].st);
t[x<<1|1].putset(tm+1,tr,t[x].st);
t[x].st=0;
}
if(t[x].ad)
{
t[x<<1].putadd(tl,tm,t[x].ad);
t[x<<1|1].putadd(tm+1,tr,t[x].ad);
t[x].ad=0;
}
}
bool cut(int x,int tl,int tr)
{
return ql>tr || qr<tl;
}
bool check(int x,int tl,int tr)
{
return ql<=tl && tr<=qr;
}
void set(int _ql,int _qr,ll _val)
{
ql=_ql,qr=_qr,val=_val;
_set(1,1,n);
}
void _set(int x,int tl,int tr)
{
if(cut(x,tl,tr))return;
if(check(x,tl,tr))
{
t[x].putset(tl,tr,val);
return;
}
int tm=(tl+tr)>>1;
pushdown(x,tl,tm,tr);
_set(x<<1,tl,tm);
_set(x<<1|1,tm+1,tr);
pushup(x,tl,tm,tr);
}
void add(int _ql,int _qr,ll _val)
{
ql=_ql,qr=_qr,val=_val;
_add(1,1,n);
}
void _add(int x,int tl,int tr)
{
if(cut(x,tl,tr))return;
if(check(x,tl,tr))
{
t[x].putadd(tl,tr,val);
return;
}
int tm=(tl+tr)>>1;
pushdown(x,tl,tm,tr);
_add(x<<1,tl,tm);
_add(x<<1|1,tm+1,tr);
pushup(x,tl,tm,tr);
}
ll get_val(int _ql,int _qr)
{
ql=_ql,qr=_qr;
return _get_val(1,1,n);
}
//改
ll _get_val(int x,int tl,int tr)
{
if(cut(x,tl,tr))return 0;
if(check(x,tl,tr))return t[x].val;
ll res=0;int tm=(tl+tr)>>1;
pushdown(x,tl,tm,tr);
res+=_get_val(x<<1,tl,tm);
res+=_get_val(x<<1|1,tm+1,tr);
pushup(x,tl,tm,tr);
return res;
}
}T;
段树(扫描线)
struct SegmentTree
{
static const int __=1e5+5;
typedef double type;
type a[__];int n;
struct seg
{
type val,len;
int times;
seg() {}
seg(type l,type v,int t) {set(l,v,t);}
void set(type l,type v,int t)
{
len=l,val=v,times=t;
}
}t[__<<2];
void pushup(int x)
{
if(t[x].times)
t[x].val=t[x].len;
else
t[x].val=t[x<<1].val+t[x<<1|1].val;
}
void build(int x=1,int tl=1,int tr=-1)
{
if(tr==-1)tr=n;
if(tl+1==tr)t[x].set(a[tr]-a[tl],0,0);
else
{
int tm=(tl+tr)>>1;
build(x<<1,tl,tm);
build(x<<1|1,tm,tr);
t[x].len=t[x<<1].len+t[x<<1|1].len;
pushup(x);
}
}
void add(type ql,type qr,int v)
{
int l=lower_bound(a+1,a+1+n,ql)-a;
int r=lower_bound(a+1,a+1+n,qr)-a;
add(l,r,v,1,1,n);
}
void add(int ql,int qr,int v,int x,int tl,int tr)
{
if(ql>=tr || qr<=tl)return;
if(ql<=tl && tr<=qr)
{
t[x].times+=v;
pushup(x);
return;
}
int tm=(tl+tr)>>1;
add(ql,qr,v,x<<1,tl,tm);
add(ql,qr,v,x<<1|1,tm,tr);
pushup(x);
}
type get_sum() {return t[1].val;}
}T;
点树(扫描线)
struct SegmentTree
{
static const int __=1e5+5;
typedef ll type;
type a[__];int n;
struct seg
{
type val,len;
ll times;
seg() {}
seg(type l,type v,ll t) {set(l,v,t);}
void set(type l,type v,ll t)
{
len=l,val=v,times=t;
}
}t[__<<2];
void pushup(int x)
{
if(!t[x].times)t[x].val=0;
else t[x].val=t[x].times;
t[x].val+=max(t[x<<1].val,t[x<<1|1].val);
}
void build(int x=1,int tl=1,int tr=-1)
{
if(tr==-1)tr=n;
if(tl==tr)t[x].set(0,0,0);
else
{
int tm=(tl+tr)>>1;
build(x<<1,tl,tm);
build(x<<1|1,tm+1,tr);
t[x].len=t[x<<1].len+t[x<<1|1].len;
pushup(x);
}
}
void add(type ql,type qr,ll v)
{
int l=lower_bound(a+1,a+1+n,ql)-a;
int r=lower_bound(a+1,a+1+n,qr)-a;
add(l,r,v,1,1,n);
}
void add(int ql,int qr,ll v,int x,int tl,int tr)
{
if(ql>tr || qr<tl)return;
if(ql<=tl && tr<=qr)
{
t[x].times+=v;
pushup(x);
return;
}
int tm=(tl+tr)>>1;
add(ql,qr,v,x<<1,tl,tm);
add(ql,qr,v,x<<1|1,tm+1,tr);
pushup(x);
}
type get_sum() {return t[1].val;}
}T;
区间合并
struct SegmentTree
{
const static int __=1e5+5;
int n,ql,qr;
struct node
{
int tl,tr,v,lv,rv;
node() {}
void set(int l,int r){tl=l,tr=r;}
void set(int _v,int _lv,int _rv)
{
v=_v,lv=_lv,rv=_rv;
}
int length(){return tr-tl+1;}
void clear() {v=lv=rv=0;}
}t[__<<2];
node pushup(node &ls,node &rs)
{
if(!ls.v)return rs;
if(!rs.v)return ls;
int lv=ls.lv,rv=rs.rv,v=max(ls.v,rs.v);
if(a[ls.tr]==a[rs.tl])
{
if(ls.lv==ls.length())
lv+=rs.lv;
if(rs.rv==rs.length())
rv+=ls.rv;
v=max(v,ls.rv+rs.lv);
}
node res;
res.set(ls.tl,rs.tr);
res.set(v,lv,rv);
return res;
}
void build(int _n){build(1,1,n=_n);}
void build(int x,int tl,int tr)
{
t[x].set(tl,tr);
if(tl==tr){t[x].set(1,1,1);return;}
int tm=(tl+tr)>>1;
build(x<<1,tl,tm);
build(x<<1|1,tm+1,tr);
t[x]=pushup(t[x<<1],t[x<<1|1]);
}
int get_val(int _ql,int _qr)
{
ql=_ql,qr=_qr;
return get_val(1).v;
}
node get_val(int x)
{
if(ql<=t[x].tl && t[x].tr<=qr)
return t[x];
int tm=(t[x].tl+t[x].tr)>>1;
node l,r;
l.clear(),r.clear();
if(ql<=tm)l=get_val(x<<1);
if(qr>tm)r=get_val(x<<1|1);
return pushup(l,r);
}
}T;
