#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define pb push_back
#define fr(i, l, r) for(ll i = l; i <= r; ++ i)
#define rf(i, r, l) for(ll i = l; i >= r; -- i)
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef int ll;
typedef pair<ll, ll> pll;
const ll oo = ll(1e9) + 10;
ll n, Q, N;
ll a[100100], mp[1000100], nmb[1000010], ans;
struct SegmentTree{
vector < _set < pair < int, int> > > t;
void uni(ll n){
ll k = 1;
while(k < n)k *= 2;
t.resize(2 * k + 10);
}
void del(ll x, ll y, ll z, ll v = 1, ll l = 1, ll r = N){
if(l != r){
ll c = (l + r) / 2;
if(x <= c)del(x, y, z, v * 2, l, c);
else del(x, y, z, v * 2 + 1, c + 1, r);
}
t[v].erase({y, z});
}
void ins(ll x, ll y, ll z, ll v = 1, ll l = 1, ll r = N){
if(l != r){
ll c = (l + r) / 2;
if(x <= c)ins(x, y, z, v * 2, l, c);
else ins(x, y, z, v * 2 + 1, c + 1, r);
}
t[v].insert({y, z});
}
void get(ll l, ll r, ll x, ll v = 1, ll tl = 1, ll tr = N){
if(l > r)return;
if(tl == l && tr == r){
ans += t[v].size() - t[v].order_of_key(make_pair(x, -oo));
return;
}
ll c = (tl + tr) / 2;
get(l, min(r, c), x, v * 2, tl, c);
get(max(l, c + 1), r, x, v * 2 + 1, c + 1, tr);
}
} tree1488;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
set <ll> st, s2;
cin >> n >> Q;
fr(i, 1, n){
cin >> a[i];
st.insert(a[i]);
}
struct dt{
ll t, x, y;
};
vector <dt> q;
fr(z, 1, Q){
ll t;
cin >> t;
if(t == 1){
ll p, v;
cin >> p >> v;
q.pb({t, p, v});
st.insert(v);
} else{
ll x;
cin >> x;
s2.insert(x);
q.pb({t, x, x});
}
}
//сожмем координаты
ll now = 1;
for(auto i : st)nmb[i] = now ++;
for(auto i : s2){
auto it = st.upper_bound(i);
if(it == st.begin()){
nmb[i] = 0;
continue;
}
-- it;
nmb[i] = nmb[*it];
}
now --;
fr(i, 1, n)a[i] = nmb[a[i]];
tree1488.uni(now);
N = now;
a[0] = a[1];
fr(i, 1, n){
ll x = a[i - 1];
ll y = a[i];
if(x > y)swap(x, y);
if(x == y)mp[x] ++;
else tree1488.ins(x, y, i);
}
for(auto i : q){
ll t = i.t;
if(t == 1){
ll p = i.x;
ll v = nmb[i.y];
//удалить старую пару
if(p == 1 || a[p - 1] == a[p])mp[a[p]] --;
else {
ll x = a[p - 1], y = a[p];
if(x > y)swap(x, y);
tree1488.del(x, y, p);
}
if(p != n){
if(a[p + 1] == a[p])mp[a[p]] --;
else{
ll x = a[p + 1], y = a[p];
if(x > y)swap(x, y);
tree1488.del(x, y, p + 1);
}
}
a[p] = v;
//добавить новую пару
if(p == 1 || a[p - 1] == a[p])mp[a[p]] ++;
else {
ll x = a[p - 1], y = a[p];
if(x > y)swap(x, y);
tree1488.ins(x, y, p);
}
if(p != n){
if(a[p + 1] == a[p])mp[a[p]] ++;
else{
ll x = a[p + 1], y = a[p];
if(x > y)swap(x, y);
tree1488.ins(x, y, p + 1);
}
}
} else{
ans = 0;
ll x = nmb[i.x];
tree1488.get(1, x, x);
cout << ans << "\n";
}
}
}
/*
3 3
1 5 1
2 3
1 3 5
2 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
