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;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb push_back
const int mxN = (1e6 + 1);
int tree[(int) 1e6 + 1] = {};
int n;
int sum(int k) {
int s = 0;
while(k >= 1) {
s += tree[k];
k -= k&-k;
}
return s;
}
void add(int k, int x) {
while(k <= mxN) {
tree[k] += x;
k += k&-k;
}
}
void newL(int a, int b) {
if(a > b)
swap(a, b);
add(a + 1, 1);
add(b, -1);
}
void removeL(int a, int b) {
if(a > b)
swap(a, b);
add(a + 1, -1);
add(b, 1);
}
void solve()
{
int m;
cin >> n >> m;
int a[n + 1];
FOR(i, 1, n + 1)
cin >> a[i];
FOR(i, 2, n + 1) {
newL(a[i], a[i - 1]);
}
FOR(i, 0, m) {
int x;
cin >> x;
if(x == 1) {
int p, h;
cin >> p >> h;
if(p != 1) {
removeL(a[p], a[p - 1]);
newL(a[p - 1], h);
}
if(p != n) {
removeL(a[p], a[p + 1]);
newL(a[p + 1], h);
}
a[p] = h;
} else {
int p;
cin >> p;
cout << sum(p) << nl;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |