Read problems statements [Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

There are two sequences $A_{1}, A_{2}, \dots, A_{N}$ and $B_{1}, B_{2}, \dots, B_{N}$. Answer $Q$ queries on these sequences.

In each query, you should calculate the dot product of subsequences $A_{x}, A_{x+1}, \dots, A_{x+l-1}$ and $B_{y}, B_{y+1}, \dots, B_{y+l-1}$, i.e. the value of the expression
$$\sum_{k=0}^{l-1} A_{x+k} B_{y+k} \,.$$

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$.
Each of the following $Q$ lines contains three space-separated integers $x$, $y$ and $l$ describing one query.

------  Output ------
For each query, print a single line containing one integer — the answer to the query (the dot product).

------  Constraints  ------
$1 ≤ T ≤ 30,000$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ A_{i}, B_{i} ≤ 10^{4}$ for each valid $i$
the sum of $N$ for all test cases does not exceed $10^{5}$
the sum of $Q$ for all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
1
5 2
4 6 5 2 7
3 2 4 6 3
2 4 2
1 1 1
----- Sample Output 1 ------ 
51
12

Source: codechef | Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Square root algorithms

Mathematics


Solutions:
import numpy as np
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = np.array([int(i) for i in input().split()])
	b = np.array([int(i) for i in input().split()])
	for i in range(q):
		(x, y, l) = [int(i) for i in input().split()]
		print(np.dot(a[x - 1:x + l - 1], b[y - 1:y + l - 1]))


import math
from sys import stdin, stdout
import random
import array as arr
import numpy as np
from sys import stdin, stdout
from collections import OrderedDict
from collections import defaultdict
from collections import deque
import heapq as hq

def get_input():
	return list(map(int, stdin.readline().strip().split()))

def single_input():
	return int(input())

def simple_input():
	return input()

def solve():
	(n, q) = get_input()
	a = np.array(get_input())
	a = np.insert(a, 0, 0)
	b = np.array(get_input())
	b = np.insert(b, 0, 0)
	for i in range(q):
		(x, y, l) = get_input()
		print(np.dot(a[x:x + l], b[y:y + l]))

def main():
	temp = get_input()
	t = temp[0]
	for i in range(t):
		solve()
main()


import numpy as np
for i in range(int(input())):
	(n, q) = (int(s) for s in input().split())
	A = np.array([int(s) for s in input().split()])
	B = np.array([int(s) for s in input().split()])
	for j in range(q):
		(x, y, l) = (int(s) for s in input().split())
		print(np.dot(A[x - 1:x + l - 1], B[y - 1:y + l - 1]))


import numpy as np
T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	A = np.fromstring(input(), dtype=np.int64, sep=' ')
	B = np.fromstring(input(), dtype=np.int64, sep=' ')
	for _ in range(Q):
		(i, j, k) = list(map(int, input().split()))
		i -= 1
		j -= 1
		print(np.dot(A[i:i + k], B[j:j + k]))


import numpy as np
for _ in range(int(input())):
	(n, q) = [int(x) for x in input().split()]
	a = np.array([int(x) for x in input().split()])
	b = np.array([int(x) for x in input().split()])
	while q:
		(x, y, l) = [int(x) for x in input().split()]
		print(np.dot(a[x - 1:x + l - 1], b[y - 1:y + l - 1]))
		q -= 1