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>
#define DIM 100010
using namespace std;
struct segment_tree{
int sum,lazy;
} aint[DIM*40];
int n,m,i,j,x,y,poz,val,q,tip;
int v[DIM];
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[fiu_st].sum += aint[nod].lazy;
aint[fiu_st].lazy += aint[nod].lazy;
aint[fiu_dr].sum += aint[nod].lazy;
aint[fiu_dr].lazy += aint[nod].lazy;
}
aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
aint[nod].sum += val;
aint[nod].lazy += val;
update_lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
aint[nod].sum = aint[(nod<<1)].sum + aint[(nod<<1)|1].sum;
}
int query (int nod, int st, int dr, int poz){
update_lazy(nod,st,dr);
if (st == dr)
return aint[nod].sum;
int mid = (st+dr)>>1;
if (poz <= mid)
return query (nod<<1,st,mid,poz);
else return query ((nod<<1)|1,mid+1,dr,poz);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>q;
for (i=1;i<=n;i++)
cin>>v[i];
m = 1000000;
//m = 7;
for (i=1;i<n;i++){
int x = v[i], y = v[i+1];
if (x > y)
swap (x,y);
update (1,1,m,x,y,1);
}
for (i=2;i<n;i++)
update (1,1,m,v[i],v[i],-1);
for (;q--;){
cin>>tip;
if (tip == 1){
cin>>poz>>val;
if (poz > 1){
int x = v[poz-1], y = v[poz];
if (x > y)
swap (x,y);
update (1,1,m,x,y,-1);
}
if (poz < n){
int x = v[poz], y = v[poz+1];
if (x > y)
swap (x,y);
update (1,1,m,x,y,-1);
}
if (poz > 1 && poz < n)
update (1,1,m,v[poz],v[poz],1);
v[poz] = val;
if (poz > 1){
int x = v[poz-1], y = v[poz];
if (x > y)
swap (x,y);
update (1,1,m,x,y,1);
}
if (poz < n){
int x = v[poz], y = v[poz+1];
if (x > y)
swap (x,y);
update (1,1,m,x,y,1);
}
if (poz > 1 && poz < n)
update (1,1,m,v[poz],v[poz],-1);
} else {
cin>>poz;
cout<<query(1,1,m,poz)<<"\n";
}
}
return 0;
}/// copy paste ioit
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |