说在前面
这两道题好像是一样的,但是我一开始没看出来...
Problem
Solution
Thinking 1
想根据输入的顺序每一次都找到当前的位置,然后在当前的BIT中计入,但是这样在它后面的顺序就要全部往后一个,比较难整(我觉得可以再搞一个后缀和的东西维护一下?
Thinking 2
不难发现最后一个人的位置是确定的,(P_n + 1),设(H_i)为第(i)个人最终的顺序,(已经知道(H_n = P_n + 1))考虑:
- 对于第(n - 1)个人,它前面有(P_{n - 1})个人,那么就是在所有人中去掉(H_n),然后在找到第(P_{n - 1} + 1)小的。
- 归纳,不难得到,将顺序倒序,第(k)个人的顺序(H_k)即为(1 sim n)去掉(H_{k + 1},H_{k + 2},cdots,H_n)后取第(P_k + 1)小。
Thinking 3
那么我们现在就是要:
- 每次查询当前第(P_k + 1)小
- 将(H_k)所在位置清0
不难想到权值线段树,树上二分可是1个log!
# include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
int f[N];
struct Node
{
int p,v;
}a[N];
struct node
{
int val;
}T[N << 2];
void build(int root,int l,int r)
{
if(l == r)
{
T[root].val = 1;
return;
}
int mid = (l + r) >> 1;
build(root << 1,l,mid),build(root << 1 | 1,mid + 1,r);
T[root].val = T[root << 1].val + T[root << 1 | 1].val;
return;
}
void update(int root,int l,int r,int x,int d)
{
if(l == r && l == x)
{
T[root].val += d;
return;
}
int mid = (l + r) >> 1;
if(l <= x && x <= mid) update(root << 1,l,mid,x,d);
if(mid + 1 <= x && x <= r) update(root << 1 | 1,mid + 1,r,x,d);
T[root].val = T[root << 1].val + T[root << 1 | 1].val;
return;
}
int qfind(int root,int l,int r,int k)
{
int mid = (l + r) >> 1;
if(l == r) return l;
if(T[root << 1].val >= k)
{
return qfind(root << 1,l,mid,k);
}
else
{
return qfind(root << 1 | 1,mid + 1,r,k - T[root << 1].val);
}
}
int H[N];
int main(void)
{
while(~scanf("%d",&n))
{
for(int i = 1; i <= n; i++)
{
scanf("%d%d",&a[i].p,&a[i].v);
}
build(1,1,n);
for(int i = n; i >= 1; i--)
{
H[i] = qfind(1,1,n,a[i].p + 1);
update(1,1,n,H[i],-1);
}
for(int i = 1; i <= n; i++)
{
f[H[i]] = a[i].v;
}
for(int i = 1; i <= n; i++) printf("%d ",f[i]);
printf("
");
}
return 0;
}