线段树（区间最大值和最大值的个数）

传送门：

链接：https://ac.nowcoder.com/acm/contest/9667/B
来源：牛客网

牛牛有n个宝石，第i个宝石的价值是w[i].

有m个操作，操作分为两种类型

− Change   x  y   把第x个宝石的价值改成 y 

− Ask          l   r   询问区间[l,r]内宝石的最大价值，和最大价值的宝石有多少个。

 

 

线段树中查询区间最大值的时候都是上传标记的

先查询左右节点在上传标记

例:求和中的下传标记：

要先下传标记在，查询左右子节点

void push(int p){
	t[2*p].lazy+=t[p].lazy;//下传标记 
	t[2*p].s+=1ll*(t[2*p].r-t[2*p].l+1)*t[p].lazy;
	
	t[2*p+1].lazy+=t[p].lazy;
	t[2*p+1].s+=1ll*(t[2*p+1].r-t[2*p+1].l+1)*t[p].lazy;
	
	t[p].lazy=0;//还原标记 
}

 

更新时：

push(p);
if(l<=t[2*p].r){
	update(2*p,l,r,k);
} 
if(r>=t[2*p+1].l){
　　update(2*p+1,l,r,k);
}

这里的上传标记（回溯的时候上传）

上传标记的时候是根据2*p和2*p+1更新p

void push_up(int p){
	t[p].ma=max(t[2*p].ma,t[2*p+1].ma);
	if(t[2*p].ma==t[2*p+1].ma){
		t[p].cnt=t[2*p].cnt+t[2*p+1].cnt;
	} 
	else if(t[2*p].ma>t[2*p+1].ma){
		t[p].cnt=t[2*p].cnt;
	}
	else{
		t[p].cnt=t[2*p+1].cnt;
	}
}

更新时：

int mid=(t[p].l+t[p].r)/2;
    if(x<=mid){
        update(2*p,x,k);
    } 
    else{
        update(2*p+1,x,k);
    }
    push_up(p);

就是在区间求和中建树中也上传标记了

t[p].s=t[2*p].s+t[2*p+1].s;

这个题就是：

维护一个区间最值，和一个区间最值的个数，在查询的时候先找出区间最值，在找出最值出现的次数

上传标记时：

void push_up(int p){
    t[p].ma=max(t[2*p].ma,t[2*p+1].ma);
    if(t[2*p].ma==t[2*p+1].ma){
        t[p].cnt=t[2*p].cnt+t[2*p+1].cnt;
    } 
    else if(t[2*p].ma>t[2*p+1].ma){
        t[p].cnt=t[2*p].cnt;
    }
    else{
        t[p].cnt=t[2*p+1].cnt;
    }
}

AC代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=4e6+100; 
int a[maxn]; 
struct node{
    int l,r;
    int ma,cnt;
}t[maxn];
int ans1,n,m,x,y;
void push_up(int p){
    t[p].ma=max(t[2*p].ma,t[2*p+1].ma);
    if(t[2*p].ma==t[2*p+1].ma){
        t[p].cnt=t[2*p].cnt+t[2*p+1].cnt;
    } 
    else if(t[2*p].ma>t[2*p+1].ma){
        t[p].cnt=t[2*p].cnt;
    }
    else{
        t[p].cnt=t[2*p+1].cnt;
    }
}
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].cnt=0;
    if(l==r){
        t[p].ma=a[l];
        t[p].cnt=1;
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    push_up(p);
}
void update(int p,int x,int k){
    if(t[p].l==t[p].r){
        t[p].ma=k;
        t[p].cnt=1;
        return ;
    } 
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid){
        update(2*p,x,k);
    } 
    else{
        update(2*p+1,x,k);
    }
    push_up(p);
} 
void query(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        ans1=max(ans1,t[p].ma);
        return ;
    }
    int mid=(L+R)/2;
    if(l<=mid){
        query(2*p,l,r); 
    }
    if(r>mid){
        query(2*p+1,l,r);
    }
    push_up(p);
}
int getcnt(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r&&t[p].cnt){
        if(ans1==t[p].ma){
            return t[p].cnt;
        }
        else return 0;
    }
    int z=0;
    int mid=(L+R)/2; 
    if(l<=mid){
        z+=getcnt(2*p,l,r);
    }
    if(r>mid){
        z+=getcnt(2*p+1,l,r);
    } 
    push_up(p);
    return z;
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    char str[maxn];
    for(int i=1;i<=m;i++){
        cin>>str>>x>>y;
        if(str[0]=='A'){
            ans1=0;
            query(1,x,y);
            printf("%d %d
",ans1,getcnt(1,x,y));
        }
        else{
            update(1,x,y);
        }
    }
}