HackerEarth Replace problem solution

1. ai bi xi yi – change all occurrences of xi to yi on the segment [ai,bi]
2. ai bi xi – count number of occurrences of xi on the segment [ai,bi]

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
#include <unordered_map>
using namespace std;

#ifdef LOCAL
    #define debug_flag 1
#else
    #define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
    os << "[" << p.first << ", " << p.second << "]";
    return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
    os << "[";
    bool first = true;
    for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
    {
        if (!first)
            os << ", ";
        first = false;
        os << *it;
    }
    os << "]";
    return os;
}

 template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const std::map<T1, T2>& v) 
{
    os << "[";
    bool first = true;
    for (typename std::map<T1, T2>::const_iterator it = v.begin(); it != v.end(); ++it)
    {
        if (!first)
            os << ", ";
        first = false;
        os << *it;
    }
    os << "]";
    return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
    vector<string> v;
    stringstream ss(s);
    string x;
    while (getline(ss, x, c))
        v.emplace_back(x);
    return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
        cerr << name  << " = " << a << " ";
    else
        cerr << name << " ";
    _print(++it, args...);
}

typedef long long int int64;

const int B = 3e8;

int buf_ptr;
char buf[B];

void* operator new(size_t t) {
    buf_ptr += t;
    assert(buf_ptr <= B);
    return buf + buf_ptr - t;
}

void operator delete(void*) {}

struct Node {
  int sum;
  Node *l, *r;

  Node(int x) {
    sum = x;
    l = nullptr;
    r = nullptr;
  }

  Node(Node *_l, Node *_r) {
    sum = 0;
    if (_l != nullptr) {
      sum += _l->sum;
    }
    if (_r != nullptr) {
      sum += _r->sum;
    }
    l = _l;
    r = _r;
  }
};

typedef Node* pNode;

const int LOGN = 19;
const int N = (1 << LOGN);

int n, q;
pNode empty_tree[N + 1];
pNode tree_list[N];

void create_empty_tree() {
  pNode node = new Node(0);
  empty_tree[1] = node;
  for (int i = 1; i <= LOGN; i++) {
    node = new Node(node, node);
    empty_tree[1 << i] = node;
  }
}

bool not_inter(int l, int r, int a, int b) {
  return l > b || r < a;
}

bool is_in(int l, int r, int a, int b) {
  return a <= l && r <= b;
}

pNode set_val(pNode t, int l, int r, int pos, int val) {
  if (l == r) {
    return new Node(val);
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    return new Node(set_val(t->l, l, m, pos, val), t->r);
  } else {
    return new Node(t->l, set_val(t->r, m + 1, r, pos, val));
  }
}

pNode set_val(pNode t, int pos, int val) {
  return set_val(t, 0, N - 1, pos, val);
}

int get_sum(pNode t, int l, int r, int a, int b) {
  if (not_inter(l, r, a, b)) {
    return 0;
  }
  if (is_in(l, r, a, b)) {
    return t->sum;
  }
  int m = (l + r) / 2;
  return get_sum(t->l, l, m, a, b) +
    get_sum(t->r, m + 1, r, a, b);
}

int get_sum(pNode t, int a, int b) {
  return get_sum(t, 0, N - 1, a, b);
}

pair<pNode, pNode> recolor(pNode x_tree, pNode y_tree, int l, int r, int a, int b) {
  if (not_inter(l, r, a, b) || x_tree->sum == 0) {
    return make_pair(x_tree, y_tree);
  }

  if (is_in(l, r, a, b) && y_tree->sum == 0) {
    return make_pair(empty_tree[r - l + 1], x_tree);
  }

  int m = (l + r) / 2;
  pair<pNode, pNode> pl = recolor(x_tree->l, y_tree->l, l, m, a, b);
  pair<pNode, pNode> pr = recolor(x_tree->r, y_tree->r, m + 1, r, a, b);
  return make_pair(new Node(pl.first, pr.first), new Node(pl.second, pr.second));
}

pair<pNode, pNode> recolor(pNode x_tree, pNode y_tree, int a, int b) {
  return recolor(x_tree, y_tree, 0, N - 1, a, b);
}

int main()
{
#ifdef LOCAL
    freopen ("input.txt", "r", stdin);
#endif


  create_empty_tree();

  for (int i = 0; i < N; i++) {
    tree_list[i] = empty_tree[N];
  }

  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    tree_list[x] = set_val(tree_list[x], i, 1);   
  }

  for (int it = 0; it < q; it++) {
    int type, a, b, x, y;
    scanf("%d%d%d%d", &type, &a, &b, &x);
    a--;
    b--;
    if (type == 1) {
      scanf("%d", &y);
    } else {
      y = -1;
    }
    if (type == 1) {
      if (x == y) {
        continue;
      }
      pNode x_tree = tree_list[x];
      pNode y_tree = tree_list[y];
      pair<pNode, pNode> p = recolor(x_tree, y_tree, a, b);
      tree_list[x] = p.first;
      tree_list[y] = p.second;
    } else {
      int ans = get_sum(tree_list[x], a, b);
      printf("%dn", ans);
    }
  }

    return 0;
}