#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
if(b==0)return 1;
if(b%2==0){
ll t=bin_pow(a,b/2);
return t*t%MOD;
}
else return a*bin_pow(a,b-1)%MOD;
}
ll sum[4000005];
void update(int idx,int val,int v,int tl,int tr){
if(idx==tl&&tl==tr){
sum[v]+=val;
return;
}
if(tl>idx||tr<idx)return;
int tm=(tl+tr)/2;
update(idx,val,2*v,tl,tm),update(idx,val,2*v+1,tm+1,tr);
sum[v]=sum[2*v]+sum[2*v+1];
}
ll sum1(int idx,int v,int tl,int tr){
if(tl>=0&&tr<=idx)return sum[v];
if(tl>idx||tr<0)return 0;
int tm=(tl+tr)/2;
return sum1(idx,2*v,tl,tm)+sum1(idx,2*v+1,tm+1,tr);
}
int main()
{
//freopen("stones.in","r",stdin);
//freopen("stones.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
cin>>n>>m;
vector<ll>a(n);
for(int i=0;i<n;i++)cin>>a[i];
update(a[0],1,1,0,n-1);
update(a[0]+1,-1,1,0,n-1);
for(int i=1;i<n;i++){
l=a[i-1],r=a[i];
if(l>r)swap(l,r);
if(a[i-1]>=a[i])r--;
else l++;
update(l,1,1,0,n-1);
update(r+1,-1,1,0,n-1);
}
while(m--){
cin>>z;
if(z==1){
cin>>x>>y;
x--;
if(x){
l=a[x-1],r=a[x];
if(l>r)swap(l,r);
if(a[x-1]>=a[x])r--;
else l++;
update(l,-1,1,0,n-1);
update(r+1,1,1,0,n-1);
}
else{
update(a[0],-1,1,0,n-1);
update(a[0]+1,1,1,0,n-1);
}
if(x<n-1){
l=a[x+1],r=a[x];
if(l>r)swap(l,r);
if(a[x]>=a[x+1])r--;
else l++;
update(l,-1,1,0,n-1);
update(r+1,1,1,0,n-1);
}
a[x]=y;
if(x){
l=a[x-1],r=a[x];
if(l>r)swap(l,r);
if(a[x-1]>=a[x])r--;
else l++;
update(l,1,1,0,n-1);
update(r+1,-1,1,0,n-1);
}
else{
update(a[0],1,1,0,n-1);
update(a[0]+1,-1,1,0,n-1);
}
if(x<n-1){
l=a[x+1],r=a[x];
if(l>r)swap(l,r);
if(a[x]>=a[x+1])r--;
else l++;
update(l,1,1,0,n-1);
update(r+1,-1,1,0,n-1);
}
}
else{
cin>>x;
ans=sum1(x,1,0,n-1);
cout<<ans;
cout<<"\n";
}
}
return 0;
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:38:8: warning: unused variable 't' [-Wunused-variable]
38 | ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
| ^
game.cpp:38:16: warning: unused variable 'k' [-Wunused-variable]
38 | ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
| ^
game.cpp:38:20: warning: unused variable 'sum' [-Wunused-variable]
38 | ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
| ^~~
game.cpp:38:52: warning: unused variable 'mn' [-Wunused-variable]
38 | ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
| ^~
game.cpp:38:65: warning: unused variable 'mx' [-Wunused-variable]
38 | ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
