#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){
t.resize(n + 10);
}
void del(ll x, ll y, ll z){
for(ll i = x; i <= N; i += i & -i)t[i].erase({y, z});
}
void ins(ll x, ll y, ll z){
for(ll i = x; i <= N; i += i & -i)t[i].insert({y, z});
}
ll get(ll x, ll y){
ll ans = 0;
for(ll i = x; i >= 1; i -= i & -i)ans += t[i].size() - t[i].order_of_key(make_pair(y, -oo));
return ans;
}
} 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 ++;
vector <ll> vv;
for(auto i : st)vv.pb(i);
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 = upper_bound(vv.begin(), vv.end(), i.x) - vv.begin(), y = x;
if(x < vv.size()){
if(vv[x] != i.x)y ++;
cout << tree1488.get(x, y) << endl;
}
}
}
}
/*
3 3
1 5 1
2 3
1 3 5
2 3
*/
Compilation message
game.cpp: In function 'int main()':
game.cpp:137:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x < vv.size()){
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4088 KB |
Output is correct |
| 3 |
Correct |
12 ms |
3960 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
4216 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4088 KB |
Output is correct |
| 3 |
Correct |
12 ms |
3960 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
4216 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4088 KB |
Output is correct |
| 3 |
Correct |
12 ms |
3960 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
4216 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
