题目链接

https://ac.nowcoder.com/acm/contest/9667/B

解题思路

线段树,特征过于明显
类似于线段树维护区间最大值,这里多了个对最大值个数的维护,最大值个数的维护只要在PushOn函数中同最大值的维护一起进行即可。
PushDown是用大区间更新小区间,一般用在有lazy的时候;PushOn是小区间更新大区间,为了维护某些值进行的
比较板子,难点在于容易敲错,bug还难de……
注意:
1.因为要输出最大值和个数,但是通过return返回只能返回一个值,因此我们这里采用引用的方式进行返回。
2.对于最大值的维护比较板子,对于个数的维护需要判断一下左右子树的最大值是否相等,若相等,当前树的最大值个数等于左右子树的最大值个数相加,否则,左右子树哪一个最大值大,用哪一个的最大值和最大值个数更新当前树。

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=2e5+10;
struct TREE{int l,r,mx,cnt;}tr[N<<2];
int n,m,l,r,ans1,ans2,a[N];
string op;

inline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch-'0');return x*f;}

void PushOn(int i)
{
    if(tr[i<<1].mx==tr[i<<1|1].mx) tr[i].mx=tr[i<<1].mx,tr[i].cnt=tr[i<<1].cnt+tr[i<<1|1].cnt;
    else if(tr[i<<1].mx>tr[i<<1|1].mx) tr[i].mx=tr[i<<1].mx,tr[i].cnt=tr[i<<1].cnt;
    else tr[i].mx=tr[i<<1|1].mx,tr[i].cnt=tr[i<<1|1].cnt;
}

void Build(int i,int l,int r)
{
    tr[i].l=l;
    tr[i].r=r;
    tr[i].mx=0;
    tr[i].cnt=0;
    if(l==r) 
    {
        tr[i].cnt=1;
        tr[i].mx=a[l];
        return ;
    }
    int mid=l+r>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);

    PushOn(i);
}

void Update(int i,int x,int y)
{
    if(tr[i].l==tr[i].r)
    {
        tr[i].mx=y;//直接修改就行,因为判断了一下,成bug了……
        return ;    
    } 
    if(x<=tr[i<<1].r) Update(i<<1,x,y);
    else Update(i<<1|1,x,y);

    PushOn(i);
}

void Query(int i,int l,int r,int& mx,int& cnt)
{
    if(l<=tr[i].l && tr[i].r<=r)
    {
        if(tr[i].mx==mx) cnt+=tr[i].cnt;//这里也异于板子
        else if(tr[i].mx>mx) mx=tr[i].mx,cnt=tr[i].cnt;
        return ;
    }
    if(r<tr[i].l || l>tr[i].r) return ;
    if(tr[i<<1].r>=l) Query(i<<1,l,r,mx,cnt);
    if(tr[i<<1|1].l<=r) Query(i<<1|1,l,r,mx,cnt);
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    Build(1,1,n);
    while(m--)
    {
        cin>>op;l=read();r=read();
        if(op[0]=='A') ans1=0,ans2=0,Query(1,l,r,ans1,ans2),printf("%d %d\n",ans1,ans2);
        else Update(1,l,r);
    }
}