11260: 【原1260】Toy

题目描述

author: Cheezer 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1260

Description

cc很喜欢玩玩具，在cc的强烈要求下，爸爸妈妈又给她买了新玩具。这种玩具在买来的时候，原本是独立的n块，并且这n块会有M种不同的形状。

现在cc想把这些块连接成一条长链。cc的手中始终会握住当前长链玩具的首部，加入第i块( 形状为m[i] )时，cc会写下一个数字k[i]，然后将其插入到长链的从首部开始数的第k[i]个块与第k[i]+1个块之间,如果k[i]=0则接到首部之前，如果k[i]=当前链长度len，则接到尾部之后。但是当cc将这个长链玩具接好时，cc发现玩具实在太长了，而且全部都缠在了一起，根本不知道是个什么样子。

不过幸好cc还留着那些写下的数字，现在请你根据数字，模拟出长链玩具的最终形态。

Input Format

第一行一个正整数n。

以后n行，每一行两个正整数k[i]和m[i],如上文所述

20%：n<=5000

40%：n<=50000

100%：n<=300000 , m<=500000

Output Format

仅1行，输出从长链的首部到尾部的每个块的形状

Sample Input

Sample Output

7 3 6 5

yyong119's solution

#include <cstdio>
#define MAX_N 300010
using namespace std;
struct Node {
    int pos, num;
} a[MAX_N];
int n;
int tree[MAX_N << 2];
int ans[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1;
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
void build_tree(int x, int l, int r) {
    tree[x] = r - l + 1;
    if (l != r) {
        int mid = (l + r) >> 1;
        build_tree(x << 1, l, mid);
        build_tree(x << 1 | 1, mid + 1, r);
    }
}
int query(int x, int l, int r, int pos) {
    if (l == r) {
        tree[x] = 0;
        while (x) {
            x >>= 1; --tree[x];
        }
        return l;
    }
    // printf("%d %d %d %d\n",l, r, tree[x << 1], tree[x << 1 | 1]);
    int mid = (l + r) >> 1;
    if (tree[x << 1] >= pos) return query(x << 1, l, mid, pos);
    else return query(x << 1 | 1, mid + 1, r, pos - tree[x << 1]);
}
int main() {
    n = read();
    build_tree(1, 1, n);
    for (register int i = 0; i < n; ++i) {
        a[i].pos = read(); a[i].num = read();
    }
    for (register int i = n - 1; i >= 0; --i) {
        int k = query(1, 1, n, a[i].pos + 1);
        // printf("##%d\n", k);
        ans[k] = a[i].num;
    }
    for (register int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
struct Tr {
    int siz, v, prio, lch, rch;
};
Tr tr[300005];
int S = 0, root = 0;
int n, ans[300005], tot = 0;
void maintain(int x){
    tr[x].siz = 1 + tr[tr[x].lch].siz + tr[tr[x].rch].siz;
}
int tree_new(int k){
    ++S;
    tr[S].siz = 1, tr[S].v = k, 
    tr[S].prio = rand(), 
    tr[S].lch = tr[S].rch = 0;
    return S;
}
void Split_K(int now, int k, int &x, int &y){
    if (!now) x = y = 0;
    else {
        if (k > tr[tr[now].lch].siz){
            x = now, Split_K(tr[now].rch, k - tr[tr[now].lch].siz - 1, tr[now].rch, y);
        }else {
            y = now, Split_K(tr[now].lch, k, x, tr[now].lch);
        }
        maintain(now);
    }
}
int Merge(int x, int y){
    if (!x || !y) return x + y;
    if (tr[x].prio < tr[y].prio){
        tr[x].rch = Merge(tr[x].rch, y);
        maintain(x);
        return x;
    }else{
        tr[y].lch = Merge(x, tr[y].lch);
        maintain(y);
        return y;
    }
} 
void Insert_K(int k, int v){
    int x, y, z = tree_new(v);
    Split_K(root, k, x, y);
    root = Merge(Merge(x, z), y);
}
void Traverse(int cur){
    if (!cur) return ;
    Traverse(tr[cur].lch);
    ans[++tot] = tr[cur].v;
    Traverse(tr[cur].rch);
}

void init(){
    n = read();
    tr[0].siz = 0;
    srand(time(NULL));
    for (int i = 1; i <= n; ++i){
        int pos = read(), u = read();
        Insert_K(pos, u);
    }
}
void solve(){
    Traverse(root);
    for (int i = 1; i <= tot; ++i)
        printf("%d ", ans[i]);
}
int main(){
    init();
    solve();
    return 0;
}