UVA - 11922
Permutation Transformer
| Time Limit: 2000MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
[Submit] [Go Back] [Status]
Description
| Permutation Transformer |
Write a program to transform the permutation 1, 2, 3,..., n according to m instructions. Each instruction (a, b) means to take out the subsequence from the a-th to the b-th element, reverse it, then append it to the end.
Input
There is only one case for this problem. The first line contains two integers n and m ( 1
n, m
100, 000). Each of the next m lines contains an instruction consisting of two integers a and b ( 1
a
b
n).
Output
Print n lines, one for each integer, the final permutation.
Explanation of the sample below
Instruction (2,5): Take out the subsequence {2,3,4,5}, reverse it to {5,4,3,2}, append it to the remaining permutation {1,6,7,8,9,10}
Instruction (4,8): The subsequence from the 4-th to the 8-th element of {1,6,7,8,9,10,5,4,3,2} is {8,9,10,5,4}. Take it out, reverse it, and you'll get the sample output.
Warning: Don't use cin, cout for this problem, use faster i/o methods e.g scanf, printf.
Sample Input
10 2
2 5
4 8
Sample Output
1
6
7
3
2
4
5
10
9
8
Source
Root :: Prominent Problemsetters :: Rujia Liu
Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 3. Data Structures :: Binary Search Trees :: Examples
[Submit] [Go Back] [Status]
題意：
維護序列1,2,3...n。隻有一種操作：
a b 表示把[a, b]翻轉後放到序列尾部
Splay的基本操作
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
//#define WIN
#ifdef WIN
typedef __int64 LL;
#define iform "%I64d"
#define oform "%I64d\n"
#define oform1 "%I64d"
#else
typedef long long LL;
#define iform "%lld"
#define oform "%lld\n"
#define oform1 "%lld"
#endif
#define S64I(a) scanf(iform, &(a))
#define P64I(a) printf(oform, (a))
#define P64I1(a) printf(oform1, (a))
#define REP(i, n) for(int (i)=0; (i)<n; (i)++)
#define REP1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FOR(i, s, t) for(int (i)=(s); (i)<=(t); (i)++)
#define keyTree (ch[ch[root][1]][0])
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
const double PI = (4.0*atan(1.0));
const int maxn = 100000 + 20;
int ch[maxn][2], val[maxn], pre[maxn], size[maxn], S[maxn];
int root, top1, top2;
LL sumv[maxn], addv[maxn];
int rev[maxn];
// debug
void push_down(int );
void Treaval(int x) {
if(x) {
Treaval(ch[x][0]);
printf("結點%2d : 左兒子 %2d 右兒子 %2d 父結點 %2d size = %2d ,val = %2d\n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]);
Treaval(ch[x][1]);
}
}
void debug() {
printf("root=%d\n",root);
Treaval(root);
}
void New(int & r, int fa, int v) {
if(top2) r = S[--top2];
else r = ++top1;
pre[r] = fa;
size[r] = 1;
ch[r][0] = ch[r][1] = 0;
sumv[r] = val[r] = v;
addv[r] = 0;
rev[r] = 0;
}
void Reversed(int r) {
if(!r) return ;
rev[r] ^= 1;
swap(ch[r][0], ch[r][1]);
}
void push_up(int r) {
size[r] = size[ch[r][0]] + size[ch[r][1]] + 1;
sumv[r] = sumv[ch[r][0]] + sumv[ch[r][1]] + val[r];
}
void push_down(int r) {
if(addv[r]) {
int lson = ch[r][0], rson = ch[r][1];
addv[lson] += addv[r];
val[lson] += addv[r];
addv[rson] += addv[r];
val[rson] += addv[r];
sumv[lson] += addv[r] * size[lson];
sumv[rson] += addv[r] * size[rson];
addv[r] = 0;
}
if(rev[r]) {
Reversed(ch[r][0]);
Reversed(ch[r][1]);
rev[r] = 0;
}
}
void Rotate(int x, int d) {
int y = pre[x];
push_down(x);
push_down(y);
ch[y][!d] = ch[x][d];
pre[ch[x][d]] = y;
if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;
pre[x] = pre[y];
ch[x][d] = y;
pre[y] = x;
push_up(y);
}
void Splay(int x, int goal) {
push_down(x);
while(pre[x] != goal) {
if(pre[pre[x]] == goal)
Rotate(x, ch[pre[x]][0] == x);
else {
int y = pre[x];
int d = ch[pre[y]][0] == y;
if(ch[y][d] == x) {
Rotate(x, !d);
Rotate(x, d);
} else {
Rotate(y, d);
Rotate(x, d);
}
}
}
push_up(x);
if(goal == 0) root = x;
}
void RotateTo(int k, int goal) {
int r = root;
push_down(r);
while(size[ch[r][0]] != k) {
if(k < size[ch[r][0]]) r = ch[r][0];
else {
k -= size[ch[r][0]] + 1;
r = ch[r][1];
}
push_down(r);
}
Splay(r, goal);
}
int que[maxn];
void erase(int x) {
int y = pre[x];
int head = 0, tail = 0;
for(que[tail++] = x; head < tail; head++) {
int r = que[head];
S[top2++] = r;
if(ch[r][0]) que[tail++] = ch[r][0];
if(ch[r][1]) que[tail++] = ch[r][1];
}
ch[y][ch[y][1] == x] = 0;
push_up(y);
}
void build(int & r, int L, int R, int fa) {
if(L > R) return ;
int M = (L + R) / 2;
New(r, fa, M);
if(L < M) build(ch[r][0], L, M-1, r);
if(M < R) build(ch[r][1], M+1, R, r);
push_up(r);
}
void init(int n) {
root = top1 = top2 = 0;
ch[0][0] = ch[0][1] = size[0] = pre[0] = 0;
addv[0] = sumv[0] = 0;
New(root, 0, -1);
New(ch[root][1], root, -1);
size[root] = 2;
build(keyTree, 1, n, ch[root][1]);
push_up(ch[root][1]);
push_up(root);
}
int getPre(int r) {
int t = ch[r][0];
if(!t) return INF;
while(ch[t][1]) t = ch[t][1];
return val[t];
}
int getNext(int r) {
int t = ch[r][1];
if(!t) return INF;
while(ch[t][0]) t = ch[t][0];
return val[t];
}
LL query(int L, int R) {
RotateTo(L-1, 0);
RotateTo(R+1, root);
return sumv[keyTree];
}
void update(int L, int R, int v) {
RotateTo(L-1, 0);
RotateTo(R+1, root);
addv[keyTree] += v;
val[keyTree] += v;
sumv[keyTree] += (LL) v * size[keyTree];
}
void print(int x) {
if(!x) return ;
push_down(x);
print(ch[x][0]);
printf("%d\n", val[x]);
print(ch[x][1]);
}
char str[10];
int main() {
int n, m;
while(scanf("%d%d", &n, &m) != EOF) {
init(n);
while(m--) {
int a, b;
scanf("%d%d", &a, &b);
RotateTo(a-1, 0);
RotateTo(b+1, root);
Reversed(keyTree);
int t = keyTree;
keyTree = 0;
push_up(ch[root][1]);
push_up(root);
int nn = n - (b-a+1);
RotateTo(nn, 0);
RotateTo(nn+1, root);
keyTree = t;
pre[t] = ch[root][1];
push_up(ch[root][1]);
push_up(root);
}
RotateTo(0, 0);
RotateTo(n+1, root);
print(keyTree);
}
return 0;
}