In this HackerRank Swaps and Sum problem solution, you are given a sequence and we need to swap the first two elements of segment and second two-element and soon. also we have given two integers we need to find the sum between the range.

HackerRank Swaps and Sum problem solution


Problem solution in Java Programming.

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

public class HR_swaps_and_sum {

    static int size(Node x) {
        return x == null ? 0 : x.size;
    }

    static long sum(Node x) {
        return x == null ? 0 : x.sum;
    }

    static class Node {
        final static Random rnd = new Random(42);

        Node l, r;
        int depth;
        int size;
        long val, sum;

        Node(long val) {
            depth = rnd.nextInt();
            this.val = val;
            rehash();
        }

        void rehash() {
            size = 1;
            sum = val;
            if (l != null) {
                size += l.size;
                sum += l.sum;
            }
            if (r != null) {
                size += r.size;
                sum += r.sum;
            }
        }
    }

    static Node[] split(Node x, int left) {
        if (x == null) {
            return new Node[2];
        }
        Node[] p;
        if (left <= size(x.l)) {
            p = split(x.l, left);
            x.l = p[1];
            p[1] = x;
        } else {
            p = split(x.r, left - size(x.l) - 1);
            x.r = p[0];
            p[0] = x;
        }
        x.rehash();
        return p;
    }

    static Node[] splitAt(Node x, int... at) {
        Node[] ret = new Node[at.length + 1];
        for (int i = at.length - 1; i >= 0; --i) {
            Node[] tmp = split(x, at[i]);
            ret[i + 1] = tmp[1];
            x = tmp[0];
        }
        ret[0] = x;
        return ret;
    }

    static Node merge(Node l, Node r) {
        if (l == null) {
            return r;
        }
        if (r == null) {
            return l;
        }
        if (l.depth > r.depth) {
            r.l = merge(l, r.l);
            r.rehash();
            return r;
        } else {
            l.r = merge(l.r, r);
            l.rehash();
            return l;
        }
    }

    static Node mergeAll(Node... nodes) {
        Node ret = null;
        for (Node node : nodes) {
            ret = merge(ret, node);
        }
        return ret;
    }

    public static void solve(Input in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        int q = in.nextInt();
        Node even = null, odd = null;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                even = merge(even, new Node(in.nextLong()));
            } else {
                odd = merge(odd, new Node(in.nextLong()));
            }
        }
        for (int it = 0; it < q; ++it) {
            int type = in.nextInt();
            int l = in.nextInt() - 1;
            int r = in.nextInt();
            Node[] splitEven = splitAt(even, (l + 1) / 2, (r + 1) / 2);
            Node[] splitOdd = splitAt(odd, l / 2, r / 2);
            if (type == 1) {
                if (splitEven[1].size != (r - l) / 2 || splitOdd[1].size != (r - l) / 2) {
                    throw new AssertionError();
                }
                even = mergeAll(splitEven[0], splitOdd[1], splitEven[2]);
                odd = mergeAll(splitOdd[0], splitEven[1], splitOdd[2]);
            } else {
                out.println(sum(splitEven[1]) + sum(splitOdd[1]));
                even = mergeAll(splitEven);
                odd = mergeAll(splitOdd);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

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

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

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


Problem solution in C++ programming.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <map>
#include <set>
#include <vector>
#include <complex>
#include <queue>
#include <tuple>
 
using namespace std;
typedef long long ll;

struct Tree {
    using D = ll;
    struct Node;
    using NP = Node*;
    static Node last_d;
    static NP last;
    struct Node {
        NP p, l, r;
        int sz;
        D v, sm;
        Node(D v) :p(nullptr), l(last), r(last), sz(1), v(v), sm(v) {}
        Node() : l(nullptr), r(nullptr), sz(0), v(0), sm(0) {}
        inline int pos() {
            if (p) {
                if (p->l == this) return -1;
                if (p->r == this) return 1;
            }
            return 0;
        }
        void rot() {
            NP qq = p->p;
            int pps = p->pos();
            if (p->l == this) {
                p->l = r; r->p = p;
                r = p; p->p = this;
            } else {
                p->r = l; l->p = p;
                l = p; p->p = this;
            }
            p->update(); update();
            p = qq;
            if (!pps) return;
            if (pps == -1) {
                qq->l = this;
            } else {
                qq->r = this;
            }
            qq->update();
        }
        void splay() {
            assert(this != last);
            supush();
            int ps;
            while ((ps = pos())) {
                int pps = p->pos();
                if (!pps) {
                    rot();
                } else if (ps == pps) {
                    p->rot(); rot();
                } else {
                    rot(); rot();
                }
            }
        }
        NP splay(int k) {
            assert(this != last);
            assert(0 <= k && k < sz);
            if (k < l->sz) {
                return l->splay(k);
            } else if (k == l->sz) {
                splay();
                return this;
            } else {
                return r->splay(k-(l->sz+1));
            }
        }
        void supush() {
            if (pos()) {
                p->supush();
            }
            push();
        }
        //pushpush""
        void push() { 
            assert(sz);
        }
        NP update() {
            assert(this != last);
            sz = 1+l->sz+r->sz;
            sm = v;
            if (l->sz) {
                sm += l->sm;
            }
            if (r->sz) {
                sm += r->sm;
            }
            return this;
        }
    } *n;
    static NP merge(NP l, NP r) {
        if (r == last) {
            return l;
        }
        r = r->splay(0);
        assert(r->l == last);
        r->l = l;
        l->p = r;
        return r->update();
    }
    static pair<NP, NP> split(NP x, int k) {
        assert(0 <= k && k <= x->sz);
        if (k == x->sz) {
            return {x, last};
        }
        x = x->splay(k);
        NP l = x->l;
        l->p = nullptr;
        x->l = last;
        return {l, x->update()};
    }
    static NP built(int sz, ll d[]) {
        if (!sz) return last;
        int md = sz/2;
        NP x = new Node(d[md]);
        x->l = built(md, d);
        x->l->p = x;
        x->r = built(sz-(md+1), d+(md+1));
        x->r->p = x;
        return x->update();
    }
    Tree() : n(last) {}
    Tree(NP n) : n(n) {}
    Tree(int sz, D d[]) {
        n = built(sz, d);
    }
    int sz() {
        return n->sz;
    }
    void insert(int k, D v) {
        auto u = split(n, k);
        n = merge(merge(u.first, new Node(v)), u.second);
    }
    void erase(int k) {
        auto u = split(n, k);
        n = merge(u.first, split(u.second, 1).second);
    }
    void merge(Tree t) {
        n = merge(n, t.n);
    }
    Tree split(int l) {
        auto a = split(n, l);
        n = a.first;
        return Tree(a.second);
    }
    D get(int l) {
        auto a = split(n, l);
        auto b = split(a.second, 1);
        D res = b.first->v;
        n = merge(merge(a.first, b.first), b.second);
        return res;
    }
    D sum(int l, int r) {
        auto b = split(n, r);
        auto a = split(b.first, l);
        D res = a.second->sm;
        n = merge(merge(a.first, a.second), b.second);
        return res;
    }
};
Tree::Node Tree::last_d = Tree::Node();
Tree::NP Tree::last = &last_d;

const int MN = 100100;
ll a[2][MN];
Tree tr[2];
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i%2][i/2]);
    }
    tr[0] = Tree((n+1)/2, a[0]);
    tr[1] = Tree(n/2, a[1]);
    for (int qc = 0; qc < q; qc++) {
        int t; ll l, r;
        scanf("%d %lld %lld", &t, &l, &r); l--;
        if (t == 1) {
            Tree x[2], y[2];
            x[1] = tr[0].split((r+1)/2);
            x[0] = tr[0].split((l+1)/2);
            y[1] = tr[1].split(r/2);
            y[0] = tr[1].split(l/2);
            tr[0].merge(y[0]);
            tr[0].merge(x[1]);
            tr[1].merge(x[0]);
            tr[1].merge(y[1]);
        } else {
            printf("%lld\n", tr[0].sum((l+1)/2, (r+1)/2) + tr[1].sum(l/2, r/2));
        }
    }
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
typedef struct _ct_node{
  int size;
  int priority;
  int value;
  long long sum;
  struct _ct_node *left,*right;
} ct_node;
long long get_sum(int x,int y,ct_node *root);
void get_size(ct_node *root);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
long long sumOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
void reverse(int x,int y);
void computeTree(int x);
int N,P[200000],T[200000],st[200000];
ct_node poll[200000],*odd,*even;

int main(){
  int Q,x,y,i;
  scanf("%d%d",&N,&Q);
  for(i=0;i<N;i++){
    scanf("%d",&poll[i].value);
    poll[i].priority=P[i]=rand();
    poll[i].size=-1;
    poll[i].left=poll[i].right=NULL;
  }
  computeTree(0);
  computeTree(1);
  for(i=0;i<N;i++)
    if(T[i]==-1)
      if(i%2)
        odd=&poll[i];
      else
        even=&poll[i];
    else
      if(i<T[i])
        poll[T[i]].left=&poll[i];
      else
        poll[T[i]].right=&poll[i];
  get_size(odd);
  get_size(even);
  while(Q--){
    scanf("%d",&x);
    switch(x){
      case 1:
        scanf("%d%d",&x,&y);
        reverse(x,y);
        break;
      default:
        scanf("%d%d",&x,&y);
        if(x==y)
          if(x%2)
            printf("%lld\n",get_sum((x-1)/2,(x-1)/2,even));
          else
            printf("%lld\n",get_sum((x-1)/2,(x-1)/2,odd));
        else
          printf("%lld\n",get_sum((x-1)/2,(y-2)/2,odd)+get_sum(x/2,(y-1)/2,even));
    }
  }
  return 0;
}
long long get_sum(int x,int y,ct_node *root){
  if(!root || x>y || x>root->size-1 || y<0)
    return 0;
  if(x<=0 && y>=root->size-1)
    return root->sum;
  int curidx=sizeOf(root->left),t;
  long long ls,rs,ans=0;
  if(curidx>=x && curidx<=y)
    ans=root->value;
  if(y<curidx)
    ls=get_sum(x,y,root->left);
  else
    ls=get_sum(x,curidx-1,root->left);
  if(x>curidx)
    rs=get_sum(x-curidx-1,y-curidx-1,root->right);
  else
    rs=get_sum(0,y-curidx-1,root->right);
  return ans+ls+rs;
}
void get_size(ct_node *root){
  if(!root)
    return;
  int ls=0,rs=0;
  long long lsu=0,rsu=0;
  if(root->left){
    if(root->left->size==-1)
      get_size(root->left);
    ls=root->left->size;
    lsu=root->left->sum;
  }
  if(root->right){
    if(root->right->size==-1)
      get_size(root->right);
    rs=root->right->size;
    rsu=root->right->sum;
  }
  root->size=ls+rs+1;
  root->sum=lsu+rsu+root->value;
  return;
}
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;
}
long long sumOf(ct_node *root){
  return (root)?root->sum:0;
}
void recalc(ct_node *root){
  root->size=sizeOf(root->left)+sizeOf(root->right)+1;
  root->sum=sumOf(root->left)+sumOf(root->right)+root->value;
  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 reverse(int x,int y){
  ct_node *ol,*om,*or,*el,*em,*er;
  int A,B;
  A=(x-1)/2;
  B=(y-2)/2;
  split(A-1,&ol,&or,odd);
  split(B-A,&om,&or,or);
  A=x/2;
  B=(y-1)/2;
  split(A-1,&el,&er,even);
  split(B-A,&em,&er,er);
  odd=merge(merge(ol,em),or);
  even=merge(merge(el,om),er);
  return;
}
void computeTree(int x){
  int i,k,top=-1;
  for(i=x;i<N;i+=2){
    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;
}