题解：P12179 DerrickLo's Game (UBC002B)

· · 题解

首先，每次询问，操作后的序列显然是原序列中的最大值。比这个值大显然不会更优秀。

然后区间赋最大值显然是两个两个赋值比一大段的赋值更优秀，因为 4(n-1)\le n^2。

所以每个数赋值成最大值代价最多是 4。

考虑什么情况下代价小于 4，显然是这个数和最大值的差距小于 4。

现在我们可以把询问的序列中的数分成和最大值差距大于等于 4 和小于等于 4 的来考虑。

考虑如何快速计算小于等于 4 的个数，可以对每个值开一颗权值线段树，这样可以快速查询一个区间中某个数的出现次数。

然后查询最大值再开一颗线段树即可。

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=2e5+5;
int n,q,a[N];
struct node{
    int tree[N*4];
    void push_up(int x){
        tree[x]=max(tree[x<<1],tree[x<<1|1]);
    }
    void build(int x,int l,int r){
        if(l==r)tree[x]=a[l];
        else {
            int mid=(l+r)/2;build(x<<1,l,mid);build(x<<1|1,mid+1,r);
            push_up(x); 
        }
    }
    void update(int x,int l,int r,int q){
        if(l==r)tree[x]=a[l];
        else {
            int mid=(l+r)/2;
            if(q<=mid)update(x<<1,l,mid,q);
            else update(x<<1|1,mid+1,r,q);
            push_up(x); 
        }
    }
    int query(int x,int l,int r,int ql,int qr){
        if(ql<=l&&qr>=r)return tree[x];
        int re=0,mid=(l+r)/2;
        if(ql<=mid)re=query(x<<1,l,mid,ql,qr);
        if(qr>mid)re=max(re,query(x<<1|1,mid+1,r,ql,qr));
        return re;
    }
}T;
int tree[N*50],ls[N*50],rs[N*50],tot;
int rt[N];
il void push_up(int x){
    tree[x]=tree[ls[x]]+tree[rs[x]];
}
void update(int x,int l,int r,int q,int w){
    if(l==r){
        tree[x]+=w;return ;
    }int mid=(l+r)/2;
    if(q<=mid){
        if(ls[x]==0)ls[x]=++tot;
        update(ls[x],l,mid,q,w);
    }else{
        if(rs[x]==0)rs[x]=++tot;
        update(rs[x],mid+1,r,q,w);
    }
    push_up(x);
}
int query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)return tree[x];
    int re=0,mid=(l+r)/2;
    if(ql<=mid&&ls[x])re=query(ls[x],l,mid,ql,qr);
    if(qr>mid&&rs[x])re+=query(rs[x],mid+1,r,ql,qr);
    return re;
}
int main(){
    read(n);read(q);
    for(int i=1;i<=200000;i++){
        rt[i]=++tot;
    }
    for(int i=1;i<=n;i++){
        read(a[i]);
        update(rt[a[i]],1,n,i,1);
    }
    T.build(1,1,n);
    while(q--){
        int op,l,r;
        read(op);read(l);read(r);
        if(op==1){
            update(rt[a[l]],1,n,l,-1);
            a[l]=r;
            update(rt[a[l]],1,n,l,1);
            T.update(1,1,n,l);
        }else{
            int tmp=T.query(1,1,n,l,r),cnt=0,cnt2=0,ans=0;
            for(int i=tmp;i>=max(1,tmp-3);i--){
                cnt2=query(rt[i],1,n,l,r);
                ans+=(tmp-i)*cnt2;
                cnt+=cnt2;
            }
            ans+=(r-l+1-cnt)*4;
            printf("%d\n",ans);
        }
    }

    return 0;
}