B-最好的宝石

B-最好的宝石

• 询问区间[l,r]内宝石的最大价值，和最大价值的宝石有多少个
• 在最大值上新添加一个属性区间最大值相同的个数cnt，建树的时候初始化cnt = 1（自身：区间[x,x]，cnt为1）

    tr[u].cnt = 0;
    if(tr[u].v == tr[u << 1].v) tr[u].cnt += tr[u << 1].cnt;
    if(tr[u].v == tr[u << 1 | 1].v) tr[u].cnt += tr[u << 1 | 1].cnt;

• 进行区间查询的时候，计算最大值，计算与最大值的相同个数

  if(maxv == tr[u].v) cnt += tr[u].cnt;
        if(maxv < tr[u].v){
            maxv = tr[u].v;
            cnt = tr[u].cnt;
        }

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 2e5 + 10;

int n,m;
int a[N];

struct Node{
    int l,r;
    int v,cnt;
}tr[N * 4];

int maxv,cnt;

void pushup(int u){
    tr[u].v = max(tr[u << 1].v,tr[u << 1 | 1].v);
    tr[u].cnt = 0;
    if(tr[u].v == tr[u << 1].v) tr[u].cnt += tr[u << 1].cnt;
    if(tr[u].v == tr[u << 1 | 1].v) tr[u].cnt += tr[u << 1 | 1].cnt;
}

void build(int u,int l,int r){
    if(l == r) tr[u] = {l,r,a[l],1};
    else{
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}

void query(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r){
        if(maxv == tr[u].v) cnt += tr[u].cnt;
        if(maxv < tr[u].v){
            maxv = tr[u].v;
            cnt = tr[u].cnt;
        }
        return ;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) query(u << 1,l,r);
    if(r > mid) query(u << 1 | 1,l,r);
}

void modify(int u,int x,int v){
    if(tr[u].l == x && tr[u].r == x){
        tr[u].cnt = 1;
        tr[u].v = v;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) modify(u << 1,x,v);
        else modify(u << 1 | 1,x,v);
        pushup(u);
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    build(1,1,n);
    string op;
    int x,y;
    while(m -- ){
        cin >> op;
        scanf("%d%d",&x,&y);
        if(op == "Ask"){
            maxv = 0,cnt = 0;
            query(1,x,y);
            cout<<maxv<<" "<<cnt<<endl;
        }else{
            modify(1,x,y);
        }    
    }    
    return 0;
}