using merging segment tree to solve problems about sorted list

Правка en2, от TLE, 2016-12-31 16:05:58

Two months ago, I came across a problem.

Initially there are n elements, they are in n tiles.

There are 3 kinds of queries:

1. merge two tiles into one tile.
2. split one tile into two tiles. (Formally for a tile of size k, split it into two tiles of size k1 and k2, k=k1+k2, the first tile contains the smallest k1 elements and the second tile contains the rest)
3. find the k-th smallest element in one tile.

Recently I found this technique http://blog.csdn.net/zawedx/article/details/51818475 (in Chinese) which can be used to solve this problem. This blog is my own explanation :p

First, let's suppose the values in the sorted lists are integers between 1~n. If not, you may just sort and map them.

Let's build a segment tree for every sorted list, segment trees are built based on values (1~n). In every node of a segment tree stores how many numbers are in this range, let's call this the value of a node.

It seems that it requires O(nlogn) space to store every segment tree, but we can simply ignore the nodes that value=0, and really allocate these nodes only when their value become >0.

So for a sorted list with only one element, we simply build a chain of this value, so only O(logn) memory is needed.

int s[SZ]/*value of a node*/,ch[SZ]/*a node's two children*/;
//make a seg with only node p, return in the first argument
//call with sth. like build(root,1,n,value);
void build(int& x,int l,int r,int p)
{
x=/*a new node*/; s[x]=1;
if(l==r) return;
int m=(l+r)>>1;
if(p<=m) build(ch[x],l,m,p);
else build(ch[x],m+1,r,p);
}


When we split a segment tree (sorted list), simply split two children recursively:

//make a new node t2, split t1 to t1 and t2 so that s[t1]=k
void split(int t1,int& t2,int k)
{
t2=/*a new node*/;
int ls=s[ch[t1]]; //size of t1's left child
if(k>ls) split(ch[t1],ch[t2],k-ls); //split the right child of t1
else swap(ch[t1],ch[t2]); //all right child belong to t2
if(k<ls) split(ch[t1],ch[t2],k); //split the left child of t1
s[t2]=s[t1]-k; s[t1]=k;
}


When we merge two sorted lists, merge them forcely:

//merge trees t1&t2, return merged segment tree (t1 in fact)
int merge(int t1,int t2)
{
if(t1&&t2);else return t1^t2; //nothing to merge
ch[t1]=merge(ch[t1],ch[t2]);
ch[t1]=merge(ch[t1],ch[t2]);
s[t1]+=s[t2]; /*erase t2, it's useless now*/ return t1;
}


Also, just query k-th simply.

//query k-th of segment tree x[l,r]
int ask(int x,int l,int r,int k)
{
if(l==r) return l;
int ls=s[ch[x]]; //how many nodes in left child
int m=(l+r)>>1;
}


It looks very simple, isn't it? But its total complexity is in fact O(nlogn).

Proof

Happy new year~ #### История

Правки Rev. Язык Кто Когда Δ Комментарий
en2 TLE 2016-12-31 16:05:58 3310 Real initial revision :( (published)
en1 TLE 2016-12-31 15:47:14 680 Initial revision (saved to drafts)