In this tutorial, we are going to solve or make a solution to Array and simple queries problems. so here we have given the number of elements in the array and the number of queries. and we need to perform queries on the array.
Problem solution in 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()
Problem solution in Java Programming.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public static class Treap {
public static class Node {
public int payload;
public int y;
public int count = 1;
Node left;
Node right;
public Node(int payload, int y) {
this.payload = payload;
this.y = y;
}
public Node(int payload, int y, Node left, Node right) {
this.payload = payload;
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<Integer> list = new ArrayList<>();
printNode(this, list);
return list;
}
private void printNode(Node node, List<Integer> list) {
if (node == null) return;
printNode(node.left, list);
list.add(node.payload);
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) {
FastReader fastReader = new FastReader();
int n = fastReader.nextInt();
int m = fastReader.nextInt();
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++) {
int a = fastReader.nextInt();
int from = fastReader.nextInt();
int to = fastReader.nextInt();
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(" ")));
}
public static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} 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 {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
Problem solution in 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("0n");
else {
item *p1, *p2; Split(tr, tr, p2, n - 1); Split(tr, p1, tr, 1);
printf("%dn", abs(p1->value - p2->value));
Merge(tr, p1, tr); Merge(tr, tr, p2);
}
Print(tr);
return 0;
}
Problem solution in 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("%dn",(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;
}
Problem solution in 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;
}
updateSize() {
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;
}
this.updateSize();
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;
}
this.updateSize();
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;
}
node.updateSize();
return node;
}
const { right } = this;
if (right) {
right.removeParent(true);
this.right = right.merge(node);
} else {
this.right = node;
}
this.updateSize();
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;
}
}
add(value, priority = null) {
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) {
t.add(item);
}
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);
});
