[其他目][表] 排列＠Morris' Blog｜PChome Online 人新台

2014-03-08 10:44:42| 人2,479| 回0 | 上一篇 | 下一篇

[其他目][表] 排列

推 0 收藏 0 0 站台

Description

得 UVa 11922 - Permutation Transformer ?

定一列 1, 2, 3, ..., n，藉由 m 指令，每指令序列的 [a, b] 的元素移到序列最後端。

出最後的果。

Input Format

第一行有一正整 T，代表有料。

每正整 n, m。(n, m <= 100,000)

接下 m 行指令，每行上有整 a, b (1 <= a <= b <= n)。

Output Format

每出一行 n 正整。

Sample Input

3 8 1 3 7 9 2 2 6 3 8 5 5 1 1 5 5 2 3 2 5 3 4

Sample Output

1 2 8 3 4 5 6 7 1 7 6 8 9 2 3 4 5 2 5 4 1 3

原封不於 [UVA][表] 11922 - Permutation Transformer 的解法

然是表，但在也很一定是表的限制。
路上很多定要在 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 指，稍微分了。

原本 UVa 目要做反操作。
如果不用做反，把反取消掉，且把 stack 替成 queue 即可。

#include <stdio.h>
#include <math.h>
#include <queue>
#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;
    int flag = 0;
    while(idx != NULL) {
        for(i = 0; i < idx->vn; i++) {
           if(flag)   putchar(' ');
           flag = 1;
           printf("%d", idx->v[i]);
        }
        idx = idx->next;
    }
    puts("");
    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;
    &nbs;   }
        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* inverseArray(Node *head, int l, int r) {
    static Node *lptr, *rptr, *idx, *pre;
    static Node *lpre, *rnext;
   queue<Node*> Q;
    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) {
       Q.push(idx);
        idx = idx->next;
    }
    if(lpre == NULL && rnext == NULL) { //[{ZZZ}]
        head = Q.front(), Q.pop();
        idx = head;
        while(!Q.empty()) {
            idx->next = Q.front(), Q.pop();
            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(!Q.empty()) {
            idx->next = Q.front(), Q.pop();
            idx = idx->next;
        }
        idx->next = NULL;
    } else if(lpre != NULL && rnext == NULL) {//[XXX{ZZZ}]
        idx = lpre;
        while(!Q.empty()) {
            idx->next = Q.front(), Q.pop();
            idx = idx->next;
        }
        idx->next = NULL;
    } else { //[XXX{ZZZ}XXX]
        lpre->next = rnext;
        idx = rnext;
        while(idx->next != NULL)
            idx = idx->next;
        while(!Q.empty()) {
            idx->next = Q.front(), Q.pop();
            idx = idx->next;
        }
        idx->next = NULL;
    }
    maintainList(head);
    //printList(head);
    return head;
}
int main() {
   int testcase;
    int n, m, l, r;
    int i, j;
    scanf("%d", &testcase);
    while(testcase--) {
       scanf("%d %d", &n, &m);
        //<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;
}