24h購物| | PChome| 登入
2013-03-22 08:33:45| 人氣1,081| 回應0 | 上一篇 | 下一篇

[ZJ][塊狀鏈表] a063. SGU 187. Twist and whirl - want to cheat

推薦 0 收藏 0 轉貼0 訂閱站台

內容 ：

A well-known sharper I*** invented a new way to swindle people. There are N thimbles on the table, and there is a small ball with the number under each of them. The balls are numbered with numbers from 1 to N from left to right. At one operation I*** changes the order of some subsequence of successive thimbles to the opposite. Your task is to find the order of numbers (from left to right) in sequence after all of his manipulations. The total number of manipulations is M.

輸入說明 ：

The first line contains two integer numbers N and M (1<=N<=130000, 1<=M<=100000) separated by a space. Each of the following M lines contains two integer numbers Pi, Qi (1<=Pi<=Qi<=N) - positions of the leftmost and rightmost thimbles in rotated sequence.

輸出說明 ：

Output the sequence of N numbers - the numbers of balls in the thimbles from left to right.

範例輸入 ： 

5 2
1 3
4 5

5 2
1 4
2 5

範例輸出 ：

3 2 1 5 4
4 5 1 2 3

提示 ：

SGU187加强，原题M<=2000改为M<=100000。

splay、AVL等的练习题，不卡空间，时限1s。

出處 ：

SGU 187 (管理：liouzhou_101)
雖然說是塊狀鏈表，但說實在也很難一定是塊狀鏈表的限制。
網路上很多規定要維護在 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 從原本的塊裂分出來，
然後將這些塊標記反轉操作，並且反轉這些塊的位置。

#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 ", idx->v[i]);
        else
            for(i = idx->vn-1; i >= 0; i--)
                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;
        }
        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--;
    idx = lpre;
    while(stkIdx >= 0) {
        if(idx == NULL)
            head = stk[stkIdx];
        else
            idx->next = stk[stkIdx];
        idx = stk[stkIdx--];
    }
    idx->next = rnext;
    maintainList(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;
}

我要檢舉
#塊狀鏈表#反轉操作#a063#SGU 187#Twist and whirl#want to cheat#加强版#區間反轉
台長： Morris

您可能對以下文章有興趣

人氣(1,081) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ] a647. 投資專家
此分類上一篇:[ZJ][Greedy] a646. 小民買糖果

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文