# Dynamic Array

### Problem Statement :

```Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing.
Create an integer, lastAnswer, and initialize it to 0.
There are 2 types of queries that can be performed on the list of sequences:
1. Query: 1 x y
a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
b. Append integer y to sequence seq.
2. Query: 2 x y
a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
b. Find the value of element y%size in seq (where size is the size of seq) and assign it to
c. Print the new value of lastAnswer on a new line

Note: xor is the bitwise XOR operation, which corresponds to the ^ operator in most languages. Learn more about it on Wikipedia.  is the modulo operator.

Function Description:

Complete the dynamicArray function below.

dynamicArray has the following parameters:
- int n: the number of empty sequences to initialize in seqList.
- string queries[q]: an array of query strings

Returns

int[]: the results of each type 2 query in the order they are presented

Input Format:

The first line contains two space-separated integers, n (the number of sequences) and q (the number of queries), respectively.
Each of the  subsequent lines contains a query in the format defined above, queries[i].

Constraints:
1. 1<=n,q<=10^5
2. 0<=x<=10^9
3. 0<=y<=10^9
4. It is guaranteed that query type  will never query an empty sequence or index.```

### Solution :

```                            ```Solution in C :

In C:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MAX_N_Q 100000

#define MAX_X_Y 1000000000

typedef struct linklist {
int data;

typedef struct {
int size;
}SEQUENCE;

{

if (head == NULL) {
} else {
while(temp->next != NULL)
temp = temp->next;

newnode->next = NULL;
temp->next = newnode;
}

}

while(temp)	{
printf("%d",temp->data);
temp = temp->next;
if (temp!=NULL)
printf("\n");
}
}

int main()
{
int N, Q;
int i = 0;
int choice, x, y, index;
int lastans = 0;
SEQUENCE *s = NULL;
linklistp node, temp, output = NULL, outnode;

scanf("%d", &N);
if (N < 1 || N > MAX_N_Q) {
return 1;
}
scanf("%d", &Q);
if (Q < 1 || Q > MAX_N_Q) {
return 1;
}

s = malloc(sizeof(SEQUENCE)*N);
if(s == NULL) {
return 1;
}

memset(s, 0, sizeof(SEQUENCE)*N);

do {
scanf("%d", &choice);
scanf("%d", &x);
scanf("%d", &y);

if (choice != 1 && choice != 2) {
return 1;
}

if (x < 0 || x > MAX_X_Y) {
return 1;
}

if (y < 0 || y > MAX_X_Y) {
return 1;
}

switch(choice){
case 1:
index = (x^lastans)%N;
if (node == NULL)
return 1;
node->data = y;
node->next = NULL;

s[index].size ++;
break;

case 2:
index = (x^lastans)%N;
y = y % (s[index].size);

while ( y > 0) {
temp = temp->next;
y--;
}

lastans = temp->data;
outnode ->data = temp->data;
output = insert_tail(output, outnode);
break;

}

i++;

}while (i < Q);

if (output != NULL)

return 0;
}

In C++:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int n, q;
int lastans = 0;
cin >> n >> q;
vector<vector<int>>sqces(n);
while (q--)
{
int a;
long long x, y;
cin >> a >> x >> y;
long long t = (x^lastans) % n;
if (a == 1)
{
sqces[t].push_back(y);
}
else
{
long long size = sqces[t].size();
long long b;
if (size != 0)
b = y%size;
else
continue;
cout << sqces[t][b] << endl;
lastans =sqces[t][b];
}
}
return 0;
}

In Java:

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
List<Integer>[] sequences = new List[n];
for (int n_i = 0; n_i < n; n_i++) {
sequences[n_i] = new ArrayList<>();
}
int lastans = 0;
for (int i = 0; i < q; i++) {
int t = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
List<Integer> sequence = sequences[(x^lastans)%n];
switch (t) {
case 1:
break;
case 2:
lastans = sequence.get(y%sequence.size());
System.out.println(lastans);
break;
}
}
}
}

In Python 3:

n, q = map(int, input().split())
l = [[] for _ in range(n)]

latsans = 0
for _ in range(q):
a, x, y = map(int, input().split())
if a == 1:
l[(x^latsans)%n].append(y)
else:
t = (x^latsans)%n
latsans = l[t][y%len(l[t])]
print(latsans)
#print(a, x, y, l)```
```

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty