解題區/解題區 - UVa

UVa 11071 - Permutation Representation

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定一個置換群，要我們表示成以下特定的形式，1 ≤ n ≤ 200000。

由右至左看，第一次為了填5必須移動2位，第二次移動填4也是移動2位
3 2 5 1 4 -> 1 4 3 2 5 移動 2
1 4 3 2 5 -> 3 2 1 4 5 移動 2
3 2 1 4 5 -> 2 1 3 4 5 移動 2
2 1 3 4 5 -> 1 2 3 4 5移動 1

解題者：李育賢
解題日期：2008 年 3 月 21 日

Sample Input

1
2
3
4
5
6
5
1 2 3 4 5
3 2 5 1 4
4
1 2 3 4
3 4 1 2

Sample Output

1
2
0 1 2 2 2
0 0 0 2

Solution

李育賢他的解法使用線段樹，靜態操作 shift rotate 和 remove 的問題，仔細想想似乎也不難，但是沒想到我用了模擬的塊狀鏈表解決這一道題目。

為了解決 shift，還必須增加數字的映射，否則沒辦法再 O(sqrt(n)) 時間內完成操作。

塊狀鏈表相當暴力模擬，最簡單地盡可能讓塊差不多是 sqrt(n) 個元素，這樣再 shift 的時候，可以將 head 指標移動次數卡在 sqrt(n) 將給一個操作都限制在 O(sqrt(n))。

塊狀鏈表看看就好，還是回去寫線段樹吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
// 11071 - Permutation Representation
#define MAXN 262144
int A[MAXN], B[MAXN], C[MAXN];
struct PILE {
    int v[512], size;
    PILE *next;
    int label;
    static int MAXSIZE, BUFSIZE;
    static PILE *head;
    PILE() {
        size = label = 0;
        next = NULL;
    }
};
int PILE::MAXSIZE = 512, PILE::BUFSIZE = 0;
PILE* PILE::head = NULL;
int mp[MAXN]; // map
PILE* removePileElement(PILE *where, int pos) {
    if (pos == where->size - 1) {
        where->size--;
        return where->next;
    }
    assert(pos < where->size);
    PILE::BUFSIZE++;
    PILE *m = new PILE();
    m->label = PILE::BUFSIZE;
    assert(m->size == 0);
    for (int i = pos + 1; i < where->size; i++) {
        m->v[m->size++] = where->v[i];
        assert(where->v[i] < MAXN);
        mp[where->v[i]] = m->label;
    }
    where->size = pos;
    m->next = where->next;
    where->next = m;
    return m;
}
int shrinkList() {
    for (PILE *i = PILE::head; i->next != PILE::head; ) {
        PILE *next = i->next;
        int prevsize = i->size;
        int nextsize = next->size;
        if (prevsize + nextsize <= PILE::MAXSIZE) {
            for (int j = 0; j < next->size; j++) {
                i->v[i->size++] = next->v[j];
                mp[next->v[j]] = i->label;
            }
            i->next = next->next;
            delete next;
        } else
            i = i->next;
    }
    return 0;
}
void printPile() {
    PILE *i = PILE::head;
    do {
        for (int j = 0; j < i->size; j++) {
            printf("%d -> ", i->v[j] + 1);
        }
        printf(" | ");
        i = i->next;
    } while (i != PILE::head);
    puts("\n====");
}
void solve(int n) {
//    printPile();
    for (int i = n - 1; i >= 0; i--) {
        PILE *where = NULL;
        int pos = -1;
//        printf("%d\n", i);
        for (PILE *j = PILE::head; ; j = j->next) {
            if (j->label == mp[i]) {
                where = j;
                break;
            }
        }
        assert(where != NULL);
        for (int j = 0; j < where->size; j++) {
            if (where->v[j] == i) {
                pos = j;
                break;
            }
        }
        assert(pos >= 0  && pos < where->size);
        int shift = where->size - pos - 1;
//        printf("%d %d %d\n", node[where].size, pos, shift);
        for (PILE *j = where->next; j != PILE::head; j = j->next) {
            shift += j->size;
        }
//        printf("shift %d\n", shift);
        C[i] = shift;
        PILE::head = removePileElement(where, pos);
        shrinkList();
//        printPile();
    }
    for (PILE *i = PILE::head, *j = i->next; j != PILE::head; j = i->next) {
        delete i;
        i = j;
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &B[i]);
        }
//        for (int i = 0; i < n; i++) {
//            A[i] = i + 1;
//            B[i] = A[i];
//        }
//        for (int i = 0; i < n; i++) {
//            int x = rand()%n;
//            int y = rand()%n;
//            swap(B[x], B[y]);
//        }
        for (int i = 0; i < n; i++) {
            C[A[i] - 1] = B[i] - 1;
        }
        
        PILE *node = new PILE();
        PILE::MAXSIZE = (int)sqrt(n) + 1;
        PILE::head = node;
        PILE::BUFSIZE = 0;
        PILE::BUFSIZE++;
        node->label = PILE::BUFSIZE, node->next = node;
        for (int i = 0; i < n; i++) {
            node->v[node->size++] = C[i];
            mp[C[i]] = node->label;
            if (node->size == PILE::MAXSIZE) {
                PILE *tmp = new PILE();
                PILE::BUFSIZE++;
                tmp->label = PILE::BUFSIZE;
                tmp->next = node->next;
                node->next = tmp;
                node = node->next;
            }
        }
        
        solve(n);
        
        for (int i = 0; i < n; i++) {
            printf("%d%c", C[i], i == n - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 5
 1 2 3 4 5
 3 2 5 1 4
 4
 1 2 3 4
 3 4 1 2
*/