自动搬运

查看原文

来自洛谷，原作者为

	suzhikz 我永远喜欢艾莉丝！

搬运于2025-08-24 23:13:28，当前版本为作者最后更新于2025-04-14 20:48:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

然后区间赋最大值显然是两个两个赋值比一大段的赋值更优秀，因为 $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;
}