hdu5306.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;

struct node{
	int max, snd, cnt;
	lint sum;
}tree[2100000];
int n, m, a[1000005];

void push(int p){
	int v = tree[p].max;
	if(tree[2*p].max > v){
		tree[2*p].sum += 1ll * (v - tree[2*p].max) * tree[2*p].cnt;
		tree[2*p].max = v;
	}
	if(tree[2*p+1].max > v){
		tree[2*p+1].sum += 1ll * (v - tree[2*p+1].max) * tree[2*p+1].cnt;
		tree[2*p+1].max = v;
	}
}

void pull(int p){
	tree[p].sum = tree[2*p].sum + tree[2*p+1].sum;
	tree[p].max = max(tree[2*p].max, tree[2*p+1].max);
	tree[p].snd = max(tree[2*p].snd, tree[2*p+1].snd);
	if(tree[2*p].max < tree[2*p+1].max){
		tree[p].snd = max(tree[p].snd, tree[2*p].max);
	}
	if(tree[2*p].max > tree[2*p+1].max){
		tree[p].snd = max(tree[p].snd, tree[2*p+1].max);
	}
	tree[p].cnt = 0;
	if(tree[p].max == tree[2*p].max) tree[p].cnt += tree[2*p].cnt;
	if(tree[p].max == tree[2*p+1].max) tree[p].cnt += tree[2*p+1].cnt;
}

void init(int s, int e, int p){
	if(s == e){
		tree[p] = {a[s], -1, 1, a[s]};
		return;
	}
	int m = (s+e)/2;
	init(s, m, 2*p);
	init(m+1, e, 2*p+1);
	pull(p);
}

void update(int s, int e, int ps, int pe, int p, int v){
	if(e < ps || pe < s || tree[p].max <= v) return;
	if(s <= ps && pe <= e && tree[p].snd < v){
		tree[p].sum += 1ll * (v - tree[p].max) * tree[p].cnt;
		tree[p].max = v;
		return;
	}
	push(p);
	int pm = (ps + pe) / 2;
	update(s, e, ps, pm, 2*p, v);
	update(s, e, pm+1, pe, 2*p+1, v);
	pull(p);
}

lint getsum(int s, int e, int ps, int pe, int p){
	if(e < ps || pe < s) return 0;
	if(s <= ps && pe <= e) return tree[p].sum;
	int pm = (ps + pe) / 2;
	push(p);
	return getsum(s, e, ps, pm, 2*p) + getsum(s, e, pm+1, pe, 2*p+1);
}

int getmax(int s, int e, int ps, int pe, int p){
	if(e < ps || pe < s) return 0;
	if(s <= ps && pe <= e) return tree[p].max;
	int pm = (ps + pe) / 2;
	push(p);
	return max(getmax(s, e, ps, pm, 2*p), getmax(s, e, pm+1, pe, 2*p+1));
}

int main(){
	int t;
	cin >> t;
	while(t--){
		scanf("%d %d",&n,&m);
		for(int i=1; i<=n; i++) scanf("%d",&a[i]);
		init(1, n, 1);
		while(m--){
			int t;
			scanf("%d",&t);
			if(t){
				int l, r;
				scanf("%d %d",&l,&r);
				if(t == 2) printf("%lld\n", getsum(l, r, 1, n, 1));
				else printf("%lld\n", getmax(l, r, 1, n, 1));
			}
			else{
				int s, e, x;
				scanf("%d %d %d",&s,&e,&x);
				update(s, e, 1, n, 1, x);
			}
		}
	}
}