ZAKIR

        本来想把这题放在Splay学习笔记里的，但是这题卡了我一天，而且网上解题报告很少，所以我单独拿出来写一篇报告吧。

题意：给出一个无序序列，请用翻转的方法给它排序：翻转的起点依次递增，输出每次翻转的终点。比如3 4 5 1 6 2这个序列，最小的元素在4位置，第一遍排序的时候以1为起点4为终点转后为1 5 4 3 6 2；第二遍的时候最小的在位置6，则以2为起点6为终点转成1 2 6 3 4 5；第三遍最小的在4，旋转3 4；。。。。。。

解析：

        由于涉及到区间的翻转，所以用Splay会比较方便，用Splay树记录未最终定位的元素，中序遍历Splay树即可知道当前经过翻转后的序列，每排好一个元素，就把它从树里面删除。

        每次翻转的终点都是未排序的序列的最小元素，我们可以预处理下，把每个元素在树中的位置记录下来。然后把序列按值大小排序，依次处理每个元素。

        对于一个序列中的元素，它在Splay树中序序列里面的位置加上已排好序的元素个数就是翻转的终点。而元素在树中的位置已经记录下来了，我们只要把它Splay到根结点，统计它左子树的元素个数就是中序遍历序列在该元素左边的元素个数。

        pos(i)=i左边元素个数+已排好序的元素个数+1;

        由于i已经排好了序，把它删除即可。

        为了方便提取区间和删除，添加了一个开始端点和结束端点，因为翻转会把端点翻到左子树里面导致在统计左子树元素个数的时候令我蛋疼不已。最后不得已在节点里添加了一项记录该子树除端点以外的节点个数。如果各位网友有更好的办法，欢迎留言赐教，小弟不胜感激！

最后附上代码：

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

struct IN
{
	int val,pos;
}in[100001];

bool cmp(const IN &a,const IN &b)
{
	if(a.val==b.val)
		return a.pos<b.pos;
	return a.val<b.val;
}

struct Node
{
	Node *pre,*ch[2];//前驱结点，左右孩子
	bool rev;               //标记是否被翻转
	int size,val,rsz;     //子树大小,结点的值，子树除端点以外的大小
}*root,buf[100010],*null;

Node *rec[100010];
const int INF=1<<28;
int idx,N;

Node *addNode()
{
	Node *p;
	p=&buf[idx++];
	p->rsz=p->size=1;
	p->rev=false;
	p->ch[0]=p->ch[1]=p->pre=null;
	return p;
}

inline void UpdateSize(Node *p)
{
	p->size=p->ch[0]->size+p->ch[1]->size+1;
	p->rsz=p->ch[0]->rsz+p->ch[1]->rsz;
	if(p->val!=-1)p->rsz++;
}

inline void UpdateRev(Node *p)//更新处理翻转
{
	if(p==null||!p||!p->rev)return;
	swap(p->ch[0],p->ch[1]);
	if(p->ch[0]!=null)p->ch[0]->rev=!p->ch[0]->rev;
	if(p->ch[1]!=null)p->ch[1]->rev=!p->ch[1]->rev;
	p->rev=false;
}

void Init()
{
	idx=0;
	null=addNode();
	null->size=0;null->val=-1;null->rsz=0;
	root=addNode();                                //此处添加了两个端点
	root->ch[1]=addNode();root->val=-1;root->rsz=0;
	root->ch[1]->pre=root;root->ch[1]->val=-1;root->ch[1]->rsz=0;
	UpdateSize(root);
}

void Rotate(Node *x,int c)
{
	Node *y=x->pre;
	y->ch[!c]=x->ch[c];
	if(x->ch[c]!=null)
		x->ch[c]->pre=y;
	x->pre=y->pre;
	if(y->pre!=null)
		if(y->pre->ch[0]==y)
			y->pre->ch[0]=x;
		else
			y->pre->ch[1]=x;
	x->ch[c]=y;y->pre=x;
	if(y==root)root=x;
	UpdateSize(y);
}

void Splay(Node *x,Node *f)
{
	while(x->pre!=f)
	{
		Node *y=x->pre,*z=y->pre;
		UpdateRev(z);UpdateRev(y);UpdateRev(x);;
		if(x->pre->pre==f)
			Rotate(x,x->pre->ch[0]==x);
		else
		{
			if(z->ch[0]==y)
				if(y->ch[0]==x)
					Rotate(y,1),Rotate(x,1);
				else
					Rotate(x,0),Rotate(x,1);
			else
				if(y->ch[1]==x)
					Rotate(y,0),Rotate(x,0);
				else
					Rotate(x,1),Rotate(x,0);
		}
	}
	UpdateSize(x);
}

void Select(int kth,Node *f)
{
	int tmp;
	Node *t=root;
	while(1)
	{
		UpdateRev(t);
		tmp=t->ch[0]->size;
		if(tmp+1==kth)break;
		if(kth<=tmp)
			t=t->ch[0];
		else
		{
			kth-=tmp+1;
			t=t->ch[1];
		}
	}
	Splay(t,f);
}

Node *Build(int l,int r)
{
	if(l>r)return null;
	int mid=(l+r)>>1;
	Node *p=addNode();
	rec[mid]=p;p->val=in[mid].val;
	p->ch[0]=Build(l,mid-1);
	if(p->ch[0]!=null)
		p->ch[0]->pre=p;
	p->ch[1]=Build(mid+1,r);
	if(p->ch[1]!=null)
		p->ch[1]->pre=p;
	UpdateSize(p);
	return p;
}

void Delete()
{
	Node *oroot=root;
	root=root->ch[1];
	root->pre=null;
	Select(1,null);
	root->ch[0]=oroot->ch[0];
	root->ch[0]->pre=root;
	UpdateSize(root);
}

void Gao()
{
	for(int i=1;i<=N;i++)
		in[i].pos=i;
	sort(in+1,in+N+1,cmp);
	for(int i=1;i<=N;i++)
	{
		Splay(rec[in[i].pos],null);
		if(root->ch[0]!=null)
			root->ch[0]->rev=!root->ch[0]->rev;
		printf("%d",root->ch[0]->rsz+i);
		if(i!=N)putchar(' ');
		Delete();
	}
	puts("");
}

int main()
{
	while(scanf("%d",&N),N)
	{
		Init();
		for(int i=1;i<=N;i++)
			scanf("%d",&in[i].val);

		Node *troot=Build(1,N);
		root->ch[1]->ch[0]=troot;
		troot->pre=root->ch[1];
		UpdateSize(root->ch[1]);
		UpdateSize(root);
		Splay(root->ch[1],null);
		Gao();
	}
	return 0;
}

本来想写成线段树学习笔记的，无奈太懒了，先记录下来吧，这篇文章会不断更新的。

hdu1166敌兵布阵
线段树的入门题,更新结点，查询区间和。

hdu1754 I Hate It 

入门题，更新结点，查询区间最大值

hdu 1698  Just a Hook 

更新一段区间上的颜色，求值。学习了懒操作。

poj 2777 Count Color

给区间染色，求一段区间内颜色的种数。学会了线段树的新写法以及位操作。

hdu 2795 Billboard

题意：一个公告牌长为h，宽为w。每张公告的长为1，宽为wi。贴公告时优先贴最上一行，尽量往左贴。现有一批公告，请给出每个公告所在行的行号，如果不能贴，就输出-1；

解析：把公告板逆时针转90度，这时候题目就转化成从左往右找一个点，这个点的值加上wi小于等于w。给线段树的结点加一个元素Min记录当前区间最低点的高度。这样每当要插入一个公告，我们就二分区间找一个Min+wi<=w的点。如果当前区间最低点加wi都大于w，那么该区间肯定放不进这个公告。找到结点后插入，从底往上更新区间的最低点高度。

#include <cstdio>
#include <iostream>
using namespace std;

struct SegTree
{
    int left,right;
    int Min;
}st[800000];

int h,w;

void Build(int l,int r,int idx)
{
    st[idx].left=l;
    st[idx].right=r;
    st[idx].Min=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(l,mid,idx*2);
    Build(mid+1,r,idx*2+1);
}

void Insert(int l,int r,int idx,int val)
{
    if(st[idx].left==l&&st[idx].right==r)
    {
        st[idx].Min+=val;
        return;
    }
    int mid=(st[idx].left+st[idx].right)>>1;
    if(r<=mid)
        Insert(l,r,idx*2,val);
    else if(l>mid)
        Insert(l,r,idx*2+1,val);
    else
    {
        Insert(l,mid,idx*2,val);
        Insert(mid+1,r,idx*2+1,val);
    }
    st[idx].Min=min(st[idx*2].Min,st[idx*2+1].Min);
}

int Query(int idx,int val)
{
    if(st[idx].left==st[idx].right)
    {
        if(val+st[idx].Min<=w)
            return st[idx].left;
        else
            return -1;
    }
    if(st[idx].Min+val>w)
        return -1;
    if(st[idx*2].Min+val<=w)
        return Query(idx*2,val);
    else
        return Query(idx*2+1,val);
}

int main()
{
    int N;
    while(scanf("%d%d%d",&h,&w,&N)!=EOF)
    {
        int len=min(h,N);
        Build(1,len,1);
        for(int i=1,val;i<=N;i++)
        {
            scanf("%d",&val);
            int pos=Query(1,val);
            if(pos!=-1)
            {
                printf("%d\n",pos);
                Insert(pos,pos,1,val);
            }
            else
                printf("%d\n",pos);
        }
    }
    return 0;
}

poj 3667 Hotel

题意：模拟宾馆的开房退房过程，有点类似内存的申请，当入住时，输入人数，在空的房里从尽量少的房间号开始连续选取D个房间，输出起始房间号;当退房时，输入开始位置和要退的房间数，把这些连续的房间清空。

解析：膜拜小HH的思路，线段树的结点添加三个元素，lval,rval,tot,lval表示从线段树的左端点开始最长的空余长度，rval表示从线段的右端点开始最长的空余长度，tot表示这段区间里面最长的空余长度。每当有入住申请时，优先在左子树找空余的区间，否则看左子树的rval+右子树的lval（即区间的中间一段），否则看右子树。

if(st[idx*2].tot>=w)
	return Query(w,idx*2);
else if(st[idx*2].rval+st[idx*2+1].lval>=w)
	return st[idx*2].right-st[idx*2].rval+1;
else if(st[idx*2+1].tot>=w)
	return Query(w,idx*2+1);
else
	return 0;

而插入的时候自底向上更新

int mid=(st[idx].left+st[idx].right)>>1;
if(l<=mid)
	Update(l,r,flag,idx*2);
if(r>mid)
	Update(l,r,flag,idx*2+1);
st[idx].tot=max(st[idx*2].rval+st[idx*2+1].lval,max(st[idx*2].tot,st[idx*2+1].tot));
st[idx].lval=st[idx*2].lval;
st[idx].rval=st[idx*2+1].rval;
if(st[idx*2].tot==st[idx*2].dis())
	st[idx].lval+=st[idx*2+1].lval;
if(st[idx*2+1].tot==st[idx*2+1].dis())
	st[idx].rval+=st[idx*2].rval;

poj 1436 Horizontally Visible Segments

题意：水平可视：如果两竖直线段之间可以有一条水平线穿过，且该水平线不穿过其他线段，那么这里竖直线段是水平可视的，如果有三天边两两都是水平可视的，那么称这三条边构成triangle of segments，问给定的线段能构成多少个triangle of segments。

解析：类似区间染色，把线段一层一层盖在区间上，盖的过程中如果区间已经有颜色且区间上的颜色没有跟当前插入的颜色关联（即水平可视）就把当前颜色插入到区间颜色邻接表中。首先我们按照线段的x坐标从小到大排序，然后依次插入线段，插入前先Query。最后暴力寻找两两间可见的三个线段。