#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int f1[1000002];
int f2[1000002];
int n,m;
int nmax=1000001;
int h[100001];
int getsum1(int v){
int ans=0;
for(int i=v;i>=1;i=(i&(i-1))){
ans+=f1[i];
}
return ans;
}
int getsum2(int v){
int ans=0;
for(int i=v;i>=1;i=(i&(i-1))){
ans+=f2[i];
}
return ans;
}
void update1(int v,int x){
for(int i=v;i<=nmax;i=2*i-(i&(i-1))){
f1[i]+=x;
}
}
void update2(int v,int x){
for(int i=v;i<=nmax;i=2*i-(i&(i-1))){
f2[i]+=x;
}
}
int rangesum(int l,int r){
int sum1=getsum1(r)+getsum2(r)*r;
int sum2=getsum1(l-1)+getsum2(l-1)*(l-1);
return(sum1-sum2);
}
int rangeupdate(int l,int r,int x){
int u1=-(l-1)*x;
int u2=r*x;
update1(l,u1);
update1(r+1,u2);
update2(l,x);
update2(r+1,-x);
}
int main(){
cin>>n>>m;
for(int k=1;k<=n;k++){
cin>>h[k];
}
for(int k=2;k<=n;k++){
int l=min(h[k],h[k-1]);
int r=max(h[k],h[k-1]);
rangeupdate(l,r,1);
}
while(m--){
int ind;
cin>>ind;
if(ind==1){
int pos,val;
cin>>pos>>val;
if(pos>1&&pos<n){
int l1=min(h[pos],h[pos-1]);
int r1=max(h[pos],h[pos-1]);
int l2=min(h[pos],h[pos+1]);
int r2=max(h[pos],h[pos+1]);
h[pos]=val;
int l3=min(h[pos],h[pos-1]);
int r3=max(h[pos],h[pos-1]);
int l4=min(h[pos],h[pos+1]);
int r4=max(h[pos],h[pos+1]);
rangeupdate(l1,r1,-1);
rangeupdate(l2,r2,-1);
rangeupdate(l3,r3,1);
rangeupdate(l4,r4,1);
}
else{
if(pos==1){
int l2=min(h[pos],h[pos+1]);
int r2=max(h[pos],h[pos+1]);
h[pos]=val;
int l4=min(h[pos],h[pos+1]);
int r4=max(h[pos],h[pos+1]);
rangeupdate(l2,r2,-1);
rangeupdate(l4,r4,1);
}
else{
int l1=min(h[pos],h[pos-1]);
int r1=max(h[pos],h[pos-1]);
h[pos]=val;
int l3=min(h[pos],h[pos-1]);
int r3=max(h[pos],h[pos-1]);
rangeupdate(l1,r1,-1);
rangeupdate(l3,r3,1);
}
}
}
else{
int y;
cin>>y;
int ans=rangesum(y,y);
cout<<ans<<"\n";
}
}
return 0;
}
Compilation message
game.cpp: In function 'int rangeupdate(int, int, int)':
game.cpp:47:1: warning: no return statement in function returning non-void [-Wreturn-type]
47 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
