原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=5306
Gorgeous Sequence
Problem Description
There is a sequence a a a of length n n n. We use a i a_i ai to denote the i i i-th element in this sequence. You should do the following three types of operations to this sequence.
0
x
y
t
0\ x\ y\ t
0 x y t: For every
x
≤
i
≤
y
x≤i≤y
x≤i≤y, we use
m
i
n
(
a
i
,
t
)
min(a_i,t)
min(ai,t) to replace the original
a
i
a_i
ai's value.
1
x
y
1\ x\ y
1 x y: Print the maximum value of
a
i
a_i
ai that
x
≤
i
≤
y
x≤i≤y
x≤i≤y.
2
x
y
2\ x\ y
2 x y: Print the sum of
a
i
a_i
ai that
x
≤
i
≤
y
x≤i≤y
x≤i≤y.
Input
The first line of the input is a single integer T T 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 a 1 , ⋯ , a n ( ∀ 1 ≤ i ≤ n , 0 ≤ a i < 2 31 ) a_1,\cdots,a_n(∀1≤i≤n,0≤a_i<2^{31}) a1,⋯,an(∀1≤i≤n,0≤ai<231).
Each of the following m lines represents one operation ( 1 ≤ x ≤ y ≤ n , 0 ≤ t < 2 31 ) (1≤x≤y≤n,0≤t<2^{31}) (1≤x≤y≤n,0≤t<231).
It is guaranteed that T = 100 , ∑ n ≤ 1000000 , ∑ m ≤ 1000000 T=100, ∑n≤1000000, ∑m≤1000000 T=100,∑n≤1000000,∑m≤1000000.
Output
For every operation of type 1 1 1 or 2 2 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
Hint
Please use efficient IO method
Author
XJZX
Source
2015 Multi-University Training Contest 2
Recommend
wange2014 | We have carefully selected several similar problems for you: 6937 6936 6935 6934 6933
题目大意
对长度为 n n n的数列 { a i } \{a_i\} {ai}进行 m m m次操作，共有三种类型的操作：
0
x
y
t
0\ x\ y\ t
0 x y t: 对所有的
a
i
,
x
≤
i
≤
y
a_i,x≤i≤y
ai,x≤i≤y, 将
a
i
a_i
ai变为
m
i
n
(
a
i
,
t
)
min(a_i,t)
min(ai,t)。
1
x
y
1\ x\ y
1 x y: 输出区间
[
x
,
y
]
[x,y]
[x,y]中最大的
a
i
a_i
ai的值。
2
x
y
2\ x\ y
2 x y: 输出
∑
i
=
x
y
a
i
\sum_{i=x}^{y}a_i
∑i=xyai。
题解
除了维护区间和 s u m sum sum、最大值 m x mx mx这两个常规操作，为了使复杂度达到 l o g 2 n log_2n log2n级别，我们还需要维护每个区间的严格次大值 s e se se以及最大值的个数 c o t cot cot。
当
t
≥
m
x
t\ge mx
t≥mx时，操作无效直接返回；
当
s
e
<
t
<
m
x
se<t< mx
se<t<mx时，直接计算出区间和
s
u
m
−
=
(
m
x
−
t
)
×
v
o
t
sum-=(mx-t)\times vot
sum−=(mx−t)×vot，再更新最大值；
当
t
≥
s
e
t\ge se
t≥se时，无法快速更新，直接向下递归更新再向上合并。
可以发现，整个算法的最大复杂度在于第三类情况。不过我们可以这样考虑：在整个长度为 n n n的数列 { a i } \{a_i\} {ai}里，不同的数至多有 n n n个，每当出现第三种情况时，至少最大值和次大值都会变成 t t t，即至少有两个数会变成相同的。而整棵线段树所有节点一共有 n l o g 2 n nlog_2n nlog2n个，所以最多这么多次操作后，整棵线段树的节点值的最大值都会变成一样的，严格次大值为 0 0 0。再加上其他操作的复杂度，可以得到整个算法的总复杂度不会超过 O ( ( n + m ) × l o g 2 n ) O((n+m)\times log_2n) O((n+m)×log2n)。
据说可以证明复杂度是 O ( m l o g 2 n ) O(mlog_2n) O(mlog2n)的，但博主不会……
代码
退役老咸鱼含泪复习线段树……
#include<bits/stdc++.h>
#define ls v<<1
#define rs v<<1|1
using namespace std;
const int M=1e6+5;
struct node{
int le,ri,mx,se,cot,mn;
long long sum;
}tree[M<<2];
int T,n,m,que[M];
int read()
{
int r=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())r=(r<<3)+(r<<1)+c-'0';
return r;
}
void up(int v)
{
tree[v].sum=tree[ls].sum+tree[rs].sum;
tree[v].mx=max(tree[ls].mx,tree[rs].mx);
if(tree[ls].mx==tree[rs].mx)
{
tree[v].cot=tree[ls].cot+tree[rs].cot;
tree[v].se=max(tree[ls].se,tree[rs].se);
}
else if(tree[ls].mx>tree[rs].mx)
{
tree[v].cot=tree[ls].cot;
tree[v].se=max(tree[ls].se,tree[rs].mx);
}
else
{
tree[v].cot=tree[rs].cot;
tree[v].se=max(tree[rs].se,tree[ls].mx);
}
}
void push(int v,int mn)
{
if(tree[v].mx<mn)return;
tree[v].sum-=1ll*(tree[v].mx-mn)*tree[v].cot;
tree[v].mx=tree[v].mn=mn;
}
void down(int v)
{
if(tree[v].mn>=0)
{
push(ls,tree[v].mn);
push(rs,tree[v].mn);
tree[v].mn=-1;
}
}
void build(int v,int le,int ri)
{
tree[v].le=le,tree[v].ri=ri;
tree[v].mn=-1;
if(le==ri)
{
tree[v].cot=1;
tree[v].se=0;
tree[v].sum=tree[v].mx=que[le];
return;
}
int mid=le+ri>>1;
build(ls,le,mid),build(rs,mid+1,ri);
up(v);
}
void qmin(int v,int le,int ri,int t)
{
if(t>=tree[v].mx)return;
if(le<=tree[v].le&&tree[v].ri<=ri&&tree[v].se<t)
{
tree[v].sum-=1ll*(tree[v].mx-t)*tree[v].cot;
tree[v].mx=tree[v].mn=t;
return;
}
down(v);
int mid=tree[v].le+tree[v].ri>>1;
if(le<=mid)qmin(ls,le,ri,t);
if(mid<ri)qmin(rs,le,ri,t);
up(v);
}
int askmax(int v,int le,int ri)
{
if(le<=tree[v].le&&tree[v].ri<=ri)return tree[v].mx;
int mid=tree[v].le+tree[v].ri>>1,re=0;
down(v);
if(le<=mid)re=askmax(ls,le,ri);
if(mid<ri)re=max(re,askmax(rs,le,ri));
return re;
}
long long asksum(int v,int le,int ri)
{
if(le<=tree[v].le&&tree[v].ri<=ri)return tree[v].sum;
int mid=tree[v].le+tree[v].ri>>1;
long long re=0;
down(v);
if(le<=mid)re=asksum(ls,le,ri);
if(mid<ri)re+=asksum(rs,le,ri);
return re;
}
void in()
{
//memset(tree,0,sizeof(tree));
//scanf("%d%d",&n,&m);
n=read(),m=read();
for(int i=1;i<=n;++i)que[i]=read();//scanf("%d",&que[i]);
}
void ac()
{
build(1,1,n);
for(int i=1,op,x,y;i<=m;++i)
{
//scanf("%d%d%d",&op,&x,&y);
op=read(),x=read(),y=read();
if(!op)
{
//scanf("%d",&op);
op=read();
qmin(1,x,y,op);
}
else if(op-1)printf("%lld\n",asksum(1,x,y));
else printf("%d\n",askmax(1,x,y));
}
}
int main()
{
scanf("%d",&T);
for(;T;--T)in(),ac();
//system("pause");
}