【HDU5306】优美的序列

  • 本文为博主原创，未经许可不得转载

这道题的线段树做法非常的妙，似乎应该叫做吉司机线段树

感觉这个东西有一大堆套路

具体的做法就是维护最大值及其出现次数和次大值

修改时如果x大于最大值就退出

否则若大于次大值，则暴力修改

否则递归左右子树

时间复杂度是$O(m \log^2 n)$

我不会证明复杂度，好像要用到势能分析什么的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000010
using namespace std;
typedef long long ll;
struct node{int ma,se,t,flag;ll num;}tr[MAXN<<3];
int n,m;
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void relord(int p){
	tr[p].num=tr[p<<1].num+tr[p<<1|1].num;
	tr[p].ma=max(tr[p<<1].ma,tr[p<<1|1].ma);
	if(tr[p<<1].ma==tr[p<<1|1].ma){
		tr[p].t=tr[p<<1].t+tr[p<<1|1].t;
		tr[p].se=max(tr[p<<1].se,tr[p<<1|1].se);
	}
	else if(tr[p<<1].ma>tr[p<<1|1].ma){
		tr[p].t=tr[p<<1].t;
		tr[p].se=max(tr[p<<1|1].ma,tr[p<<1].se);
	}
	else{
		tr[p].t=tr[p<<1|1].t;
		tr[p].se=max(tr[p<<1].ma,tr[p<<1|1].se);
	}
}
void cal(int p,int value){
	tr[p].num+=(ll)tr[p].t*(value-tr[p].ma);
	tr[p].ma=tr[p].flag=value;
}
void pushdown(int p){
	int value=tr[p].flag;
	if(tr[p<<1].ma>value)   cal(p<<1,value);
	if(tr[p<<1|1].ma>value) cal(p<<1|1,value);
	tr[p].flag=-1;
}
void build(int p,int l,int r){
	tr[p].flag=-1; tr[p].se=0;
	if(l==r) {tr[p].num=tr[p].ma=read(); tr[p].t=1; return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
	relord(p);
}
void updata(int p,int l,int r,int x,int y,int value){
	if(tr[p].flag!=-1) pushdown(p);
	int mid=(l+r)>>1;
	if(x>r||y<l) return;
	if(x<=l&&y>=r){
		if(value>=tr[p].ma) return;
		else if(value>tr[p].se) {cal(p,value);return;}
		else{
			updata(p<<1,l,mid,x,y,value);
			updata(p<<1|1,mid+1,r,x,y,value);
			relord(p);
			return;
		}
	}
	updata(p<<1,l,mid,x,y,value); updata(p<<1|1,mid+1,r,x,y,value);
	relord(p);
}
int getmax(int p,int l,int r,int x,int y){
	if(tr[p].flag!=-1) pushdown(p);
	if(x>r||y<l) return 0;
	if(x<=l&&y>=r) return tr[p].ma;
	int mid=(l+r)>>1;
	return max(getmax(p<<1,l,mid,x,y),getmax(p<<1|1,mid+1,r,x,y));
}
ll getsum(int p,int l,int r,int x,int y){
	if(tr[p].flag!=-1) pushdown(p);
	if(x>r||y<l) return 0;
	if(x<=l&&y>=r) return tr[p].num;
	int mid=(l+r)>>1;
	return getsum(p<<1,l,mid,x,y)+getsum(p<<1|1,mid+1,r,x,y);
}
void solve(){
	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){int x=read();updata(1,1,n,l,r,x);}
		else if(opt==1)printf("%d\n",getmax(1,1,n,l,r));
		else printf("%lld\n",getsum(1,1,n,l,r));
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

本文标题:【HDU5306】优美的序列

文章作者:chty

发布时间:2017年05月26日 - 20时42分

最后更新:2018年03月02日 - 17时14分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,