In this HackerEarth Incremental queries problem solution You are given an array A consisting of N elements A1,A2,A3,...,AN. You must process N queries and there are two types of queries:
  1. L R: Replace Lth element by R, that is, AL = R.
  2. L R: You are required to print the minimum number of operations to make all elements equal in subarrays AL, AL+1, ..., AR.
You can perform the following operation in order to make elements equal:

Select any index L and replace AL with AL + 1 or AL + 2.


HackerEarth Incremental queries problem solution


HackerEarth Incremental queries problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll txtc; cin>>txtc; while(txtc--)
typedef long long int ll;
typedef long double ld;
ll a[200001];
struct obj{
ll sum,odd,even,maxm;
};
obj ans;
obj seg_tree[4*200001];
void build(int index,int l,int r){
if(l==r){
seg_tree[index].sum=a[l];
seg_tree[index].odd=(a[l]%2);
seg_tree[index].even=(a[l]%2==0?1:0);
seg_tree[index].maxm=a[l];
return ;
}
ll mid=(l+r)/2;
build(2*index+1,l,mid);
build(2*index+2,mid+1,r);
seg_tree[index].sum=seg_tree[2*index+1].sum+seg_tree[2*index+2].sum;
seg_tree[index].odd=seg_tree[2*index+1].odd+seg_tree[2*index+2].odd;
seg_tree[index].even=seg_tree[2*index+1].even+seg_tree[2*index+2].even;
seg_tree[index].maxm=max({seg_tree[2*index+1].maxm,seg_tree[2*index+2].maxm});
}
void update(int index,int l,int r,int node,ll val){
if(l==r){
seg_tree[index].sum=val;
seg_tree[index].odd=(val%2);
seg_tree[index].even=(val%2==0?1:0);
seg_tree[index].maxm=val;
return ;
}
int mid=(l+r)/2;
if(node>=l && node<=mid) update(2*index+1,l,mid,node,val);
else update(2*index+2,mid+1,r,node,val);
seg_tree[index].sum=seg_tree[2*index+1].sum+seg_tree[2*index+2].sum;
seg_tree[index].odd=seg_tree[2*index+1].odd+seg_tree[2*index+2].odd;
seg_tree[index].even=seg_tree[2*index+1].even+seg_tree[2*index+2].even;
seg_tree[index].maxm=max({seg_tree[2*index+1].maxm,seg_tree[2*index+2].maxm});
}
void query(int index,int low,int high,int l,int r){
//cout<<index<<" "<<low<<" "<<high<<" "<<l<<" "<<r<<endl;
if(low>=l && high<=r){
ans.sum+=seg_tree[index].sum;
ans.odd+=seg_tree[index].odd;
ans.even+=seg_tree[index].even;
ans.maxm=max(ans.maxm,seg_tree[index].maxm);
return;
}
if(low>r || high<l){
return;
}
ll mid=(low+high)/2;
query(2*index+1,low,mid,l,r);
query(2*index+2,mid+1,high,l,r);
}
ll solve(ll l, ll r,ll n){
l--; r--;
ans.sum=0; ans.odd=0; ans.even=0; ans.maxm=0;
query(0,0,n-1,l,r);
//cout<<"sum="<<ans.sum<<" odd="<<ans.odd<<" even="<<ans.odd<<" maxm="<<ans.maxm<<endl;
ll res=0,to_sum;
to_sum=ans.maxm*(r-l+1);
to_sum-=ans.sum;
if(ans.maxm%2==1){
res+=ans.even;
to_sum-=ans.even;
}
else{
res+=ans.odd;
to_sum-=ans.odd;
}
res+=(to_sum/2);
return res;
}
int main() {
FIO;
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
build(0,0,n-1);
while(m--){
ll type,l,r;
cin>>type>>l>>r;
if(type==1){
l--;
update(0,0,n-1,l,r);
a[l]=r;
}
else{
cout<<solve(l,r,n)<<endl;
}
}
return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 14;
struct Node{
int mx, cnt[2];
ll sum;
Node(){
mx = sum = cnt[0] = cnt[1] = 0;
}
Node(int x){
sum = mx = x;
cnt[x % 2] = 1;
cnt[!(x % 2)] = 0;
}
ll ans(){
return (mx * ll(cnt[0] + cnt[1]) - sum) / 2 + (cnt[!(mx % 2)] + 1) / 2;
}
Node operator +(Node o) const{
o.mx = max(o.mx, mx);
o.sum = o.sum + sum;
o.cnt[0] += cnt[0];
o.cnt[1] += cnt[1];
return o;
}
} seg[maxn * 2];
int n, q;
void upd(int p, int x){
for(seg[p += n] = x; p >>= 1; )
seg[p] = seg[p * 2] + seg[p * 2 + 1];
}
Node get(int l, int r){
Node ans;
for(l += n, r += n; l < r; l >>= 1, r >>= 1){
if(l % 2)
ans = seg[l++] + ans;
if(r % 2)
ans = ans + seg[--r];
}
return ans;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for (int i = n; i < 2 * n; i++){
int x;
cin >> x;
seg[i] = x;
}
for(int i = n - 1; i > 0; i--)
seg[i] = seg[i * 2] + seg[i * 2 + 1];
while(q--){
int t, l, r;
cin >> t >> l >> r;
l--;
if(t == 1)
upd(l, r);
else
cout << get(l, r).ans() << '\n';
}
}