11260: 【原1260】Toy

题目描述

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

Description

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

Input Format

20%：n<=5000

40%：n<=50000

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

Sample Input

``````4
0 7
1 5
1 3
2 6
``````

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];
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() {
build_tree(1, 1, n);
for (register int i = 0; i < n; ++i) {
}
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 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(){
tr[0].siz = 0;
srand(time(NULL));
for (int i = 1; i <= n; ++i){
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;
}
``````