This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define fs first
#define ss second
#define all(a) a.begin(), a.end()
#define print(a) \
for (auto x : a) \
cout << x << ' '; \
cout << endl;
#define printmp(a) \
for (auto x : a) \
cout << x.fs << ' ' << x.ss << endl;
struct SegTree
{
int size = 1;
vector<int> sums;
SegTree (){
while(1e6 > size)
size <<= 1;
sums.resize(size << 1);
}
void add(int l, int r, int i, int x, int lx, int rx){
if(l <= lx and rx <= r){
sums[x] += i;
return;
}
if(r <= lx or rx <= l)
return;
int m = (lx + rx) >> 1;
add(l, r, i, (x << 1) + 1, lx, m);
add(l, r, i, (x << 1) + 2, m, rx);
}
void add(int l, int r, int i){
if(l > r)
swap(l, r);
add(l, r, i, 0, 0, size);
}
int ans(int h, int x, int lx, int rx){
if(rx == lx + 1)
return sums[x];
int m = (lx + rx) >> 1;
if(h < m)
return sums[x] + ans(h, (x << 1) + 1, lx, m);
else
return sums[x] + ans(h, (x << 1) + 2, m, rx);
}
int ans(int h){
return ans(h, 0, 0, size);
}
};
void solve()
{
int n, m;
cin >> n >> m;
vector<int> h(n);
for(int i = 0; i < n; i ++)
cin >> h[i];
SegTree s;
for(int i = 1; i < n; i ++)
s.add(h[i - 1], h[i], 1);
while(m --){
int type;
cin >> type;
if(type == 1){
int i, v;
cin >> i >> v;
if(n == 1)
continue;
if(i == 1){
s.add(h[i], h[i - 1], -1);
h[i - 1] = v;
s.add(h[i], h[i - 1], 1);
}
else if(i == n){
s.add(h[i - 2], h[i - 1], -1);
h[i - 1] = v;
s.add(h[i - 2], h[i - 1], 1);
}
else{
s.add(h[i], h[i - 1], -1);
s.add(h[i], v, 1);
s.add(h[i - 2], h[i - 1], -1);
h[i - 1] = v;
s.add(h[i - 2], h[i - 1], 1);
}
}
else{
int h;
cin >> h;
if(n == 1){
cout << 0 << endl;
continue;
}
cout << s.ans(h) << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--)
{
solve();
cout << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |