吉老师线段树(HDU5306)
enterdawn
共 3227字,需浏览 7分钟
·
2021-05-14 15:26
给定一个数组a,实现三种操作:
1.将[l,r]区间的数修改为min(a_i,t)
2.求[l,r]区间最大值
3.求[l,r]区间和
之前der了几个细节问题,下次左右子节点一定在函数开头算出lchild和rchild。
解法不难理解,使用线段树维护区间和、区间最大值、区间最大值的个数和区间次大值。当要修改的数(t)大于等于区间最大值的时候,直接返回。大于区间次大值但小于区间最大值,我们可以利用已经维护的区间最大值个数去更新区间和,并下放懒标记。否则继续递归。
可以证明时间复杂度是O(mlog^2 n),证明过程详见吉老师当年在国家集训队的论文。
代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
ll a[1000005];
struct treenode{
ll cha;
ll sum,max,maxcount,secmax;
#define sum(x) tree[x].sum
#define cha(x) tree[x].cha
#define segmax(x) tree[x].max
#define maxc(x) tree[x].maxcount//统计区间内最大值的个数
#define secm(x) tree[x].secmax//区间次大值
}tree[1000005<<2];
void pushup(ll p){
sum(p)=sum(p<<1)+sum(p<<1|1);
if(segmax(p<<1)==segmax(p<<1|1)){
secm(p)=max(secm(p<<1),secm(p<<1|1));
segmax(p)=segmax(p<<1);
maxc(p)=maxc(p<<1)+maxc(p<<1|1);
}
else if(segmax(p<<1)<segmax(p<<1|1)){
secm(p)=max(segmax(p<<1),secm(p<<1|1));
segmax(p)=segmax(p<<1|1);
maxc(p)=maxc(p<<1|1);
}
else{
secm(p)=max(segmax(p<<1|1),secm(p<<1));
segmax(p)=segmax(p<<1);
maxc(p)=maxc(p<<1);
}
}
void pushdown(ll p){
if(cha(p)!=-1)
{
ll lc=p<<1;
ll rc=p<<1|1;
if(cha(p)<segmax(lc)&&cha(p)>secm(lc)){
sum(lc)-=1ll*(segmax(lc)-cha(p))*maxc(lc);
cha(lc)=cha(p);
segmax(lc)=cha(p);
}
if(cha(p)<segmax(rc)&&cha(p)>secm(rc)){
sum(rc)-=1ll*(segmax(rc)-cha(p))*maxc(rc);
cha(rc)=cha(p);
segmax(rc)=cha(p);
}
cha(p)=-1;
}
}
void build(ll s, ll t, ll p) {
//[s,t]区间建树,节点编号为p
cha(p)=-1;
if (s == t) {
secm(p)=-1;
maxc(p)=1;
sum(p) = a[s];
segmax(p) = a[s];
return;
}
ll mid = s + t >>1;
build(s, mid, p<<1);
build(mid + 1, t, p <<1| 1);
pushup(p);
}
ll getsum(ll l, ll r, ll s, ll t, ll p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return sum(p);
ll mid = s + t >>1, sum = 0;
pushdown(p);
if (l <= mid) sum += getsum(l, r, s, mid, p <<1);
if (r > mid) sum += getsum(l, r, mid + 1, t, p <<1|1);
return sum;
}
ll getmax(ll l, ll r, ll s, ll t, ll p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return segmax(p);
ll mid = (s + t) >>1, sum = 0;
pushdown(p);
if (l <= mid) sum = max(sum,getmax(l, r, s, mid, p <<1));
if (r > mid) sum = max(sum,getmax(l, r, mid + 1, t, p <<1| 1));
return sum;
}
//updateto为区间修改为某个值
void updateto(ll l, ll r, ll c, ll s, ll t, ll p) {
if(c>=segmax(p))return;
if (l <= s && t <= r&&c>secm(p)) {
sum(p)-=1ll*(segmax(p)-c)*maxc(p);
segmax(p)=c;
cha(p)=c;
return;
}
int mid = (s + t) >> 1;
pushdown(p);
if (l <= mid) updateto(l, r, c, s, mid, p<<1);
if (r > mid) updateto(l, r, c, mid + 1, t, p<<1|1 );
pushup(p);
}
int main() {
int _;
scanf("%d",&_);
while(_--) {
ll aa, l, r,t;
scanf("%lld%lld",&m,&n);
for (int i = 1; i <= m; i++) {
scanf("%lld",&a[i]);
}
build(1, m, 1);
while (n--) {
scanf("%lld%lld%lld",&aa,&l,&r);
if (aa == 0) {
scanf("%lld",&t);
updateto(l, r, t, 1, m, 1);
} else if (aa == 1) {
printf("%lld\n",getmax(l, r, 1, m, 1) );
} else {
printf("%lld\n",getsum(l, r, 1, m, 1) );
}
}
}
}
评论