[ABC343F] Second Largest Query 讲解
zrl123456
·
·
题解
考察：线段树（这道题不同于以前的线段树，我们需要解决三个问题）。
题目
维护值：
看到单点修改，区间查询，我们便想到了线段树。
但是这道题问的问题非常刁钻，问的是在 [l,r] 区间内严格次小值的数量，那么我们需要维护四个值：严格最小值，严格最小值数量，严格次小值，严格次小值数量（我们分别用 x_1,ans_1,x_2,ans_2 表示）。
状态转移：
我们知道了左孩子和右孩子的四个值，怎样得出父节点的四个值也是一个难点（设其左孩子为 u，右孩子为 v，父节点为 z）。
这得分九种情况讨论 （你没听错，九种情况），所以说举个例子就行：
$x_{z,1}=x_{u,1}$，$ans_{z,1}=ans_{u,1}$，$x_{z,2}=x_{u,2}$，$ans_{z,2}=ans_{u,2}$。
其余的同上，主要看代码：
```cpp
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}$。
具体看代码：
```cpp
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$ 多行）：
```cpp
#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;
}
```