本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-04 21:56:43

考察：线段树（这道题不同于以前的线段树，我们需要解决三个问题）。
题目

维护值：

看到单点修改，区间查询，我们便想到了线段树。
但是这道题问的问题非常刁钻，问的是在 $[l,r]$ 区间内严格次小值的数量，那么我们需要维护四个值：严格最小值，严格最小值数量，严格次小值，严格次小值数量（我们分别用 $x_1,ans_1,x_2,ans_2$ 表示）。

状态转移：

我们知道了左孩子和右孩子的四个值，怎样得出父节点的四个值也是一个难点（设其左孩子为 $u$，右孩子为 $v$，父节点为 $z$）。
这得分九种情况讨论 （你没听错，九种情况），所以说举个例子就行：
$x_{u,1}>x_{v,1}\lor x_{u,2}>x_{v,1}$（$x_{u,1}>x_{v,1}>x_{v,2}$，则 $x_{v,2}$ 不可能为次大值）：
$x_{z,1}=x_{u,1}$，$ans_{z,1}=ans_{u,1}$，$x_{z,2}=x_{u,2}$，$ans_{z,2}=ans_{u,2}$。
其余的同上，主要看代码：

t[x].x1=max(t[x<<1].x1,t[x<<1|1].x1);
if(t[x<<1].x1>t[x<<1|1].x1){
	t[x].ans1=t[x<<1].ans1;
	t[x].x2=max(t[x<<1].x2,t[x<<1|1].x1);
	if(t[x<<1].x2>t[x<<1|1].x1) t[x].ans2=t[x<<1].ans2;
	else if(t[x<<1].x2==t[x<<1|1].x1) t[x].ans2=t[x<<1].ans2+t[x<<1|1].ans1;
	else t[x].ans2=t[x<<1|1].ans1;
}else if(t[x<<1].x1==t[x<<1|1].x1){
	t[x].ans1=t[x<<1].ans1+t[x<<1|1].ans1;
	t[x].x2=max(t[x<<1].x2,t[x<<1|1].x2);
	if(t[x<<1].x2>t[x<<1|1].x2) t[x].ans2=t[x<<1].ans2;
	else if(t[x<<1].x2==t[x<<1|1].x2) t[x].ans2=t[x<<1].ans2+t[x<<1|1].ans2;
	else t[x].ans2=t[x<<1|1].ans2;
}else{
	t[x].ans1=t[x<<1|1].ans1;
	t[x].x2=max(t[x<<1].x1,t[x<<1|1].x2);
	if(t[x<<1].x1>t[x<<1|1].x2) t[x].ans2=t[x<<1].ans1;
	else if(t[x<<1].x1==t[x<<1|1].x2) t[x].ans2=t[x<<1].ans1+t[x<<1|1].ans2;
	else t[x].ans2=t[x<<1|1].ans2;
}

统计答案：

答案同样要四个值，用 $ansx_{1,1},ansx_{1,2},ansx_{2,1},ansx_{2,2}$ 表示，还得分六种情况，那再举个例子（设当前访问的节点为 $u$）：
$x_{u,1}>ansx_{1,1}$：
$ansx_{2,1}=ansx_{1,1}$（注意得先往下传），$ansx_{2,2}=ansx_{1,2}$，$ansx_{1,1}=x_{u,1}$，$ansx_{1,2}=ans_{u,1}$。
具体看代码：

if(t[x].x1>ans11){
	ans21=ans11;
	ans22=ans12;
	ans11=t[x].x1;
	ans12=t[x].ans1;
}else if(t[x].x1==ans11) ans12+=t[x].ans1;
else if(t[x].x1>ans21){
	ans21=t[x].x1;
	ans22=t[x].ans1;
}else if(t[x].x1==ans21) ans22+=t[x].ans1;
if(t[x].x2>ans21){\/\/注意没有 else
	ans21=t[x].x2;
	ans22=t[x].ans2;
}else if(t[x].x2==ans21) ans22+=t[x].ans2;

好了，三个问题都解决完了，剩余的按线段树板子码就行。
代码：（赛时代码，$120$ 多行）：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define INF 2147483647
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
const int N=2e5+5;
int n,q,a[N],op,l,r,p,x,ans11,ans12,ans21,ans22;
struct trees{
	int l,r,x1,ans1,x2,ans2;
}t[N<<2];
inl void pushup(int x){
	t[x].x1=max(t[x<<1].x1,t[x<<1|1].x1);
	if(t[x<<1].x1>t[x<<1|1].x1){
		t[x].ans1=t[x<<1].ans1;
		t[x].x2=max(t[x<<1].x2,t[x<<1|1].x1);
		if(t[x<<1].x2>t[x<<1|1].x1) t[x].ans2=t[x<<1].ans2;
		else if(t[x<<1].x2==t[x<<1|1].x1) t[x].ans2=t[x<<1].ans2+t[x<<1|1].ans1;
		else t[x].ans2=t[x<<1|1].ans1;
	}else if(t[x<<1].x1==t[x<<1|1].x1){
		t[x].ans1=t[x<<1].ans1+t[x<<1|1].ans1;
		t[x].x2=max(t[x<<1].x2,t[x<<1|1].x2);
		if(t[x<<1].x2>t[x<<1|1].x2) t[x].ans2=t[x<<1].ans2;
		else if(t[x<<1].x2==t[x<<1|1].x2) t[x].ans2=t[x<<1].ans2+t[x<<1|1].ans2;
		else t[x].ans2=t[x<<1|1].ans2;
	}else{
		t[x].ans1=t[x<<1|1].ans1;
		t[x].x2=max(t[x<<1].x1,t[x<<1|1].x2);
		if(t[x<<1].x1>t[x<<1|1].x2) t[x].ans2=t[x<<1].ans1;
		else if(t[x<<1].x1==t[x<<1|1].x2) t[x].ans2=t[x<<1].ans1+t[x<<1|1].ans2;
		else t[x].ans2=t[x<<1|1].ans2;
	}
}
inl void build(int l,int r,int x){
	t[x].l=l;
	t[x].r=r;
	if(l==r){
		t[x].x1=a[l];
		t[x].ans1=1;
		return;
	}
	reg int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	pushup(x);
}
inl void add(int p,int num,int x){
	if(t[x].l==p&&t[x].r==p){
		t[x].x1=num;
		return;
	}
	reg int mid=(t[x].l+t[x].r)>>1;
	if(p<=mid) add(p,num,x<<1);
	else add(p,num,x<<1|1);
	pushup(x);
}
inl void getans(int l,int r,int x){
	if(l<=t[x].l&&t[x].r<=r){
		if(t[x].x1>ans11){
			ans21=ans11;
			ans22=ans12;
			ans11=t[x].x1;
			ans12=t[x].ans1;
		}else if(t[x].x1==ans11) ans12+=t[x].ans1;
		else if(t[x].x1>ans21){
			ans21=t[x].x1;
			ans22=t[x].ans1;
		}else if(t[x].x1==ans21) ans22+=t[x].ans1;
		if(t[x].x2>ans21){
			ans21=t[x].x2;
			ans22=t[x].ans2;
		}else if(t[x].x2==ans21) ans22+=t[x].ans2;
		return;
	}
	reg int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid) getans(l,r,x<<1);
	if(r>mid) getans(l,r,x<<1|1);
}
signed main(){
	n=read();
	q=read();
	for(reg int i=1;i<=n;++i) a[i]=read();
	build(1,n,1);
	for(reg int i=1;i<=q;++i){
		op=read();
		if(op==1){
			p=read();
			x=read();
			add(p,x,1);
		}else{
			l=read();
			r=read();
			ans11=ans12=ans21=ans22=0;
			getans(l,r,1);
			write(ans22);
			puts("");
		}
	}
	return 0;
}