## Algorithm

Problem Name: Data Structures - Array and simple queries

In this HackerRank in Data Structures - Array and simple queries solutions

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 M 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.
• Type 2 queries are represented as `2 i j` : Modify the given array by removing elements from i to j and adding them to the back.

Your task is to simply print |A[1] - A[N]| of the resulting array after the execution of M queries followed by the resulting array.

Note While adding at back or front the order of elements is preserved.

Input Format

First line consists of two space-separated integers, N and M.

Second line contains N integers, which represent the elements of the array. M queries follow. Each line contains a query of either type 1 or type 2 in the form type i j

Constraints

• 1 <= M, N <= 10**5
• 1 <= A[i] <= 10**9
• 1 <= i <= j <= N

Output Format

Print the absolute value i.e. abs(A[1] - A[N])

in the first line.
Print elements of the resulting array in the second line. Each element should be seperated by a single space.

Sample Input

``````8 4
1 2 3 4 5 6 7 8
1 2 4
2 3 5
1 4 7
2 1 4
``````

Sample Output

``````1
2 3 6 5 7 8 4 1``````

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
typedef struct _ct_node{
int size;
int priority;
int value;
struct _ct_node *left,*right;
} ct_node;
void tar(ct_node *root);
int get_size(ct_node *root);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
void computeTree();
int P[100000],T[100000],st[100000],N;
ct_node pool[100000];

int main(){
int M,x,y,z,i;
ct_node *root,*l,*m,*r,*t;
scanf("%d%d",&N,&M);
for(i = 0; i  <  N; i++){
scanf("%d",&pool[i].value);
P[i] = pool[i].priority = rand();
pool[i].left = pool[i].right = NULL;
}
computeTree();
for(i = 0; i  <  N; i++)
if(T[i] == -1)
root = & pool[i];
else
if(i<T[i])
pool[T[i]].left = & pool[i];
else
pool[T[i]].right = & pool[i];
get_size(root);
for( i = 0; i  <  M; i++){
scanf("%d%d%d",&x,&y,&z);
switch(x){
case 1:
split(y - 2,&l,&t,root);
split(z - y,&m,&r,t);
root = merge(merge(m,l),r);
break;
default:
split(y - 2,&l,&t,root);
split(z - y,&m,&r,t);
root = merge(merge(l,r),m);
}
}
N = 0;
tar(root>;
printf("%d\n",(T[0]>T[N-1])?T[0]-T[N-1]:T[N-1]-T[0]);
for(i = 0; i  <  N; i++)
printf("%d ",T[i]);
return 0;
}
void tar(ct_node *root){
if(!root)
return;
tar(root -> left);
T[N++] = root -> value;
tar(root -> right);
return;
}
int get_size(ct_node *root){
if(!root)
return 0;
root->size=get_size(root->left)+get_size(root->right)+1;
return root->size;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L -> priority > R -> priority){
L -> right = merge(L -> right,R);
recalc(L);
return L;
}
R -> left = merge(L,R -> left);
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root) ? root -> size:0;
}
void recalc(ct_node *root){
root -> size = sizeOf(root -> left) + sizeOf(root -> right) + 1;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L =*R= NULL;
return;
}
int curIndex = sizeOf(root -> left);
ct_node *t;
if(curIndex <= x>{
split(x - curIndex - 1,&t,R,root -> right);
root -> right = t;
recalc(root);
*L = root;
}
else{
split(x,L,&t,root -> left);
root -> left = t;
recalc(root);
*R = root;
}
return;
}
void computeTree(){
int i,k,top=-1;
for(i = 0; i  <  N; i++){
k=top;
while(k >= 0 && P[st[k]]  <  P[i])
k--;
if(k != -1)
T[i] = st[k];
if(k < top>
T[st[k + 1]] = i;
st[++k] = i;
top = k;
}
T[st[0]] = -1;
return;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

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

int Random() { return rand() << 15 | rand(); }

struct item {
int prior, value, cnt;
item *left, *right;
item(int val = 0): value(val), prior(Random()), cnt(0), left(nullptr), right(nullptr) {}
};

int n, m;
item *tr;

int Count(item * p) { return p? p->cnt: 0; }

void Update(item * p) { if (p) p->cnt = Count(p->left) + Count(p->right) + 1; }

void Merge(item* &p, item *l, item *r)
{
if (!l || !r) p = l? l: r;
else if (l->prior > r->prior) Merge(l->right, l->right, r), p = l;
else Merge(r->left, l, r->left), p = r;
Update(p);
}

void Split(item *p, item* &l, item* &r, int key, int add = 0)
{
if (!p) { l = r = nullptr; return; }
int curkey = add + Count(p->left);
if (key  < = curkey) Split(p->left, l, p->left, key, add), r = p;
else Split(p->right, p->right, r, key, curkey + 1), l = p;
Update(p);
}

void Print(item *tr)
{
if (tr) {
Print(tr->left);
printf("%d ", tr->value);
Print(tr->right);
}
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i  <  n; i++) {
int a; scanf("%d", &a);
Merge(tr, tr, new item(a));
}
while (m--) {
int typ, l, r; scanf("%d %d %d", &typ, &l, &r); l--, r--;
item *p1, *p2; Split(tr, tr, p2, r + 1); Split(tr, p1, tr, l);
if (typ == 1) { Merge(tr, tr, p1); Merge(tr, tr, p2); }
else { Merge(tr, p2, tr); Merge(tr, p1, tr); }
}
if (n == 1) printf("0\n");
else {
item *p1, *p2; Split(tr, tr, p2, n - 1); Split(tr, p1, tr, 1);
printf("%d\n", abs(p1->value - p2->value));
Merge(tr, p1, tr); Merge(tr, tr, p2);
}
Print(tr);
return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;

public class Solution {

public static class Treap {

public static class Node {
public int y;
public int count = 1;

Node left;
Node right;

public Node(int payload, int y) {
this.y = y;
}

public Node(int payload, int y, Node left, Node right) {
this.y = y;
this.left = left;
this.right = right;
}

public void fixCount() {
count = (left == null ? 0 : left.count) +
(right == null ? 0 : right.count) + 1;
}

public List < Integer> toList() {
List list = new ArrayList<>();
printNode(this, list);
return list;
}

private void printNode(Node node, List < Integer> list) {
if (node == null) return;
printNode(node.left, list);
printNode(node.right, list);
}
}

public static Node merge(Node left, Node right) {
if (left == null) return right;
if (right == null) return left;

if (left.y > right.y) {
left.right = merge(left.right, right);
left.fixCount();
return left;
} else {
right.left = merge(left, right.left);
right.fixCount();
return right;
}
}

public static Node[] splitByOrder(Node node, int order) {
if (order == 0) {
return new Node[]{null, node};
} else if (node.count  < = order) {
return new Node[]{node, null};
} else if (node.left != null && node.left.count >= order) {
Node[] subResult = splitByOrder(node.left, order);
node.left = subResult[1];
node.fixCount();
return new Node[]{subResult[0], node};
} else {
Node[] subResult = splitByOrder(node.right,
order - (node.left != null ? node.left.count : 0) - 1);
node.right = subResult[0];
node.fixCount();
return new Node[]{node, subResult[1]};
}
}

}

static Random random = new Random();

public static void main(String[] args) {

Treap.Node root = new Treap.Node(fastReader.nextInt(), random.nextInt());
for (int i = 1; i  <  n; i++) {
root = Treap.merge(root, new Treap.Node(fastReader.nextInt(), random.nextInt()));
}

for (int i = 0; i  <  m; i++) {

Treap.Node[] subResult1 = Treap.splitByOrder(root, from - 1);
Treap.Node first = subResult1[0];
Treap.Node temp = subResult1[1];
Treap.Node[] subResult2 = Treap.splitByOrder(temp,
to - (first != null ? first.count : 0));
Treap.Node second = subResult2[0];
Treap.Node third = subResult2[1];

Treap.Node node = Treap.merge(first, third);

if (a == 1) {
root = Treap.merge(second, node);
} else {
root = Treap.merge(node, second);
}
}
List < Integer> integers = root.toList();
System.out.println(Math.abs(integers.get(0) - integers.get(integers.size() - 1)));
System.out.println(integers.stream().map(i -> Integer.toString(i)).collect(Collectors.joining(" ")));
}

StringTokenizer st;

}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
class TreeNode {
_left = 0;
_right = 1;

constructor(value, parent = null, priority = null) {
this.value = value;
this.parent = parent;
this.children = [];
this.multiplicity = 1;
this.priority = priority || this.getRandom();
this.size = 1;
this.leftSize = 0;
this.rightSize = 0;
}

get left() {
return this.children[this._left];
}

set left(node) {
this.children[this._left] = node;

if (node) {
node.parent = this;
}
}

get right() {
return this.children[this._right];
}

set right(node) {
this.children[this._right] = node;

if (node) {
node.parent = this;
}
}

get rightSize() {
return this._rightSize;
}

set rightSize(value) {
this._rightSize = value;
}

get leftSize() {
return this._leftSize;
}

set leftSize(value) {
this._leftSize = value;
}

get size() {
return this._size;
}

set size(value) {
this._size = value;
}

getRandom() {
return Math.floor(Math.random() * Number.MAX_SAFE_INTEGER) + 1;
}

swapChild(oldChild, newChild) {
const side = this.left === oldChild ? 'left' : 'right';

this[side] = newChild;
}

removeChild(child) {
this.swapChild(child);
}

removeParent(undirected = false) {
if (undirected) {
const { parent } = this;

if (parent) {
parent.removeChild(this);
}
}

this.parent = null;
}

this.leftSize = this.left ? this.left.size : 0;
this.rightSize = this.right ? this.right.size : 0;

this.size = this.leftSize + this.rightSize + 1;
}

split(key, implicitIndex = false) {
const index = implicitIndex ? this.leftSize + 1 : this.value;

if (key >= index) {
const { right } = this;

let r;

if (right) {
right.removeParent(true);

if (implicitIndex) {
key -= index;
}

const { l: l2, r: r2 } = right.split(key, implicitIndex);

this.right = l2;
r = r2;
}

return { l: this, r };
}

const { left } = this;

let l;

if (left) {
left.removeParent(true);

const { l: l2, r: r2 } = left.split(key, implicitIndex);

l = l2;
this.left = r2;
}

return { l, r: this };
}

merge(node) {
if (!node) return this;

if (this.priority > node.priority) {
const { left } = node;

if (left) {
left.removeParent(true);

node.left = this.merge(left);
} else {
node.left = this;
}

return node;
}

const { right } = this;

if (right) {
right.removeParent(true);

this.right = right.merge(node);
} else {
this.right = node;
}

return this;
}
}

class ImplicitTreap {
_root;

constructor(root) {
this.root = root;
}

get root() {
return this._root;
}

set root(node) {
this._root = node;

if (node) {
this.length = node.size;
} else {
this.length = 0;
}
}

const newNode = new TreeNode(value, null, priority);

if (!this.root) {
this.root = newNode;
} else {
const { root, length } = this;
const { l, r } = root.split(length + 1, true);

this.root = l.merge(newNode).merge(r);
}

return newNode;
}

traverseInOrder(node = this.root) {
let tree = [];

if (node) {
if (node.left) {
tree = tree.concat(this.traverseInOrder(node.left));
}

tree.push(node.value);

if (node.right) {
tree = tree.concat(this.traverseInOrder(node.right));
}
}

return tree;
}
}

function print(arr) {
const n = arr.length;
const abs = Math.abs(arr[0] - arr[n - 1]);
const elements = arr.join(' ');

console.log(abs);
console.log(elements);
}

function processData(arr, queries) {
const t = new ImplicitTreap();
for (const item of arr) {
}

for (const query of queries) {
const [type, start, end] = query.split(' ');
const startIndex = start - 1;
const endIndex = end - 1;

const { root } = t;
const { l: p1, r: p2 } = root.split(startIndex, true);
const { l: p3, r: p4 } = p2.split(endIndex - startIndex + 1, true);
const p5 = (p1) ? p1.merge(p4) : p4;

if (type == 1) {
t.root = p3.merge(p5);
} else {
t.root = p5.merge(p3);
}
}

const result = [];
for (const item of t.traverseInOrder()) {
result.push(item);
}

return result;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
const args = _input.split('\n');
const n = args.shift().split(' ')[0];
const arr = args.shift().split(' ');
const result = processData(arr, args);

print(result);
});
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3
# Enter your code here. Read input from STDIN. Print output to STDOUT

import os
import array

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

n, m = [int(s) for s in input().split()]
a = array.array('i', [int(s) for s in input().split()])

for _ in range(m):
t, i, j = [int(s) for s in input().split()]
if t == 1:
a = a[i-1:j] + a[:i-1] + a[j:]
else:
a = a[:i-1] + a[j:] + a[i-1:j]

fptr.write(f'{abs(a[0] - a[-1])}\n')
fptr.write(' '.join([str(aa) for aa in a]))
fptr.write('\n')

fptr.close()
``````
Copy The Code &