HDU 1890

本文主要是介绍HDU 1890，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

每次写树的时候都脑壳疼。
对大佬们这就是一道水题，可是对自己着实有点不好解决。憋了两天照着模板分析分析不出来，splay tree思想很精彩，实现很精妙，再加上这道题还有延迟标记，虽然过程有点难顶，但最后收获颇丰

这道题要注意几个细节:

• splay tree时时记住maintain(本模板就是pushup)
• 因为这道题使用了延迟标记，所以一定要明晰什么时候pushdown，基本上，除了建树和逆转无关以外，其他的部分都涉及到了pushdown的部分，因为，任何的旋转修改树的结构，或是查询的时候都涉及到了当前树节点对顺序（保守方法就是见到就Pushdown，一般这里的时间复杂度差异也不会特别大，机器那一点时间在这种短时间评测换来编码时间并减少出错率是值得的，但是自己练习的时候还是训练自己弄清楚为好）

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;

const int maxn= 1e5+5;

struct Node;
Node *null;

struct Node
{
	Node *ch[2], *fa;
	int size, rev;
	void clear()
	{
		if (this== null){
			return;
		}
		ch[0]= ch[1]= fa= null;
		size= 1;
		rev= 0;
	}
	void pushUp()
	{
		if (this== null){
			return;
		}
		size= ch[0]->size+ch[1]->size+1;
	}
	void setc(Node *p, int d)
	{
		if (this== null){
			return;
		}
		ch[d]= p;
		p->fa= this;
	}
	int d()
	{
		return fa->ch[1]== this;
	}
	void updateRev()
	{
		if (this== null){
			return;
		}
		swap(ch[0], ch[1]);
		rev^= 1;
	}
	void pushDown()
	{
		if (this== null){
			return;
		}
		if (rev){
			ch[0]->updateRev();
			ch[1]->updateRev();
			rev= 0;
		}
	}
};
Node pool[maxn], *tail, *root;
Node *node[maxn];
int a[maxn], b[maxn];

void Rotate(Node *x)
{
	if (x->fa== null){
		return;
	}
	Node *f= x->fa, *ff= x->fa->fa;
	f->pushDown();
	x->pushDown();
	int c= x->d(), cc= f->d();
	f->setc(x->ch[!c], c);
	x->setc(f, !c);
	if (ff->ch[cc]== f){
		ff->setc(x, cc);
	}
	else{
		x->fa= ff;
	}	
	f->pushUp();
}
void Splay(Node *&root, Node *x, Node *goal)
{
	while (x->fa!= goal){
		if (x->fa->fa== goal){
			Rotate(x);
		}
		else{
			x->fa->fa->pushDown();
			x->fa->pushDown();
			x->pushDown();
			int c= x->d(), cc= x->fa->d();
			c== cc ? Rotate(x->fa) : Rotate(x);
			Rotate(x);
		}
	}
	x->pushUp();
	if (null== goal){
		root= x;
	}
}
Node *get_kth(Node *r, int k)
{
	Node *x= r;
	x->pushDown();
	while (k!= x->ch[0]->size+1){
		if (k<= x->ch[0]->size){
			x= x->ch[0];
		}
		else{
			k-= x->ch[0]->size+1;
			x= x->ch[1];
		}
		x->pushDown();
	}

	return x;
}
void Build(Node *&x, int l, int r, Node *fa)
{
	if (l> r){
		return;
	}
	int mid= (l+r)>>1;
	x= tail++;
	x->clear();
	x->fa= fa;
	node[mid]= x;
	Build(x->ch[0], l, mid-1, x);
	Build(x->ch[1], mid+1, r, x);
	x->pushUp();
}
void Init(int n)
{
	tail= pool;
	null= tail++;
	null->ch[0]= null->ch[1]= null->fa= null;
	null->size= null->rev= 0;
	Node *p= tail++;
	p->clear();
	root= p;
	p= tail++;
	p->clear();
	root->setc(p, 1);
	Build(p->ch[0], 1, n, p);
	p->pushUp();
	root->pushUp();
}
bool cmp(int i, int j)
{
	if (a[i]!= a[j]){
		return a[i]< a[j];
	}
	return i< j;
}

int main(int argc, char const *argv[])
{
	int n;
	while (1== scanf("%d", &n) && n){
		for (int i= 1; i<= n; ++i){
			scanf("%d", a+i);
			b[i]= i;
		}
		Init(n);
		sort(b+1, b+1+n, cmp);

		for (int i= 1; i<= n; ++i){
			Splay(root, node[b[i]], null);
			int sz= root->ch[0]->size;
			printf("%d", sz);
			if (i== n){
				putchar('\n');
			}
			else{
				putchar(' ');
			}
			Splay(root, get_kth(root, i), null);
			Splay(root, get_kth(root, sz+2), root);
			root->ch[1]->ch[0]->updateRev();
		}
	}
	return 0;
}

这篇关于HDU 1890的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！