[solved] Array queries

 Problem (Array queries) : 

You are given 2 arrays A and B of length N and M respectively. You define F(A, B) as follows:

                                                    $�(�,�)=\sum _{�=1}^{�}\sum _{�=1}^{�}�[�]\times �[�]\times (�+�)$

You are also given an integer Q denoting the Q queries of the following types:

• 1 i j: Swap A[i] and B[j], that is you replace the i^th element in A with B[j] and j^th element in B with A[i]
• 2 i j: Swap A[i] and A[j], as described above
• 3 i j: Swap B[i] and B[j], as described above

Task

Given Q queries in form of array queries, you need to output Q + 1 integers. The initial value of F(A, B) and the values after each query. The value of F(A, B) can be very large so, output the values modulo 998244353.

Notes

• Assume 1-based indexing
• Queries are dependent.

Example

Assumptions

• T = 1
• N = 2
• M = 2
• A = [2, 4]
• B = [1, 5]
• Q = 1
• queries = [ [1, 2, 1] ]

Approach

• You first evaluate F(A, B) = A[1]*B[1]*( 1 + 1 ) + A[1]*B[2]*( 1 + 2 ) + B[1]*A[2]*( 1 + 2 ) + B[2]*A[2]*( 2 + 2 ) = 2*1*2 + 2*5*3 + 1*4*3 + 5*4*4 = 4 + 30 + 12 + 80 = 126.
• You swap A[2] and B[1], therefore A becomes [2, 1] and B becomes [4, 5], F(A, B) = A[1]*B[1]*( 1 + 1 ) + A[1]*B[2]*( 1 + 2 ) + B[1]*A[2]*( 1 + 2 ) + B[2]*A[2]*( 2 + 2 ) = 2*4*2 + 2*5*3 + 4*1*3 + 1*5*4 = 16 + 30 + 12 + 20 = 78.
• You, therefore, output "126 78" in a single line.

Function description

Complete the array_queries function provided in the editor. This function takes the following 6 parameters and returns a vector/array denoting the values of F(A, B) for all queries:

• N: Represents an integer denoting the length of array A
• M: Represents an integer denoting the length of array B
• A: Represents the integer array A
• B: Represents the integer array B
• Q: Represents an integer denoting the number of queries
• queries: Represents a 2D array/vector denoting queries of the type "1 i j" or "2 i j" or "3 i j". Therefore, the size of the queries array is Q*3.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer T, which denotes the number of test cases. T also specifies the number of times you have to run the array_queries function on a different set of inputs.
• For each test case:
  • The first line contains an integer N denoting the length of the array A.
  • The second line contains an integer M denoting the length of the array B.
  • The third line contains N space-separated integers denoting array A.
  • The fourth line contains M space-separated integers denoting array B.
  • The fifth line contains an integer Q denoting the number of queries.
  • The next Q lines follow. For each line:
    • The first line contains three space-separated integers denoting tp, i and j, where tp = 1, 2 or 3.

Output format

For each test case in a new line, print Q + 1 space-separated integers denoting the initial value of F(A, B) and F(A, B) after each query. Do not forget to take modulo 998244353.

Constraints

$$\begin{gathered} 1\le �\le 10 \\ 1\le �,�\le {10}^5 \\ 1\le �[�],�[�]\le {10}^6 \\ 1\le �\le {10}^5 \\ \text{If query is of type 1: }1\le �\le �,1\le �\le � \\ \text{If query is of type 2: }1\le �,�\le � \\ \text{If query is of type 3: }1\le �,�\le � \end{gathered}$$

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.

Sample Input

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

Sample Output

126 78
134 168 168 175

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

The first line contains the number of test cases, T = 2.

The first test case

The first test case is the same as the example. Please refer to that.

The second test case

Assumptions

• T = 1
• N = 3
• M = 2
• A = [3, 5, 1]
• B = [4, 1]
• Q = 3
• queries = [ [1, 1, 2], [2, 1, 3], [3, 1, 2] ]

Approach

• You first evaluate F(A, B) = A[1]*B[1]*( 1 + 1 ) + A[1]*B[2]*( 1 + 2 ) + A[2]*B[1]*( 2 + 1 ) + A[2]*B[2]*( 2 + 2 ) + A[3]*B[1]*( 3 + 1 ) + A[3]*B[2]*( 3 + 2 ) = 3*4*2 + 3*1*3 + 5*4*3 + 5*1*4 + 1*4*4 + 1*1*5 = 24 + 9 + 60 + 20 + 16 + 5 = 134.
• You swap A[1] and B[2], therefore A becomes [1, 5, 1] and B becomes [4, 3], F(A, B) = 1*4*2 + 1*3*3 + 5*4*3 + 5*3*4 + 1*4*4 + 1*3*5 = 8 + 9 + 60 + 60 + 16 + 15 = 168.
• You swap A[1] and A[3], therefore A becomes [1, 5, 1] and B remains the same. Recall that queries are dependent. The value of F(A, B) comes out to be 168.
• You swap B[1] and B[2], therefore A remained the same and B becomes [3, 4]. Recall that queries are dependent. The value of F(A, B) comes out to be 175.
• You, therefore, output "134 168 168 175" in a single line.

Solution (C++) :-

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define REP(i, n) for(int i = 0; i < (int) (n); i++)

#define FOR(i, a, b) for(int i = (a); i < (int) (b); i++)

using namespace std;

const int MOD = 998244353;

void solve(void);

int calcMOD(long long num) {

    num %= MOD;

    num += MOD;

    num %= MOD;

    return num;

}

int main() {

    IOS

    int t;

    cin >> t;

    while(t--) {

        solve();

    }

    return 0;

}

void solve(void) {

    int n, m;

    cin >> n >> m;

    vector<long long> a(n), b(m);

    long long sumA = 0, wSumA = 0, sumB = 0, wSumB = 0, ans;

    REP(i, n) {

        cin >> a[i];

        sumA += a[i];

        sumA %= MOD;

        wSumA += (i + 1) * a[i];

        wSumA %= MOD;

    }

    REP(j, m) {

        cin >> b[j];

        sumB += b[j];

        sumB %= MOD;

        wSumB += (j + 1) * b[j];

        wSumB %= MOD;

    }

    ans = sumA * wSumB + sumB * wSumA;

    ans %= MOD;

    cout << ans << ' ';

    int q;

    cin >> q;

    while(q--) {

        int op, i, j;

        cin >> op >> i >> j;

        i--, j--;

        if(op == 1) {

            sumA = calcMOD(sumA - a[i] + b[j]);

            wSumA = calcMOD(wSumA + (i + 1) * (b[j] - a[i]));

            sumB = calcMOD(sumB - b[j] + a[i]);

            wSumB = calcMOD(wSumB + (j + 1) * (a[i] - b[j]));

            swap(a[i], b[j]);

        }

        else if(op == 2) {

            wSumA = calcMOD(wSumA + (j - i) * (a[i] - a[j]));

            swap(a[i], a[j]);

        }

        else {

            wSumB = calcMOD(wSumB + (j - i) * (b[i] - b[j]));

            swap(b[i], b[j]);

        }

        ans = sumA * wSumB + sumB * wSumA;

        ans %= MOD;

        cout << ans << ' ';

    }

    cout << '\n';

}

Recommended Post :-

HCL Coding Questions:-

• Count Even Sum
  
• Length of Hypotenuse
  

Capgemini Coding Questions:-

• Move Hash
  
• Character with their frequency
  

iMocha coding Questions:-

• Mathematical Calculation: Prime number
  
• Mathematical calculation : odd numbers
  

Tech Mahindra coding questions:-

• Find Even odd difference
  
• Find Total curtains
  
• Find odd even difference
  
• Find total sum
  

Unthinkable Solutions coding questions:-

• Swap the adjacent characters of the string
  
• Double the vowel characters in the string
  
• Character with their frequency
  
• Program to find the closest value
  

Must check this:-

• PPS lab all the problems of 1st year 
• C- program of CPU scheduling Algorithms

Companies interview:-

• Swap adjacent characters 
• Double the vowel characters
  
• Check valid parenthesis
  
• Print the characters with their frequencies
  
• Find closest value
  
• Word Count
•  Program of CaesarCipher
• Program to find the perfect city
• Annual Day | Tech Mahindra coding question
• Find the number of pairs in the array whose sum is equal to a given target.

Full C course:-    

• C -Tutorial
  

Key points:-

• How to set limit in the floating value in python
  
• What is boolean data type
• How to print any character without using format specifier
• How to check that given number is power of 2 or not
  
• How to fix limit in double and floating numbers after dot (.) in c++
  
• How to print a double or floating point number in scientific notation and fixed notation
  
• How to take input a string in c
  
• How to reduce the execution time of program in c++.
  

Cracking the coding interview:-

 Array and string:-

• Is Unique
  
• Check Permutation
  
• Urlify
  
• One away
  
• String Compression
  
• Zero matrix
  

Tree and graph:-

• Route between nodes
  
• Minimal Tree
  
• List of Depth
  
• Validate BST
  
• Successor
  

Hackerearth Problems:-

• Very Cool numbers | Hacker earth solution
• Vowel Recognition | Hackerearth practice problem solution
  
• Birthday party | Hacker earth solution
• Most frequent | hacker earth problem solution
• program to find symetric difference of two sets
•  cost of balloons | Hacker earth problem solution
• Chacha o chacha | hacker earth problem solution
• jadu and dna | hacker earth solution
• Bricks game | hacker earth problem
• Anti-Palindrome strings | hacker earth solution
• connected components in the graph | hacker earth data structure
• odd one out || hacker earth problem solution
• Minimum addition | Hackerearth Practice problem
  
• The magical mountain | Hackerearth Practice problem
  
• The first overtake | Hackerearth Practice problem
  

Hackerrank Problems:-

•  Playing With Characters | Hackerrank practice problem solution
• Sum and Difference of Two Numbers | hackerrank practice problem solution
  
• Functions in C | hackerrank practice problem solution
  
• Pointers in C | hackerrank practice problem solution
  
• Conditional Statements in C | Hackerrank practice problem solution
  
• For Loop in C | hackerrank practice problem solution
  
• Sum of Digits of a Five Digit Number | hackerrank practice problem solution
  
• 1D Arrays in C | hackerrank practice problem solution
  
• Array Reversal | hackerrank practice problem solution
  
• Printing Tokens | hackerrank practice problem solution
  
• Digit Frequency | hackerrank practice problem solution
  
• Calculate the Nth term | hackerrank practice problem solution

Data structure:-

•   Program to find cycle in the graph
• Implementation of singly link list
• Implementation of queue by using link list
• Algorithm of quick sort
• stack by using link list
• program to find preorder post order and inorder of the binary search tree
• Minimum weight of spanning tree
  
• Preorder, inorder and post order traversal of the tree

Must check this:-

• PPS lab all the problems of 1st year 
• C- program of CPU scheduling Algorithms

 MCQs:-

• Engineering mathematics -4 MCQs
• CSS (Computer cyber security ) MCQS