Problem of The Day 28 December — Xsquare And Two Arrays

Xsquare And Two Arrays

Xsquare loves to play with arrays a lot. Today, he has two arrays named as A and B. Each array consists of N positive integers.

Xsquare has decided to fulfill following types of queries over his array A and array B.

• 1 L R : Print the value of AL + BL+1 + AL+2 + BL+3 + … upto Rth term.
• 2 L R : Print the value of BL + AL+1 + BL+2 + AL+3 + … upto Rth term.

Input

First line of input contains two space separated integers N and Q denoting the size of arrays ( A , B ) and number of queries respectively. Next N lines of input contains N space separated integers denoting array A. Next line of input contains N space separated integers denoting array B. Next Q lines of input contains Q queries (one per line). Each query has one of the above mentioned types.

Output

Output consists of Q lines, each containing answer to the corresponding query.

Constraints

• 1 ≤ N,Q ≤ 105
• 1 ≤ Ai,Bi ≤ 109
• 1 ≤ L,R ≤ N

SAMPLE INPUT

5 5
1 2 3 4 5
5 4 3 2 1
1 1 5
2 1 5
1 2 4
2 2 4
1 3 5

SAMPLE OUTPUT

15
15
9
9
10

Explanation

Q1 : A[1] + B[2] + A[3] + B[4] + A[5] = 1 + 4 + 3 + 2 + 5 = 15 Q2 : B[1] + A[2] + B[3] + A[4] + B[5] = 5 + 2 + 3 + 4 + 1 = 15 Q3 : A[2] + B[3] + A[4] = 2 + 3 + 4 = 9 Q4 : B[2] + A[3] + B[4] = 4 + 3 + 2 = 9 Q5 : A[3] + B[4] + A[5] = 3 + 2 + 5 = 10

Problem Link: Xsquare and Two Array

Hint: Apply Dynammic Programming.
Solution will be posted tomorrow.

SOLUTION

This problem is one of a good example of using DP.
Simply store in dp1 value as
dp1[0] =0
dp1[1] =A1
dp1[2] =A1 + B2
dp1[3] =A1 + B2 +A3

dp2 value as
dp2[0] =0
dp2[1] =B1
dp2[2] =B1 + A2
dp2[3] =B1 + A2 +B3

Now if query come as 1 L R then check if L is not even then and query asked is 1 it means A1 + B2+A3 …. (1 just to indicate its even) so we print the value from dp1 and if L is even and query asked is 2 it means B2 + A3 + B3..(2 is to indicate its even) so we print the value from dp1.
For rest of the cases value will be from dp2.

CODE

#include<iostream>
using namespace std;
#define ll long long
int main()
{
    ll N,Q; cin>>N>>Q;
    ll A[N],B[N];
for(ll i=0;i<N;i++) cin>>A[i];
    for(ll i=0;i<N;i++) cin>>B[i];
// dp1 to store A1,B2,A3....
    //dp2 to store B1,A2,B3
    //dp1[5] = A1+B2+A3+B4+A5
    //dp2[5] = B1+A2+B3+A4+B5
    ll dp1[N+1],dp2[N+1];
dp1[0]=0;
    dp2[0]=0;
    dp1[1]=A[0];
    dp2[1]=B[0];
int flag=true;
    //simple logic to fill dp1 and dp2 array
    for(ll i=1;i<N;i++)
    {
        if(flag==true)
        {
            dp1[i+1] = dp1[i] + B[i];
            dp2[i+1] = dp2[i] + A[i];
        }
        else
        {
            dp1[i+1] = dp1[i] + A[i];
            dp2[i+1] = dp2[i] + B[i];
        }
        flag=!flag;
    }
/*for(ll i=1;i<=N;i++)
        cout<<dp1[i]<<endl;
    cout<<"dp2"<<endl;
    for(ll i=1;i<=N;i++)
        cout<<dp2[i]<<endl;*/
//solving each query if x=1 then it means it will start with A and if L is odd then it will be in dp1 as A1,A3 all in dp1
    // and if x=2 and L is  even it means it start with like B2,B4 and they are also in dp1
    //rest of all are in dp2
    for(ll i=1;i<=Q;i++) { 
        int x,L,R; cin>>x>>L>>R;
        if(x==1 && L%2==1 || x==2 && L%2==0)
            cout<<dp1[R]-dp1[L-1]<<endl;
else
            cout<<dp2[R]-dp2[L-1]<<endl;
     }
}