hdu5306 Gorgeous Sequence

题意

维护一个序列,支持三种操作

  • 0 l r t 将区间$[l,r]$每个数对$t$取$min$
  • 1 l r 输出区间最大值
  • 2 l r输出区间每个数的和

分析

吉司机线段树…光看课件个人觉得还是比较误导人的(或者说只有我看完以后最初的想法naive到了暴力复杂度…)

一个错解。维护区间最大值,最大值的个数,次大值,取$min$的标记。更新时,对于一个区间,对$val$取$min$若它从未修改过,那么当$val\geq max$时直接返回,$max\gt val \geq secmax$时将区间和减去$cnt \times(max-val)$,否则继续拆分。这样会出现一个什么问题呢,就是一个区间之前有可能有一些数等于$val$,这区间如果符合修改的条件的话我们理应更新一下它的最大值的个数,然而我们不可能知道一个区间里$val$有多少个(因为$val$是不定的,或者说最多会有$10^6$种值,我们不可能对每个区间记录某个值有多少个,因而我们实时更新不了最大值的个数。考虑一个补救的办法:如果一个区间被更新过,那么$max=secmax=val$。这样的话访问这个区间时只会往下递归,因而即便是没有实时更新这里的最大值个数也不会影响答案。然而这个拿衣服做法是可卡的,如果一组数据中每次取$min$的值恰好比上一个少一,或者每次修改都是同一大的区间(例如整个序列),那么这个做法会一直递归到叶子,然后这就是一个$O(n^2logn)$的优秀做法辣

考虑正确的做法。感性理解这个最大值的个数,因为难以实时更新,实际上这个维护的值的本质要得到被打上的取$min$标记控制的值的个数。那么就可以抛弃这个原来的定义了,转而直接维护被标记控制的数的个数即可(同样记为$cnt$)。现在每个区间维护的即为最大值、控制的个数、区间和、标记即可。每次更新的时候,我们对于一个区间,可以拆分为以下两种:

  1. $max\leq val$,即便是取$min$对它也毫无影响
  2. $max \gt val$,需要把所有大于等于$val$的值染色为$val$

对于一个区间我们可以通过不断$dfs$来递归找到类型$2$的区间,如果找到的区间是一个叶子结点,我们直接将它的值归为$val$(或者归零表示$val$还没有控制这个叶子),然后一路$push~up$回来,否则继续寻找并修改。

复杂度$\in [nlogn,nlog^2n]$,粗略分析一下,每一次修改(取$min$为$val$)只会在取的$min$值比上一次(取$min$为$val1$)小的时候到一个$val1 \gt a_i \gt val$的叶子上,最坏情况下所有的叶子被这样访问一遍归于$O(n)$,然后$dfs$近似到$log$,线段树带一个$log$所以总的复杂度近似于$O(nlog^2n)$。

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace io{
const int L=(1<<19)+1;
int f;
char ibuf[L],*iS,*iT,c;
inline char Gc(){
if(iS==iT){
iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
return iS==iT?EOF:*iS++;
}
return*iS++;
}
template<class I>void Gi(I&x){
for(f=1,c=Gc();c<'0'||c>'9';c=Gc())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=Gc())x=x*10+(c&15);x*=f;
}
};
using io::Gi;
const int maxn=(int)1e6+5;
#define lson (o<<1)
#define rson (o<<1|1)
int n,m,a[maxn];
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline ll readLL()
{
char c;ll tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline void writeInt(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) {putchar('-');x=-x;}
static char s[21];int idx=0;
while(x) s[++idx]=x%10+'0',x/=10;
while(idx) putchar(s[idx--]);
}
inline void writeLL(ll x)
{
if(x==0) {putchar('0');return;}
if(x<0) {putchar('-');x=-x;}
static char s[21];int idx=0;
while(x) s[++idx]=x%10+'0',x/=10;
while(idx) putchar(s[idx--]);
}
namespace Tree{
int cnt[maxn<<2],maxv[maxn<<2],qmin[maxn<<2];
ll sumv[maxn<<2];
void maintain(int o,int l,int r)
{
sumv[o]=sumv[lson]+sumv[rson];
cnt[o]=cnt[lson]+cnt[rson];
maxv[o]=max(maxv[lson],maxv[rson]);
}
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r) {
sumv[o]=maxv[o]=a[l],cnt[o]=1,qmin[o]=a[l];
return;
}else {
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
qmin[o]=-1;
maxv[o]=max(maxv[lson],maxv[rson]);
sumv[o]= sumv[lson]+sumv[rson];
cnt[o]=cnt[lson]+cnt[rson];
}
}
void dfs(int o,int l,int r,int val)
{
if(l>r) return;
if(maxv[o]<=val) return;
qmin[o]=-1;
if(l==r) {maxv[o]=sumv[o]=cnt[o]=0;return;}
int mid=(l+r)>>1;
dfs(lson,l,mid,val);
dfs(rson,mid+1,r,val);
maintain(o,l,r);
}
void getmin(int o,int l,int r,int val)
{
if(~qmin[o] && qmin[o]<=val) return;
qmin[o]=val;
if(cnt[o]!=r-l+1) {
maxv[o]=val;
sumv[o]+=1ll*(r-l+1-cnt[o])*1ll*val;
cnt[o]=r-l+1;
}
}
void pushdown(int o,int l,int r)
{
if(~qmin[o]) {
int mid=(l+r)>>1;
getmin(lson,l,mid,qmin[o]);
getmin(rson,mid+1,r,qmin[o]);
qmin[o]=-1;
}
}
void Uqmin(int o,int l,int r,int ql,int qr,int val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {
dfs(o,l,r,val);
getmin(o,l,r,val);
return;
}else {
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Uqmin(lson,l,mid,ql,qr,val);
if(qr>mid) Uqmin(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
int Qmax(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return INT_MIN;
if(ql<=l && r<=qr) return maxv[o];
else {
int mid=(l+r)>>1;
pushdown(o,l,r);int ret=INT_MIN,tmp=0;
if(ql<=mid) {
ret=max(ret,Qmax(lson,l,mid,ql,qr));
}
if(qr>mid) {
ret=max(ret,Qmax(rson,mid+1,r,ql,qr));
}
maintain(o,l,r);
return ret;
}
}
ll Qsum(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return 0ll;
if(ql<=l && r<=qr) return sumv[o];
else {
int mid=(l+r)>>1;
pushdown(o,l,r);ll ret=0;
if(ql<=mid) ret+=Qsum(lson,l,mid,ql,qr);
if(qr>mid) ret+=Qsum(rson,mid+1,r,ql,qr);
maintain(o,l,r);
return ret;
}
} }puts("");
}
}
int T;
int main()
{
Gi(T);
for(int z=0;z<T;z++) {
Gi(n),Gi(m);
for(int i=1;i<=n;i++) Gi(a[i]);
Tree::build(1,1,n);
int op,l,r,t;
for(int i=1;i<=m;i++) {
Gi(op),Gi(l),Gi(r);
if(op==0) {
Gi(t);
Tree::Uqmin(1,1,n,l,r,t);
}else if(op==1) writeInt(Tree::Qmax(1,1,n,l,r)),putchar('\n');
else writeLL(Tree::Qsum(1,1,n,l,r)),putchar('\n');
}
}
return 0;
}