/*#pragma GCC optimize("O3")
#pragma GCC target("popcnt")*/
#include <bits/stdc++.h>
using namespace std;
#define IShowSpeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define popcnt __builtin_popcount
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mii map<int,int>
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define pb push_back
#define vt vector
#define endl '\n'
#define X first
#define Y second
typedef long double ld;
typedef long long ll;
const ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},N=3e5+10;
const ll mod=1e9+7,inf=1e18;
int n,q,y[N],t[5*N];
void upd(int l,int r,int val,int v=0,int tl=0,int tr=N) {
if(tl>=l && tr<=r){
t[v]+=val;
return;
}
if(tl+1>r || l+1>tr)return;
int mid=(tl+tr)>>1;
upd(l,r,val,v+v+1,tl,mid);
upd(l,r,val,v+v+2,mid,tr);
}
int get(int id,int res,int v=0,int tl=0,int tr=N) {
res+=t[v];
if(tr-tl==1)return res;
int mid=(tl+tr)>>1;
if(id<=mid) return get(id,res,v*2+1,tl,mid);
else return get(id,res,v*2+2,mid+1,tr);
}
void solve(){
cin>>n>>q;
for(int i=1; i<=n; ++i) cin>>y[i];
for(int i=1; i<n; ++i) {
int l=min(y[i],y[i+1]),r=max(y[i],y[i+1]);
upd(l-1,r,1);
}
while(q--){
int tp;
cin>>tp;
int i,d;
if(tp==1) {
cin>>i>>d;
if(i<n){
int l=min(y[i],y[i+1]),r=max(y[i],y[i+1]);
upd(l-1,r,-1);
}
if(i>1) {
int l=min(y[i],y[i-1]),r=max(y[i],y[i-1]);
upd(l-1,r,-1);
}
y[i]=d;
if(i<n){
int l=min(y[i],y[i+1]),r=max(y[i],y[i+1]);
upd(l-1,r,1);
}
if(i>1){
int l=min(y[i],y[i-1]),r=max(y[i],y[i-1]);
upd(l-1,r,1);
}
}
else{
cin>>d;
cout<<get(d-1,0)<<endl;
}
}
}
int main() {
IShowSpeed;
int tt=1;
//cin>>tt;
while(tt--) solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
