In this HackerEarth Replace problem solution Yet another interesting problem about queries! You have an array of n integers and q queries on this array. There are two types of queries:
  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]
This problem will be very popular! So you should solve it before it became mainstream.


HackerEarth Replace problem solution


HackerEarth Replace problem solution.

#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("%d\n", ans);
}
}

return 0;
}