【HDU - 5306】Gorgeous Sequence

题链

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma GCC optimize(2)
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define MS 1000009
#define INF 20000009
#define mod 1000000007
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define M 11431471
#define B 231
#define MM 37101101
#define BB 312

LL n,m,k;
LL sum[MS<<2]; // 区间和 
LL maxf[MS<<2]; // 区间最大值 
LL cntf[MS<<2]; // 区间最大值个数 
LL maxse[MS<<2]; // 区间第二大值 
LL lamaxf[MS<<2]; // la_区间最大值需加的数 

ll read(){
    char c=getchar();ll s=0,f=1;
    for(;!isdigit(c);c=getchar())if(c==‘-‘)f=-1;
    for(;isdigit(c);c=getchar())s=s*10+c-48;
    return s*f;
}

void push_up(int rt){
	sum[rt] = sum[ls] + sum[rs];
	maxf[rt] = max(maxf[ls],maxf[rs]);
	if(maxf[ls] == maxf[rs]){
		cntf[rt] = cntf[ls] + cntf[rs];
		maxse[rt] = max(maxse[ls],maxse[rs]); 
	} 
	else if(maxf[ls] > maxf[rs]){
		cntf[rt] = cntf[ls];
		maxse[rt] = max(maxse[ls],maxf[rs]);
	}
	else{
		cntf[rt] = cntf[rs];
		maxse[rt] = max(maxf[ls],maxse[rs]);
	}
}

void build(int l,int r,int rt){
	lamaxf[rt] = 0;
	if(l == r){
		LL x;
		x = read();
		sum[rt] = x;
		maxf[rt] = x;
		cntf[rt] = 1;
		maxse[rt] = -1e18;
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
	push_up(rt);
}

void update(int rt,LL val){
	sum[rt] += val*cntf[rt];
	maxf[rt] += val;
	lamaxf[rt] += val;
}

void push_down(int rt){
	LL maxn = max(maxf[ls],maxf[rs]);
	if(maxf[ls] == maxn) update(ls,lamaxf[rt]);
	if(maxf[rs] == maxn) update(rs,lamaxf[rt]);
	lamaxf[rt] = 0;
}

void update_min(int L,int R,int l,int r,int rt,LL val){
	if(maxf[rt] <= val) return;
	if(L <= l && r <= R && val > maxse[rt]){
		update(rt,val-maxf[rt]);
		return;
	}
	push_down(rt);
	int m = l+r>>1;
	if(m >= L) update_min(L,R,l,m,ls,val);
	if(m <  R) update_min(L,R,m+1,r,rs,val);
	push_up(rt);
}

LL get_sum(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return sum[rt];
	}
	push_down(rt);
	LL ans = 0;
	int m = l+r>>1;
	if(m >= L) ans += get_sum(L,R,l,m,ls);
	if(m <  R) ans += get_sum(L,R,m+1,r,rs);
	return ans;
}

LL get_max(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R) return maxf[rt];
	push_down(rt);
	LL ans = -1e18;
	int m = l+r>>1;
	if(m >= L) ans = max(ans,get_max(L,R,l,m,ls));
	if(m <  R) ans = max(ans,get_max(L,R,m+1,r,rs));
	return ans;
}

void solve(){
	n = read() ,m = read();
	build(1,n,1);
	while(m--){
		LL op,l,r,val;
		op = read();
		l = read() ,r = read();
		if(op == 0){
			val = read();
			update_min(l,r,1,n,1,val);
		}
		else if(op == 1) printf("%lld\n",get_max(l,r,1,n,1));
		else printf("%lld\n",get_sum(l,r,1,n,1));
	}
}

int main() {
	//ios::sync_with_stdio(false);
	LL te;
	te = read();
	while(te--){
		solve();
	} 
	
	
	return 0;
}

【HDU - 5306】Gorgeous Sequence

原文：https://www.cnblogs.com/Tecode/p/14425550.html