Splay树（区间第k小）——POJ 2761 Feed the dogs

对应POJ题目：点击打开链接

Description

Input

Output

Sample Input

7 2
1 5 2 6 3 7 4
1 5 3
2 7 1

Sample Output

3
2

 题意：

给n个数和m个区间查询（每个查询区间之间可能有交集，但不会覆盖），每个查询输出序列的第k小的数。

思路：

据说可用各种树过~

伸展树，首先保存下所有查询，对查询的左边界按升序排序，然后对排序后的每个查询区间建立一颗独立的树，至于第k小，就可以直接计算出来；在为下一个查询区间建树时，如果跟前一次查询区间没有交集，就把整棵树删掉重新建；如果有交集，就可以把跟前一次查询区间没有交集的结点删掉，有交集的留下，再把当前查询区间没有交集的加上。

#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <iostream>
#define MAX(x, y) ((x)>(y)?(x):(y))
const int MAXN = 100100;
using namespace std;
typedef int Type;
Type a[MAXN], b[MAXN>>1];

struct Q
{
	int x, y, z, id;
	Q()
	{
		id = x = y = z = 0;
	}
};

Q q[MAXN>>1];

bool cmp(Q q1, Q q2)
{
	if(q1.x != q2.x) return q1.x < q2.x;
	else return q1.y < q2.y;
}

typedef struct TREE
{
	Type val;
    TREE *fa, *l, *r;
    int sz; //以该结点为根的树的总结点数
}Tree;

Tree *mark[MAXN]; //保存结点位置

struct SplayTree
{
	public:
	SplayTree()
	{
		rt = NULL;
		inf = 1000000000;
	}

	void Push_up(Tree *T)
	{
		T->sz = (T->l ? T->l->sz : 0) + (T->r ? T->r->sz : 0) + 1;
	}

	void NewNode(Tree *pre, Tree *&T, Type v)
	{
		T = (Tree *)malloc(sizeof(Tree));
		T->val = v;
		T->sz = 1;
		T->fa = pre;
		T->l = T->r = NULL;
	}

	void Init()
	{
		NewNode(NULL, rt, -inf);
		NewNode(rt, rt->r, inf);
		rt->sz = 2;
	}

	void R_rotate(Tree *x)
	{
		Tree *y = x->fa;
		Tree *z = y->fa;
		Tree *k = x->r;
		y->l = k;
		x->r = y;
		if(z){
			if(y == z->l) z->l = x;
			else z->r = x;
		}
		if(k) k->fa = y;
		y->fa = x;
		x->fa = z;
		Push_up(y);
	}

	void L_rotate(Tree *x)
	{
		Tree *y = x->fa;
		Tree *z = y->fa;
		Tree *k = x->l;
		y->r = k;
		x->l = y;
		if(z){
			if(y == z->r) z->r = x;
			else z->l = x;
		}
		if(k) k->fa = y;
		y->fa = x;
		x->fa = z;
		Push_up(y);
	}
	
	//寻找第x个数的结点
	Tree *FindTag(int x)
	{
		if(NULL == rt) return NULL;
		Tree *p;
		p = rt;
		Type sum = (p->l ? p->l->sz : 0) + 1;
		while(sum != x)
		{
			if(sum < x){
				p = p->r;
				x -= sum;
			}
			else p = p->l;
			if(NULL == p) break;
			sum = (p->l ? p->l->sz : 0) + 1;
		}
		return p;
	}

	void Splay(Tree *X, Tree *&T)
	{
		Tree *p, *end;
		end = T->fa;
		while(X->fa != end)
		{
			p = X->fa;
			if(end == p->fa){ //p是根结点
				if(X == p->l) R_rotate(X);
				else L_rotate(X);
				break;
			}
			//p不是根结点
			if(X == p->l){
				if(p == p->fa->l){
					R_rotate(p); //LL
					R_rotate(X); //LL
				}
				else{
					R_rotate(X); //RL
					L_rotate(X);
				}
			}
			else{
				if(p == p->fa->r){ //RR
					L_rotate(p);
					L_rotate(X);
				}
				else{ //LR
					L_rotate(X);
					R_rotate(X);
				}
			}
		}
		T = X;
		Push_up(T);
	}
		
	void Insert(Type *A, int x, int y)
	{
		int i;
		//考验指针技巧的代码
		Tree **link, *p;
		for(i = x; i <= y; i++){
			link = &rt;
			while(*link)
			{
				p = *link;
				if(A[i] < p->val) link = &p->l; 
				else link = &p->r;
			}
			NewNode(p, *link, A[i]);
			mark[i] = *link;
			Splay(*link, rt);
		}
	}

	void Delete(Type *A, int x, int y)
	{
		int i;
		Tree *t;
		for(i = x; i <= y; i++){
			t = mark[i];
			Splay(t, rt);
			t = rt->l;
			while(t->r) t = t->r;
			Splay(t, rt->l);
			t = rt;
			rt = rt->l;
			rt->r = t->r;
			free(t);
			rt->r->fa = rt;
			rt->fa = NULL;
			Push_up(rt); //切记更新sz
		}
	}

	void Query(int id, int x)
	{
		x++; //自增1，因为有个-oo结点
		Tree *p;
		p = rt;
		int sum = (p->l ? p->l->sz : 0) + 1;
		while(sum != x)
		{
			if(sum < x){
				p = p->r;
				x -= sum;
			}
			else p = p->l;
			if(NULL == p) break;
			sum = (p->l ? p->l->sz : 0) + 1;
		}
		b[id] = p->val;
	}

	void Show()
	{
		InOrder(rt);
		printf("\n");
	}

	void InOrder(Tree *T)
	{
		if(NULL == T) return;
		InOrder(T->l);
		printf("%d ", T->val);
		InOrder(T->r);
	}

	void Free()
	{
		FreeTree(rt);
	}

	void FreeTree(Tree *T)
	{
		if(NULL == T) return;
		FreeTree(T->l);
		FreeTree(T->r);
		free(T);
	}

	private:
	Type inf;
	Tree *rt;
};

SplayTree spl;

int main()
{
	//freopen("in.txt","r",stdin);
	int n, m, i;
	while(scanf("%d%d", &n, &m) == 2)
	{
		for(i = 1; i <= n; i++)
			scanf("%d", a + i);
		for(i = 1; i <= m; i++){
			scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z);
			q[i].id = i; //把位置记下方便输出
		}
		sort(q + 1, q + m + 1, cmp);
		for(i = 1; i <= m; i++){
			if(q[i].x <= q[i-1].y){ //有交集
				spl.Delete(a, q[i-1].x, q[i].x - 1);
				spl.Insert(a, q[i-1].y + 1, q[i].y);
			}
			else{
				spl.Free(); //把整棵树删掉
				spl.Init();
				spl.Insert(a, q[i].x, q[i].y);
			}
			spl.Query(q[i].id, q[i].z);
		}
		spl.Free();
		for(i = 1; i <= m; i++)
			printf("%d\n", b[i]);
	}
	return 0;
}

Splay树（区间第k小）——POJ 2761 Feed the dogs

原文：http://blog.csdn.net/u013351484/article/details/46984715