首页 > ACM题库 > HDU-杭电 > HDU 3487-Play with Chain-计算几何-[解题报告]HOJ
2014
04-04

HDU 3487-Play with Chain-计算几何-[解题报告]HOJ

Play with Chain

问题描述 :

YaoYao is fond of playing his chains. He has a chain containing n diamonds on it. Diamonds are numbered from 1 to n.
At first, the diamonds on the chain is a sequence: 1, 2, 3, …, n.
He will perform two types of operations:
CUT a b c: He will first cut down the chain from the ath diamond to the bth diamond. And then insert it after the cth diamond on the remaining chain.
For example, if n=8, the chain is: 1 2 3 4 5 6 7 8; We perform “CUT 3 5 4”, Then we first cut down 3 4 5, and the remaining chain would be: 1 2 6 7 8. Then we insert “3 4 5” into the chain before 5th diamond, the chain turns out to be: 1 2 6 7 3 4 5 8.

FLIP a b: We first cut down the chain from the ath diamond to the bth diamond. Then reverse the chain and put them back to the original position.
For example, if we perform “FLIP 2 6” on the chain: 1 2 6 7 3 4 5 8. The chain will turn out to be: 1 4 3 7 6 2 5 8

He wants to know what the chain looks like after perform m operations. Could you help him?

输入:

There will be multiple test cases in a test data.
For each test case, the first line contains two numbers: n and m (1≤n, m≤3*100000), indicating the total number of diamonds on the chain and the number of operations respectively.
Then m lines follow, each line contains one operation. The command is like this:
CUT a b c // Means a CUT operation, 1 ≤ a ≤ b ≤ n, 0≤ c ≤ n-(b-a+1).
FLIP a b    // Means a FLIP operation, 1 ≤ a < b ≤ n.
The input ends up with two negative numbers, which should not be processed as a case.

输出:

There will be multiple test cases in a test data.
For each test case, the first line contains two numbers: n and m (1≤n, m≤3*100000), indicating the total number of diamonds on the chain and the number of operations respectively.
Then m lines follow, each line contains one operation. The command is like this:
CUT a b c // Means a CUT operation, 1 ≤ a ≤ b ≤ n, 0≤ c ≤ n-(b-a+1).
FLIP a b    // Means a FLIP operation, 1 ≤ a < b ≤ n.
The input ends up with two negative numbers, which should not be processed as a case.

样例输入:

8 2
CUT 3 5 4
FLIP 2 6
-1 -1

样例输出:

1 4 3 7 6 2 5 8

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents          
by—cxlove

再撸一发Splay。

包括区间切割和反转操作。

对于Splay处理区间[l,r],将l-1转至根部,将r+1转至根的右孩子,这样根的右孩子的左子树便为[l,r],相当犀利啊,Splay的操作大多基于这样的旋转操作。

对于切割,便是旋转之后,把子树先取下,然后再转到要插入的位置,将子树接上。

反转操作,加个懒惰标记,表示子树是否要交换,

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define N 300015
#define inf 1<<29
#define MOD 100000007
#define LL long long
#define Key_value ch[ch[root][1]][0]
#define _match(a,b) ((a)==(b))
using namespace std;
int n,q;
int size[N],pre[N],key[N],num[N],rev[N];
int ch[N][2],tot,root,node[N];
//debug部分copy from hh  
void Treaval(int x) {  
    if(x) {  
        Treaval(ch[x][0]);  
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);  
        Treaval(ch[x][1]);  
    }  
}  
void debug() {printf("%d\n",root);Treaval(root);}  
//以上Debug  
void NewNode(int &r,int k,int father){
	r=++tot;
	ch[r][0]=ch[r][1]=0;
	pre[r]=father;
	rev[r]=0;
	key[r]=k;
}
void Push_Up(int r){
	size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
}
void Push_Down(int r){
	if(rev[r]){
		swap(ch[r][0],ch[r][1]);
		rev[ch[r][0]]^=1;
		rev[ch[r][1]]^=1;
		rev[r]=0;		
	}
}
void Bulid(int &r,int L,int R,int father){
	if(L>R)
		return ;
	int mid=(L+R)/2;
	NewNode(r,mid,father);
	Bulid(ch[r][0],L,mid-1,r);
	Bulid(ch[r][1],mid+1,R,r);
	Push_Up(r);
}
void Init(){
	tot=root=0;
	ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=0;
	NewNode(root,-1,0);
	NewNode(ch[root][1],-1,root);
	size[root]=2;
	Bulid(Key_value,1,n,ch[root][1]);
	Push_Up(ch[root][1]);
	Push_Up(root);
}
void Rotate(int x,int kind){  
	int y=pre[x];    
	Push_Down(y);
	Push_Down(x);
	ch[y][!kind]=ch[x][kind];   
	pre[ch[x][kind]]=y;  
	if(pre[y])  
		ch[pre[y]][ch[pre[y]][1]==y]=x;  
	pre[x]=pre[y];  
	ch[x][kind]=y;  
	pre[y]=x;  
	Push_Up(y);  
}   
void Splay(int r,int goal){  
	Push_Down(r);
	while(pre[r]!=goal){  
		if(pre[pre[r]]==goal)  
			Rotate(r,ch[pre[r]][0]==r);  
		else{  
			int y=pre[r];  
			int kind=(ch[pre[y]][0]==y);  
			if(ch[y][kind]==r){  
				Rotate(r,!kind);  
				Rotate(r,kind);  
			}  
			else{  
				Rotate(y,kind);  
				Rotate(r,kind);  
			}  
		}  
	}  
	Push_Up(r);  
	if(goal==0) root=r;  
} 
int Get_Kth(int r,int k){
	Push_Down(r);
	int t=size[ch[r][0]];
	if(t==k-1)
		return r;
	if(t>=k)
		return Get_Kth(ch[r][0],k);
	else
		return Get_Kth(ch[r][1],k-t-1);
}
int Get_Min(int r){
	Push_Down(r);
	while(ch[r][0]){
		r=ch[r][0];
		Push_Down(r);
	}
	return r;
}
int Get_Max(int r){
	Push_Down(r);
	while(ch[r][1]){
		r=ch[r][1];
		Push_Down(r);
	}
	return r;
}
void Reversal(int a,int b){
	int x=Get_Kth(root,a);
	int y=Get_Kth(root,b+2);
	Splay(x,0);
	Splay(y,root);		
	rev[Key_value]^=1;
}
void Cut(int a,int b,int c){
	int x=Get_Kth(root,a);
	int y=Get_Kth(root,b+2);	
	Splay(x,0);
	Splay(y,root);
	int tmp=Key_value;
	Key_value=0;
	Push_Up(ch[root][1]);
	Push_Up(root);
	int z=Get_Kth(root,c+1);
	Splay(z,0);
	int m=Get_Min(ch[root][1]);
	Splay(m,root);
	Key_value=tmp;
	pre[Key_value]=ch[root][1];
	Push_Up(ch[root][1]);
	Push_Up(root);
}
int cnt;
void InOrder(int r){
	if(r==0)
		return;
	Push_Down(r);
	InOrder(ch[r][0]);
	if(cnt>=1&&cnt<=n){
	    if(cnt>1) printf(" ");
    	printf("%d",key[r]);
	}
	cnt++;
	InOrder(ch[r][1]);
}	
int main(){
	while(scanf("%d%d",&n,&q)!=EOF){
		if(n==-1&&q==-1)
			break;
		Init();
		while(q--){
			char str[10];
			int a,b,c;
			scanf("%s",str);		
			if(str[0]=='C'){
				scanf("%d%d%d",&a,&b,&c);
				Cut(a,b,c);
			}
			else{
				scanf("%d%d",&a,&b);
				Reversal(a,b);
			}
		}	
		cnt=0;
		InOrder(root);
		printf("\n");
	}
	return 0;
}

参考:http://blog.csdn.net/acm_cxlove/article/details/7800979


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。