[UVA][塊狀鏈表] 11922 - Permutation Transformer
Permutation Transformer
| 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, m100, 000). Each of the next m
lines contains an instruction consisting of two integers a and b (
1abn).
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
同理做法如
[ZJ][塊狀鏈表] a063. SGU 187. Twist and whirl - want to cheat
雖然說是塊狀鏈表，但說實在也很難一定是塊狀鏈表的限制。
網路上很多規定要維護在 sqrt(n) 與 2*sqrt(n) 之間，
但有一個疑惑，萬一插入形成 2sqrt(n), 1, 2sqrt(n), 1, 2sqrt(n), 1 ....
不懂這要怎麼維護，總之能合併就合併。
這題給定塊一個反轉的懶操作，需要的時候才將其反轉。
當要翻轉 [l, r] 時，必須將塊分裂成 [l...ai][ai+1...aj+1]...[ak+1...r]
即操作是要將 l 跟 r 從原本的塊裂分出來，
然後將這些塊標記反轉操作，並且反轉這些塊的位置。
但是這題反轉完要串接在字串尾端。
分成四個反轉可能[{ZZZ}], [{ZZZ}XXX], [XXX{ZZZ}], [XXX{ZZZ}XXX]
{ZZZ}區是反轉的指定區間，由於要修改 head 指針，稍微分開寫了。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Node {
int v[800], vn;
int inv_label;
Node *next;
Node() {
vn = 0;
inv_label = 0;
next = NULL;
}
};
int p_size;
void printList(Node *head) {
Node *idx = head;
int i, j = 0;
while(idx != NULL) {
printf("%d : ", ++j);
for(i = 0; i < idx->vn; i++)
printf("%d ", idx->v[i]);
puts("");
idx = idx->next;
}
puts("====");
}
void freeList(Node *head) {
Node *idx = head, *pre = NULL;
while(idx != NULL) {
pre = idx, idx = idx->next;
delete pre;
}
}
void printAns(Node *head) {
Node *idx = head;
int i, j = 0;
while(idx != NULL) {
if(idx->inv_label == 0)
for(i = 0; i < idx->vn; i++)
printf("%d\n", idx->v[i]);
else
for(i = idx->vn-1; i >= 0; i--)
printf("%d\n", idx->v[i]);
idx = idx->next;
}
freeList(head);
}
void invNode(Node *node) {
static int i, j;
for(i = 0, j = node->vn-1; i < j; i++, j--)
swap(node->v[i], node->v[j]);
node->inv_label = 0;
}
void maintainList(Node *head) {
Node *idx, *p;
int i, j;
idx = head;
while(idx != NULL && idx->next != NULL) {
if(idx->vn + idx->next->vn <= 2*p_size) { // merge
p = idx->next;
if(idx->inv_label)
invNode(idx);
if(p->inv_label)
invNode(p);
for(i = idx->vn, j = 0; j < p->vn; i++, j++)
idx->v[i] = p->v[j];
idx->vn += p->vn;
idx->next = p->next;
delete p;
}
idx = idx->next;
}
}
Node* split(Node *node, int v) { // length(left) = v
static int i, j;
if(node->inv_label)
invNode(node);
Node *tmp = new Node();
tmp->next = node->next;
node->next = tmp;
tmp->vn = node->vn - v;
for(i = v, j = 0; i < node->vn; i++, j++)
tmp->v[j] = node->v[i];
node->vn = v;
}
Node *stk[10000];
Node* inverseArray(Node *head, int l, int r) {
static Node *lptr, *rptr, *idx, *pre;
static Node *lpre, *rnext;
idx = head;
int sum_element = 0; // element items
pre = NULL;
while(idx != NULL) {//Array[sum_element+1, sum_element+idx->vn]
if(sum_element+1 < l && l <= sum_element + idx->vn) { // split
split(idx, l-(sum_element+1)); // left[...l-1], right[l...]
lptr = idx->next, lpre = idx;
}
if(sum_element+1 == l)
lptr = idx, lpre = pre;
if(sum_element+1 <= r && r < sum_element + idx->vn) { // split
split(idx, r-sum_element); // left[...r], right[r+1...]
rptr = idx->next;
}
if(sum_element+idx->vn == r)
rptr = idx;
sum_element += idx->vn;
pre = idx, idx = idx->next;
}
//printList(head);
rnext = rptr->next;
int stkIdx = 0;
idx = lptr;
while(idx != rnext) {
stk[stkIdx++] = idx;
idx->inv_label = !idx->inv_label;
idx = idx->next;
}
stkIdx--;
if(lpre == NULL && rnext == NULL) { //[{ZZZ}]
head = stk[stkIdx];
idx = head;
stkIdx--;
while(stkIdx >= 0) {
idx->next = stk[stkIdx--];
idx = idx->next;
}
idx->next = NULL;
} else if(lpre == NULL && rnext != NULL) {//[{ZZZ}XXX]
head = rnext;
idx = rnext;
while(idx->next != NULL)
idx = idx->next;
while(stkIdx >= 0) {
idx->next = stk[stkIdx--];
idx = idx->next;
}
idx->next = NULL;
} else if(lpre != NULL && rnext == NULL) {//[XXX{ZZZ}]
idx = lpre;
while(stkIdx >= 0) {
idx->next = stk[stkIdx--];
idx = idx->next;
}
idx->next = NULL;
} else { //[XXX{ZZZ}XXX]
lpre->next = rnext;
idx = rnext;
while(idx->next != NULL)
idx = idx->next;
while(stkIdx >= 0) {
idx->next = stk[stkIdx--];
idx = idx->next;
}
idx->next = NULL;
}
maintainList(head);
//printList(head);
return head;
}
int main() {
int n, m, l, r;
int i, j;
while(scanf("%d %d", &n, &m) == 2) {
//<init>
p_size = (int)sqrt(n);
Node *head = new Node(), *pre = NULL, *idx = head;
for(i = 1; i <= n; i++) {
if(idx->vn < p_size) {
idx->v[idx->vn++] = i;
} else {
idx->next = new Node();
pre = idx, idx = idx->next;
i--;
}
}
//</init>
while(m--) {
scanf("%d %d", &l, &r);
head = inverseArray(head, l, r);
}
printAns(head);
}
return 0;
}