merge.cpp

#include <bits/stdc++.h>
using namespace std;

#define MID ((l + r)/2)
#define LEFT ((2*no))
#define RIGHT ((2*no) + 1)
const int MAXN = 3e5 + 10;

struct node
{
	vector<int> v;

	node(){}

} tree[MAXN];

int v[MAXN];

node operator+(const node& a, const node& b)
{
	node ans;
	int sizeA = (int)a.v.size();
	int sizeB = (int)b.v.size();
	int left = 0, right = 0;

	while(sizeA + sizeB > left + right)
	{
		if(left == sizeA) ans.v.push_back(b.v[right++]);
		else if(right == sizeB) ans.v.push_back(a.v[left++]);
		else
		{
			if(a.v[left] < b.v[right]) ans.v.push_back(a.v[left++]);
			else ans.v.push_back(b.v[right++]);
		}
	}
	return ans;
}

void build(int no, int l, int r)
{
	if(l == r) tree[no].v.push_back(v[l]);
	else
	{
		build(LEFT, l, MID);
		build(RIGHT, MID + 1, r);
		tree[no] = tree[LEFT] + tree[RIGHT];
	}
}