#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define tree zalupa
#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 N = (ll)500000 + 10;
const ll oo = ll(1e9) + 10;
ll n, Q;
ll a[N], mp[N];
struct SegmentTree{
vector < _set < pair < int, int> > > t;
void uni(){
t.resize(N * 4);
}
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});
}
ll get(ll l, ll r, ll x, ll v = 1, ll tl = 1, ll tr = N){
if(l > r)return 0;
if(tl == l && tr == r){
pll p;
p = make_pair(x, -oo);
ll v1 = t[v].order_of_key(p);
return t[v].size() - v1;
}
ll c = (tl + tr) / 2;
return 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);
tree1488.uni();
cin >> n >> Q;
fr(i, 1, n)cin >> a[i];
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);
}
//cout << "kjfd" << endl;
fr(z, 1, Q){
ll t;
cin >> t;
if(t == 1){
ll p, v;
cin >> p >> v;
if(v > N)cout << 1 / 0;
//удалить старую пару
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{
ll x, ans = 0;
cin >> x;
ans = tree1488.get(1, x, x);
cout << ans << "\n";
}
}
}
/*
3 3
1 5 1
2 3
1 3 5
2 3
*/
Compilation message
game.cpp: In function 'int main()':
game.cpp:85:32: warning: division by zero [-Wdiv-by-zero]
if(v > N)cout << 1 / 0;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
188152 KB |
Output is correct |
| 2 |
Execution timed out |
1101 ms |
189536 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
188152 KB |
Output is correct |
| 2 |
Execution timed out |
1101 ms |
189536 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
188152 KB |
Output is correct |
| 2 |
Execution timed out |
1101 ms |
189536 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
