2017-12-12

【hdu5603】：Gorgeous Sequence

Problem Description

There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.

0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value.
1 x y: Print the maximum value of ai that x≤i≤y.
2 x y: Print the sum of ai that x≤i≤y.

Input

The first line of the input is a single integer T, indicating the number of testcases.

The first line contains two integers n and m denoting the length of the sequence and the number of operations.
The second line contains n separated integers a1,…,an (∀1≤i≤n,0≤ai<231).
Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).

It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000.

Output

For every operation of type 1 or 2, print one line containing the answer to the corresponding query.

Sample Input

1
5 5
1 2 3 4 5
1 1 5
2 1 5
0 3 5 3
1 1 5
2 1 5

Sample Output

5
15
3
12

Solution

题目大意就是维护一个区间支持
1.区间 [l,r] 对 x 取 min
2.区间查询最大值
3.区间查询和

emmm 没看题解前我只会打暴力
事实上
这tm就是一个xjb搞的线段树裸体23333

然后聪明的你一下子就想到了
1.维护一个区间最大值
2.维护一个区间次大值

然后对于一次修改 x，如果区间最大值还小于x 那么就可以直接return
如果x 小于最大值但是同时也大于等于次大值
我们可以直接将 $sum = cnt*(max-x)$ (cnt是这个区间中最大值出现的个数)

然后如果都不满足的话，我们只能老老实实的分治修改子区间
对于如何修改子区间，大佬们都可以直接dfs。
emmmm
其实貌似可以直接update，就将两个子区间的最大值改成本区间的最大值（和题目中的操作等价）

最后说一下pushup，pushdown
pushup在普通线段树的基础上要多维护一个次大值
和vijos的小白逛公园类似，可以在两个子区间里找一个较小的最大值就可以

pushdown的意义在于我们对一个区间进行了修改操作后，他的最大值要么不变或变小
此时我们还没有直接对他的子区间进行正确的修改。
对于子区间中大于当前修改后的最大值一定是不合法的
我们需要将两个区间的最大值更新为父亲区间的最大值（和题目中的操作等价）

两个操作都和题目中的操作等价，所以这问题个人认为会变简单很多。
复杂度我太菜了不会证明….大家可以移步一位大佬的博客
传送门

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read(){
	int rtn=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))rtn=(rtn<<1)+(rtn<<3)+ch-'0',ch=getchar();
	return rtn*f;
}
#define maxn (int)(1e6+10)
#define inf 1e9
namespace SegmentTree{
	inline void update(int,int,int,int,int,int);
	inline void pushdown(int,int,int);
	struct node{
		int max,cnt,sed;LL sum;
	}T[maxn<<3];
	inline void pushup(int p){
		T[p].sum=T[p<<1].sum+T[p<<1|1].sum;
		T[p].max=max(T[p<<1].max,T[p<<1|1].max);
		T[p].sed=-inf,T[p].cnt=0;
		if(T[p].max==T[p<<1].max)T[p].cnt+=T[p<<1].cnt;
		else if(T[p].max>T[p<<1].max)T[p].sed=T[p<<1].max;
		if(T[p].max==T[p<<1|1].max)T[p].cnt+=T[p<<1|1].cnt;
		else if(T[p].max>T[p<<1|1].max)T[p].sed=T[p<<1|1].max;
		T[p].sed=max(T[p].sed,max(T[p<<1].sed,T[p<<1|1].sed));
	}
	inline void build(int p,int l,int r){
		if(l==r){
			T[p].sum=T[p].max=read();T[p].cnt=1;T[p].sed=-inf;return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		pushup(p);
	}
	inline void update(int p,int lp,int rp,int l,int r,int v){
		int mid=lp+rp>>1;
		if(lp==l&&rp==r){
			if(v>=T[p].max)return;
			else if(v<T[p].max&&v>=T[p].sed){
				T[p].sum-=(LL)T[p].cnt*(T[p].max-v);
				T[p].max=v;return;
			}
			update(p<<1,lp,mid,l,mid,v);
			update(p<<1|1,mid+1,rp,mid+1,r,v);
			pushup(p);return;
		}
		pushdown(p,lp,rp);
		if(r<=mid)update(p<<1,lp,mid,l,r,v);
		else if(l>mid)update(p<<1|1,mid+1,rp,l,r,v);
		else update(p<<1,lp,mid,l,mid,v),update(p<<1|1,mid+1,rp,mid+1,r,v);
		pushup(p);
	}
	inline void pushdown(int p,int l,int r){
		int mid=l+r>>1;
		if(T[p].max<T[p<<1].max)update(p<<1,l,mid,l,mid,T[p].max);
		if(T[p].max<T[p<<1|1].max)update(p<<1|1,mid+1,r,mid+1,r,T[p].max);
	}
	inline LL query_sum(int p,int lp,int rp,int l,int r){
		if(lp==l&&rp==r)return T[p].sum;
		pushdown(p,lp,rp);
		int mid=lp+rp>>1;
		if(r<=mid)return query_sum(p<<1,lp,mid,l,r);
		else if(l>mid)return query_sum(p<<1|1,mid+1,rp,l,r);
		else return query_sum(p<<1,lp,mid,l,mid)+query_sum(p<<1|1,mid+1,rp,mid+1,r);
	}
	inline int query_max(int p,int lp,int rp,int l,int r){
		if(lp==l&&rp==r)return T[p].max;
		pushdown(p,lp,rp);
		int mid=lp+rp>>1;
		if(r<=mid)return query_max(p<<1,lp,mid,l,r);
		else if(l>mid)return query_max(p<<1|1,mid+1,rp,l,r);
		else return max(query_max(p<<1,lp,mid,l,mid),query_max(p<<1|1,mid+1,rp,mid+1,r));
	}
}using namespace SegmentTree;
int n,m;
int main(){
	int t=read();
	while(t--){
		n=read(),m=read();
		build(1,1,n);
		for(int i=1;i<=m;i++){
			int opt=read(),l=read(),r=read();
			if(opt==0)update(1,1,n,l,r,read());
			else if(opt==1)printf("%d\n",query_max(1,1,n,l,r));
			else if(opt==2)printf("%lld\n",query_sum(1,1,n,l,r));
		}
	}
	return 0;
}