#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
fast;
}
ll maxX = 2e6;
vi bit(4 * maxX);
void add(int i,int v)
{
for (;i<=maxX;i += i & (-i))bit[i] += v;
}
void add(int l,int r,int v)
{
if (l > r)swap(l,r);
add(l,v);
add(r + 1,-1);
}
int get(int i)
{
int ret = 0;
for (;i>0;i -= i &(-i))ret += bit[i];
return ret;
}
int main()
{
setIO();
int n,q;
cin>>n>>q;
vi h(n + 1);
for (int i = 1;i<=n;i++){
cin>>h[i];
if (i >= 2)
add(h[i - 1],h[i],1);
}
while (q--){
int t;
cin>>t;
if (t == 1){
int p,v;
cin>>p>>v;
if (p >= 2){
add(h[p - 1],h[p],-1);
add(h[p - 1],v,1);
}
if (p < n){
add(h[p],h[p + 1],-1);
add(v,h[p + 1],1);
}
h[p] = v;
}
else{
int H;
cin>>H;
cout<<get(H)<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
31564 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
31536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
31564 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
31536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
31564 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
31536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
