2014
04-04

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

by—cxlove

#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;
}

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