赛时不会 E，看到 F 高兴坏了。
First. 题目分析
首先，这道题单点修，区间查，一般都可以用数据结构做，此时我们不妨往线段树上想一想。
那么求次大，我们线段树需要维护什么呢？
对于合并两个区间，其的次大并不是两个区间次大中的较大者，而还需要考虑两个区间的最大值，即两个区间最大值、次大值中的次大值。
那么要求数量，那是否需要再维护一个最大值数量和次大值数量呢？
所以要维护的信息就是：
-
最大值
-
次大值
-
最大值的数量
-
次大值的数量
此时求出来了次大值，那么对于所有等于次大的数，将其的数量加于次大的数量上即可。
一点小提醒：本题是严格次小，所以次大值一开始设为 -1，并且更新的时候要去重。
Second. 区间合并的实现
我的做法很暴力，将两个区间分别的次大和最大存于一个数组里，然后排序，再去重，再像求序列次大一样更新。
这里 node 表示的是每个区间的信息。
struct node {
int ma , ma2 , cnt , cnt2;
// ma : 最大值
// ma2 : 次大值
// cnt : 最大值的个数
// cnt2 : 次大值的个数
}t[N * 4];
node hb(node x , node y) {
node res = { -1, -1, 0, 0 };
int cur[5] = { 0, x.ma, y.ma, x.ma2, y.ma2 };
sort(cur + 1 , cur + 1 + 4);
for (int i = 1; i <= 4; i++) {
if (cur[i] == cur[i - 1]) continue;
if (cur[i] > res.ma) res.ma2 = res.ma , res.ma = cur[i];
else if (cur[i] > res.ma2) res.ma2 = cur[i]; // 类比序列次大，如果大于最大值，那么先将次大值更新为最大值，然后最大值更新为该值
}
if (res.ma == x.ma) res.cnt += x.cnt;
if (res.ma == y.ma) res.cnt += y.cnt;
if (res.ma2 == x.ma) res.cnt2 += x.cnt; // 对于所有 = 次大的加上它的数量
if (res.ma2 == x.ma2) res.cnt2 += x.cnt2;
if (res.ma2 == y.ma) res.cnt2 += y.cnt;
if (res.ma2 == y.ma2) res.cnt2 += y.cnt2;
if (res.ma2 == res.ma) res.ma2 = -1 , res.cnt2 = 0;
return res;
}
这里采用了小粉兔式写法（强烈推荐，超好用）。
Third. 修改和查询的实现
修改
由于是单点修改，所以不用 lazy。
直接递归到修改节点，再一层层更新即可。
void updata(int p , int l , int r , int k , int x) {
if (l == r) t[p] = { x, -1, 1, 0 }; // 直接修改
else {
int mid = l + r >> 1;
if (mid >= k) updata(p * 2 , l , mid , k , x);
if (mid < k) updata(p * 2 + 1 , mid + 1 , r , k , x);
t[p] = hb(t[p * 2] , t[p * 2 + 1]); // 向上更新
}
}
查询
直接查询并合并查询得到的区间即可。
node getans(int p , int l , int r , int ql , int qr) {
if (ql <= l && r <= qr) {return t[p]; }
int mid = l + r >> 1; node res = { -1, -1, -1, -1 };
if (mid >= ql) res = getans(p * 2 , l , mid , ql , qr);
if (mid < qr) {
node x = getans(p * 2 + 1 , mid + 1 , r , ql , qr);
if (res.ma != -1) res = hb(res , x); // 如果于左右两边都相交，那么合并左右两边
else res = x;
}
return res;
}
最后完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pi;
const int N = 2e5 + 10;
int n , q;
int a[N];
struct node {
int ma , ma2 , cnt , cnt2;
}t[N * 4];
node hb(node x , node y) {
node res = { -1, -1, 0, 0 };
int cur[5] = { 0, x.ma, y.ma, x.ma2, y.ma2 };
sort(cur + 1 , cur + 1 + 4);
for (int i = 1; i <= 4; i++) {
if (cur[i] == cur[i - 1]) continue;
if (cur[i] > res.ma) res.ma2 = res.ma , res.ma = cur[i];
else if (cur[i] > res.ma2) res.ma2 = cur[i];
}
if (res.ma == x.ma) res.cnt += x.cnt;
if (res.ma == y.ma) res.cnt += y.cnt;
if (res.ma2 == x.ma) res.cnt2 += x.cnt;
if (res.ma2 == x.ma2) res.cnt2 += x.cnt2;
if (res.ma2 == y.ma) res.cnt2 += y.cnt;
if (res.ma2 == y.ma2) res.cnt2 += y.cnt2;
if (res.ma2 == res.ma) res.ma2 = -1 , res.cnt2 = 0;
return res;
}
void build(int p , int l , int r) {
if (l == r) t[p] = { a[l], -1, 1, 0 };
else build(p * 2 , l , l + r >> 1) , build(p * 2 + 1 , (l + r >> 1) + 1 , r) , t[p] = hb(t[p * 2] , t[p * 2 + 1]);
}
void updata(int p , int l , int r , int k , int x) {
if (l == r) t[p] = { x, -1, 1, 0 };
else {
int mid = l + r >> 1;
if (mid >= k) updata(p * 2 , l , mid , k , x);
if (mid < k) updata(p * 2 + 1 , mid + 1 , r , k , x);
t[p] = hb(t[p * 2] , t[p * 2 + 1]);
}
}
node getans(int p , int l , int r , int ql , int qr) {
if (ql <= l && r <= qr) {return t[p]; }
int mid = l + r >> 1; node res = { -1, -1, -1, -1 };
if (mid >= ql) res = getans(p * 2 , l , mid , ql , qr);
if (mid < qr) {
node x = getans(p * 2 + 1 , mid + 1 , r , ql , qr);
if (res.ma != -1) res = hb(res , x);
else res = x;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1 , 1 , n);
while (q--) {
int opt , l , r;
cin >> opt >> l >> r;
if (opt == 1) updata(1 , 1 , n , l , r);
else cout << getans(1 , 1 , n , l , r).cnt2 << endl;
}
return 0;
}