小練習，splay區間反轉

一道codevs的區間翻轉問題。

http://codevs.cn/problem/1743/

題意，每次找最左邊的數，令為k:   k=1,結束;  否則,ans++,翻轉[1,k].

(給定的是全排列，是以，加兩個點就可以直接做了。)

題目中說可能無解，但我覺得應該有解，是以就沒管-1.   求大神指導一下到底是否一定有解。

（當然最好定義一個較大的操作數，大于此操作數仍無法結束程式，輸出-1）

以下簡要分析：

①兩個虛拟點是極有用的，有了這兩個虛拟點就避免讨論l=1時l-1找不到的情況。

②（我用的指針）插入的時候，一直向最右邊插就可以了（記得每次把插入的點旋到根）~~~PS：我傻逼了，splay如果旋完我直接return 了，忘記如果旋到根要變root的指向。

③指針的操作就是不容易直接記錄每個點的位置（好像可以直接找）(管它的，我寫複雜了~) 是以我還用了size存左子數個數，每次找排名第2的（有虛拟節點），把它的值找到，是1結束，否則翻轉。

其實我這樣看似多餘，實則是有必要的----  你每次直接調用位址進行操作，它上面可能有lazy标記沒有變化，那麼你操作完就有可能偏離了正常的答案，是以就需要從上往下依次找，每層下放lazy.

④pushdown是在每次往下查詢的時候都要用到的，隻要需要從根往下找，每層pushdown以下，操作類似于線段樹。

之後就是正常的splay就可以了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 300000+20
using namespace std;
int n;
int cnt=0;
struct node
{
	node *f;
	node *ch[2];
	int key;
	int lazy;
	int size;
}S[maxn];
node *root;
void pushup(node *u)
{
	u->size=1;
	if(u->ch[0])u->size+=u->ch[0]->size;
	if(u->ch[1])u->size+=u->ch[1]->size;
}
void pushdown(node *u)
{
	if(u==NULL||!u->lazy)return ;
	if(u->ch[0])u->ch[0]->lazy^=1;
	if(u->ch[1])u->ch[1]->lazy^=1;
	node *y;
	y=u->ch[0];
	u->ch[0]=u->ch[1];
	u->ch[1]=y;
	u->lazy=0;
}
void rotate(node *u)
{
	node *f=u->f;
	if(f==NULL)return ;
	pushdown(u);
	pushdown(f);
	node *ff=f->f;
	int d=u==f->ch[1];
	int dd=0;
	if(ff!=NULL)dd=f==ff->ch[1];
	
	if(u->ch[d^1])u->ch[d^1]->f=f;
	f->ch[d]=u->ch[d^1];
	
	f->f=u;
	u->ch[d^1]=f;
	
	if(ff!=NULL)ff->ch[dd]=u;
	u->f=ff;
	pushup(f);
	pushup(u);
}
void splay(node *u,node *p)
{
	pushdown(u);
	while(u->f!=p)
	{
		node *f=u->f;
		node *ff=f->f;
		if(ff==p)
		{
			rotate(u);
			break;
		}
		int d=u==f->ch[1];
		int dd=f==ff->ch[1];
		if(d==dd)rotate(f);
		else rotate(u);
		rotate(u);
	}
	if(p==NULL)root=u;
	pushup(u);
}

void insert(int key)
{
	if(root==NULL)
	{
		root=&S[++cnt];
		root->lazy=0;
		root->key=key;
		root->size=1;
		root->ch[0]=root->ch[1]=root->f=NULL;
		return ;
	}
	node *u=root;
	node *y;
	while(1)
	{
		u->size++;
		/*if(key<u->key)
		{
			if(u->ch[0])u=u->ch[0];
			else
			{
				y=&S[++cnt];
				y->lazy=0;
				y->ch[0]=y->ch[1]=NULL;
				y->size=1;
				y->key=key;
				y->f=u;
				u->ch[0]=y;
				break;
			}
		}
		else
		{*/
			if(u->ch[1])u=u->ch[1];
			else
			{
				y=&S[++cnt];
				y->lazy=0;
				y->ch[0]=y->ch[1]=NULL;
				y->key=key;
				y->size=1;
				y->f=u;
				u->ch[1]=y;
				break;
			}
		
	}
	splay(y,NULL);
}
node * find(int k)
{
	node *u=root;
	while(1)
	{
		pushdown(u);
		int size=1;
		if(u->ch[0])size+=u->ch[0]->size;
		if(size==k)return u;
		if(k<size)u=u->ch[0];
		else 
		{
			k-=size;
			u=u->ch[1];
		}
	}
}
int find2()
{
	return find(2)->key;
}
void flip(int l,int r)
{
	//l,r+2
	node *ll=find(l);
	node *rr=find(r+2);
	splay(ll,NULL);
	splay(rr,root);
	root->ch[1]->ch[0]->lazy^=1;
}
void dfs(node *u)
{
	if(u->ch[0])dfs(u->ch[0]);
	printf("%d ",u->key);
	if(u->ch[1])dfs(u->ch[1]);
}
int main()
{
	scanf("%d",&n);
	root=NULL;
	int x;
	insert(0);
	for(int i=1;i<=n;i++)
	{		
		scanf("%d",&x);
		insert(x);
	}	
	insert(n+1);
	int ans=0;
	while(1)
	{
		int k=find2();
		if(k==1)break;
		ans++;
		flip(1,k);
	}
	printf("%d\n",ans);
	return 0;
}