ICPC-CCPC/abc342-f.cpp at main · SkyEyeController/ICPC-CCPC · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 1;
int n, q, a[maxn], tag[maxn << 2];
typedef struct node
{
    pair<int, int> fir = {0, 0}, sec = {-1, 0};
} node;
node tree[maxn << 2];
void upgrade(int p)
{
    map<int, int> mp;
    mp[tree[p << 1].fir.first] += tree[p << 1].fir.second;
    mp[tree[p << 1].sec.first] += tree[p << 1].sec.second;
    mp[tree[p << 1 | 1].fir.first] += tree[p << 1 | 1].fir.second;
    mp[tree[p << 1 | 1].sec.first] += tree[p << 1 | 1].sec.second;
    auto it = mp.rbegin();
    tree[p].fir = {(*it).first, (*it).second};
    if (mp.size() >= 2)
    {
        it++;
        tree[p].sec = {(*it).first, (*it).second};
    }
    mp.clear();
    return;
}
void buildtree(int p = 1, int cl = 1, int cr = n)
{
    if (cl > cr)
        return;
    if (cl == cr)
        return void((tree[p].fir = {a[cl], 1}, tree[p].sec = {-1, 0}));
    int mid = (cl + cr) >> 1;
    buildtree(p << 1, cl, mid);
    buildtree(p << 1 | 1, mid + 1, cr);
    upgrade(p);
    return;
}
void update(int pos, int x, int p = 1, int cl = 1, int cr = n)
{
    if (cl > cr)
        return;
    if (pos < cl || pos > cr)
        return;
    if (cl == cr)
        return void((tree[p].fir = {a[cl], 1}, tree[p].sec = {-1, 0}));
    int mid = (cl + cr) >> 1;
    update(pos, x, p << 1, cl, mid);
    update(pos, x, p << 1 | 1, mid + 1, cr);
    upgrade(p);
    return;
}
void insert(int pos, int x)
{
    a[pos] = x;
    update(pos, x);
}
using pp = pair<pair<int, int>, pair<int, int>>;
pp query(int l, int r, int p = 1, int cl = 1, int cr = n)
{
    if (cl > cr || cr < l || cl > r)
        return {{0, 0}, {-1, 0}};
    if (cl >= l && cr <= r)
    {
        return {tree[p].fir, tree[p].sec};
    }
    int mid = (cl + cr) >> 1;
    map<int, int> mp;
    pp left = query(l, r, p << 1, cl, mid);
    pp right = query(l, r, p << 1 | 1, mid + 1, cr);
    mp[left.first.first] += left.first.second;
    mp[left.second.first] += left.second.second;
    mp[right.first.first] += right.first.second;
    mp[right.second.first] += right.second.second;
    if (mp.size() == 1)
    {
        mp[-1] = 0;
    }
    pair<int, int> m1 = (*(mp.rbegin()));
    pair<int, int> m2 = (*(++mp.rbegin()));
    return {m1, m2};
}
int qquery(int l, int r)
{
    return query(l, r).second.second;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    buildtree();
    while (q--)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if (opt == 1)
        {
            insert(x, y);
        }
        else
        {
            cout << qquery(x, y) << endl;
        }
    }
    system("pause");
    return 0;
}