[ABC343F] Second Largest Query

题面翻译

给定长度为 $N$ 的序列 $A$ 和一个正整数 $Q$ 表示有 $Q$ 次操作，第 $i$ 次操作格式如下：

• 1 p x 表示将 $A_p$ 修改为 $x$。
• 2 l r 输出区间 $[l, r]$ 之间严格次大值的数量。

对于每个查询操作，输出一行一个整数代表答案。

样例 #1

样例输入 #1

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

样例输出 #1

1
0
2

样例 #2

样例输入 #2

1 1
1000000000
2 1 1

样例输出 #2

0

样例 #3

样例输入 #3

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

样例输出 #3

0
1
0
2
4

提示

制約

• $ 1\ \leq\ N,\ Q\ \leq\ 2\ \times\ 10^5 $
• $ 1\ \leq\ A_i\ \leq\ 10^9 $
• タイプ $ 1 $ のクエリにおいて、$ 1\ \leq\ p\ \leq\ N $
• タイプ $ 1 $ のクエリにおいて、$ 1\ \leq\ x\ \leq\ 10^9 $
• タイプ $ 2 $ のクエリにおいて、$ 1\ \leq\ l\ \leq\ r\ \leq\ N $
• タイプ $ 2 $ のクエリが $ 1 $ つ以上存在する
• 入力される値はすべて整数

Sample Explanation 1

はじめ、$ A\ =\ (3,\ 3,\ 1,\ 4,\ 5) $ です。 $ 1 $ 個目のクエリでは、$ (3,\ 3,\ 1) $ において $ 2 $ 番目に大きい値は $ 1 $ であり、$ 3,\ 3,\ 1 $ の中に $ 1 $ は $ 1 $ 個あるので $ 1 $ を出力します。 $ 2 $ 個目のクエリでは、$ (5) $ において $ 2 $ 番目に大きい値は存在しないので $ 0 $ を出力します。 $ 3 $ 個目のクエリでは、$ A\ =\ (3,\ 3,\ 3,\ 4,\ 5) $ となります。 $ 4 $ 個目のクエリでは、$ (3,\ 3,\ 4) $ において $ 2 $ 番目に大きい値は $ 3 $ であり、$ 3,\ 3,\ 4 $ の中に $ 3 $ は $ 2 $ 個あるので $ 2 $ を出力します。

#include <iostream>
using namespace srd;
const int N = 2e5 + 5;

int n, q;

struct node {
    int maxn, maxn2;
    int siz, siz2;
}tree[N << 2];

int a[N];

bool cmp(int x, int y)
{
    return x > y;
}

node up(node p, node q)
{
    map<int, int>mp;
    set<int>v;
    mp[p.maxn] += p.siz;
    mp[q.maxn] += q.siz;
    mp[p.maxn2] += p.siz2;
    mp[q.maxn2] += q.siz2;
    v.insert(p.maxn), v.insert(q.maxn);
    v.insert(p.maxn2), v.insert(q.maxn2);
    node s;
    auto it = v.rbegin();
    s.maxn = *it;
    s.siz = mp[*it];
    it++;
    s.maxn2 = *it;
    s.siz2 = mp[*it];
    return s;
}

void build(int i, int l, int r)
{
    if (l == r)
    {
        tree[i].maxn = a[l], tree[i].siz = 1;
        tree[i].maxn2 = -1, tree[i].siz2 = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    tree[i] = up(tree[i << 1], tree[i << 1 | 1]);
}

void update(int i, int l, int r, int pos, int k)
{
    if (l == r)
    {
        tree[i].maxn = k, tree[i].siz = 1;
        tree[i].maxn2 = -1, tree[i].siz2 = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(i << 1, l, mid, pos, k);
    else update(i << 1 | 1, mid + 1, r, pos, k);
    tree[i] = up(tree[i << 1], tree[i << 1 | 1]);
}

node query(int i, int l, int r, int tl, int tr)
{
    if (l >= tl && r <= tr) return tree[i];
    int mid = (l + r) >> 1;
    if (tr <= mid) return query(i << 1, l, mid, tl, tr);
    if (tl > mid) return query(i << 1 | 1, mid + 1, r, tl, tr);
    return up(query(i << 1, l, mid, tl, tr), query(i << 1 | 1, mid + 1, r, tl, tr));
}


void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, y;
            cin >> x >> y;
            update(1, 1, n, x, y);
        }
        else if (op == 2)
        {
            int l, r;
            cin >> l >> r;
            node s = query(1, 1, n, l, r);
            if (s.maxn2 != -1) cout << s.siz2 << "\n";
            else cout << "0\n";
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}