ALIN7-Editorial (2021 HEADLINES)

editorial
, , ,
1

PROBLEM LINK:

Contest

Author: Hareesh V

DIFFICULTY:

Easy-Medium

PREREQUISITES

Segment tree

PROBLEM:

You are given a sequence of n numbers you are tasked to perform 2 types of query on this sequence.

Query 1 x y is to find the number of terms in the sequence of the form 6N+1 and store this value as L and find the number of terms of the form 6N-1 and store this value as R. you have to print rangesum (min (L %n ,R %n ),max (L %n ,R %n ))
Query 2 i val- update the value of the ith element to val

EXPLANATION:

This problem can be easily solved using segment trees. Let’s store the sequence into an array, say Valarray.
Let the number of the form 6N+1 be A
Let the number of the form 6N-1 be B
Now let’s define two arays Aarray and Barray such that

  • Aarray[i] is 1 if the number at the ith position is of the form A else 0.
  • Barray[i] is 1if the number at the ith position is of the form B else 0.

Now we construct three range sum segment trees with Aarray,Barray,ValArray

After this the queries can be easy solved

Query 1:

1 x,y can be solved by finding range sum on Aarray and Barray in the given range(x,y) and let the range sum we got from Aarray be L and Barray be R. now solution to this query is sumrange(min(L%n,R%n),max(L%n,R%n)) on the given Valarray

Query 2:

2 i val this query is to update the value of ith index to val.for changing this we need to update all the tree segment tree segment trees.while updating the Aarray and Barray segment tree we need make sure if the val is of the form A and B and the value which is been replaced is of the form A and B

Update types in Aarray :

  • Initial value - of the form A
    Replaced value - of the form A

  • Initial value - not of the form A
    Replaced Value- not of the form A

    no  need to update for these two cases

  • Initial value - of the form A
    Replaced value -not of the form A

     Update with difference  -1

  • Initial value - not of the form A
    Replaced value -of the form A

     Update with difference 1

Similarly Barray updation can be done

This problem can also be solved using fenwick tree instead of segment tree

TIME COMPLEXITY

Time complexity is O(nlog(n))

SOLUTIONS:

Setter's Solution 
from math import ceil,log
def getmid(s,e):
    return s+(e-s)//2
def constsum(arr,n):
    h=ceil(log(n,2))
    max_size=2*(2**h)-1
    st=[0]*max_size
    constutilsum(arr,0,n-1,st,0)
    return st
def constutilsum(arr,ss,se,st,si):
    if(ss==se):
        st[si]=arr[ss]
        return arr[ss]
    mid=getmid(ss,se)
    st[si]=constutilsum(arr,ss,mid,st,si*2+1)+constutilsum(arr,mid+1,se,st,si*2+2)
    return st[si]
def getsum(st,n,qs,qe):
    return getsumutil(st,0,n-1,qs,qe,0)
def getsumutil(st,ss,se,qs,qe,si):
    if(qs<=ss and qe>=se):
        return st[si]
    if(se<qs or ss>qe):
        return 0
    mid=getmid(ss,se)
    return getsumutil(st,ss,mid,qs,qe,2*si+1)+getsumutil(st,mid+1,se,qs,qe,2*si+2)
def updatevalue(arr,st,n,i,new_val):
    diff=new_val-arr[i]
    arr[i]=new_val
    updatevalueutil(st,0,n-1,i,diff,0)
def updatevalueutil(st,ss,se,i,diff,si):
    if(i<ss or i>se):
        return
    st[si]=st[si]+diff
    if(se!=ss):
        mid=getmid(ss,se)
        updatevalueutil(st,ss,mid,i,diff,2*si+1)
        updatevalueutil(st,mid+1,se,i,diff,2*si+2)
        
n=int(input())
L=list(map(int,input()))
stsum=constsum(L,n)
r1=[0]*n
r2=[0]*n
for i in range(n):
    if((L[i]+1)%6==0):
        r1[i]=1
    elif((L[i]-1)%6==0):
        r2[i]=1
str1=constsum(r1,n)
str2=constsum(r2,n)
q=int(input())
for i in range(q):
    a,b,c=map(int,input().split())
    if(a==1):
        l=getsum(str1,n,b,c)%n
        r=getsum(str2,n,b,c)%n
        res=getsum(stsum,n,min(l,r),max(l,r))
        print(str(res))
    else:
        updatevalue(L,stsum,n,b,c)
        if((c+1)%6==0):
            updatevalue(r1,str1,n,b,1)
        else:
            updatevalue(r1,str1,n,b,0)
        if((c-1)%6==0):
            updatevalue(r2,str2,n,b,1)
        else:
            updatevalue(r2,str2,n,b,0)

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

2 Likes
2

Nice! Here’s my implementation where I used fenwick trees instead.

Solution 
#include "bits/stdc++.h"
#define int long long
#define rep(x, a, b) for (int x = a; x < b; ++x)
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;

    vector<int> ships(N);
    vector<int> Ls(N);
    vector<int> Rs(N);

    auto fsum = [] (vector<int>& Ar, int idx) {
        int result = 0;
        idx++;
        while (idx) {
            result += Ar.at(idx - 1);
            idx -= idx & -idx;
        }
        return result;
    };

    auto fadd = [] (vector<int>& Ar, int idx, int val) {
        if (!val) return;
        idx++;
        while (idx <= Ar.size()) {
            Ar.at(idx - 1) += val;
            idx += idx & -idx;
        }
    };

    int num;
    rep(i, 0, N) {
        cin >> num;
        fadd(ships, i, num);
        if (num % 6 == 5) fadd(Ls, i, 1);
        if (num % 6 == 1) fadd(Rs, i, 1);
    }

    int Q, qt;
    cin >> Q;

    while (Q--) {
        cin >> qt;
        if (qt == 1) {
            int x, y;
            cin >> x >> y;
            int L = (fsum(Ls, y) - fsum(Ls, x - 1)) % N;
            int R = (fsum(Rs, y) - fsum(Rs, x - 1)) % N;
            cout << fsum(ships, max(L, R)) - fsum(ships, min(L, R) - 1) << "\n";
        } else {
            int i, val;
            cin >> i >> val;
            int currentVal = fsum(ships, i) - fsum(ships, i - 1);
            int currentL = fsum(Ls, i) - fsum(Ls, i - 1);
            int currentR = fsum(Rs, i) - fsum(Rs, i - 1);
            fadd(ships, i, val - currentVal);
            fadd(Ls, i, (val % 6 == 5) - currentL);
            fadd(Rs, i, (val % 6 == 1) - currentR);
        }
    }
    return 0;
}
1 Like