hdu5306(线段树＋区间取最值)jls线段树

jls论文：

根据上面论文我们就可以做这题了。

终于学会了jls线段树。

手敲了下，看懂理论1h，写+bug就花了不到1h。

果然线段树我还是比较熟练的

马上搞下camp树套jls树。。。

#include<bits/stdc++.h>
using namespace std;
#define ls o*2
#define rs o*2+1
typedef long long ll;
const int M=1e6+7;
ll mx[M<<2];//最大值 
ll se[M<<2];//次大值 
ll nm[M<<2];//最大值个数
ll sm[M<<2];//区间和
ll lz[M<<2];//懒标记，即该区间要与lzo 取min 
ll a[M];
void pu(int o,int l,int r)//合并左右子树 
{
	sm[o]=sm[ls]+sm[rs];
    mx[o]=max(mx[ls],mx[rs]);
    se[o]=max(se[ls],se[rs]);
	nm[o]=0;
    if(mx[ls]!=mx[rs]) se[o]=max(se[o],min(mx[ls],mx[rs]));
    if(mx[o]==mx[ls]) nm[o]+=nm[ls];
    if(mx[o]==mx[rs]) nm[o]+=nm[rs];
}
void bd(int o,int l,int r)
{
	lz[o]=se[o]=-1;
	if(l==r)
	{
		mx[o]=sm[o]=a[l];nm[o]=1;
		return ;
	}
	int m=(l+r)/2;
	bd(ls,l,m);
	bd(rs,m+1,r);
	pu(o,l,r);
}
void pd(int o,int l,int r)
{
	if(lz[o]==-1)return ;
	if(lz[o]<mx[ls])//只有取min的值小于最大值才有意义 
	{
		sm[ls]=sm[ls]+(lz[o]-mx[ls])*nm[ls];
		mx[ls]=lz[ls]=lz[o];
	}
	if(lz[o]<mx[rs])
	{
		sm[rs]=sm[rs]+(lz[o]-mx[rs])*nm[rs];
		mx[rs]=lz[rs]=lz[o];
	}
}
void up(int o,int l,int r,int x,int y,int v)//区间与x取min
{
	if(v>=mx[o])return ;
	int m=(l+r)/2;
	if(x<=l&&r<=y)
	{
		if(v>se[o])
		{
			sm[o]=sm[o]+(v-mx[o])*nm[o];
			mx[o]=lz[o]=v;//之前标记对这次标记没有影响，所以可以直接赋值 
			return ;
		}
		else if(l==r)return ;//叶子节点就不能拆分区间 了 
	}
	pd(o,l,r);
	if(x<=m)up(ls,l,m,x,y,v);
	if(y>m)up(rs,m+1,r,x,y,v);
	pu(o,l,r);
}
ll quma(int o,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		return mx[o];
	}
	pd(o,l,r);
	int m=(l+r)/2;
	ll mx=0;
	if(x<=m)mx=max(mx,quma(ls,l,m,x,y));
	if(y>m)mx=max(mx,quma(rs,m+1,r,x,y));
	return mx;
}
ll qusm(int o,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		return sm[o];
	}
	pd(o,l,r);
	int m=(l+r)/2;
	ll ans=0;
	if(x<=m)ans+=qusm(ls,l,m,x,y);
	if(y>m)ans+=qusm(rs,m+1,r,x,y);
	return ans;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		bd(1,1,n);
		while(m--)
		{
			int opt,x,y,v;
			scanf("%d",&opt);
			if(opt==0)
			{
				scanf("%d%d%d",&x,&y,&v);
				up(1,1,n,x,y,v);
			}
			else if(opt==1)
			{
				scanf("%d%d",&x,&y);
				printf("%lld\n",quma(1,1,n,x,y));
			}
			else
			{
				scanf("%d%d",&x,&y);
				printf("%lld\n",qusm(1,1,n,x,y));
			}
		}
	}
	return 0;
 }