202503021947 POJ2182 Lost Cows

Lost Cows

title: 题目
有n只小动物，每只都有一个独特的编号，分别从1到n。现在他们从左到右依次排在一条直线上，顺序是乱的。
现在，我们只知道每个位置前面有几个比他小的数。请你根据给出的信息计算出每个位置上的数是多少。
n<=80000。
输入第一行是一个正整数n，表示小动物的数量。
接下来有n-1个数，第i个数表示在第i+1个位置以前有多少个比第i+1个位置上的数小的数。
输出n行，每行一个整数，表示对应位置小动物的编号。
 

title: input
5
1
2
1
0

title: output
2
4
5
3
1

title: 思路
 
画个图看看：
![[Pasted image 20220804162220.png]]
整体上来看没什么思路, 我们从后往前单独看最后一个数, 比它小的在前面有4个, 又知总共有6个数, 显然这个数就应该为5。
同理到倒数第二个数时, 前面4个数中比它小的只有一个, 故肯定为2.
枚举到导数第四个数时, 当前已经确定的位置有 [? 2 ? 4 5 ?], 且前面未确定的数中比当前数小的有2个, 说明该数应该在最后一位,为6。
 
因此可以推断出, `a[i] + 1` 就是 a[i] 在未确定数中的位置。
 
朴素方法可以声明一个 `vis[]` 数组记录每个数是否确定, 然后从1到n枚举直到未确定的数数量等于 `a[i] + 1`, 此时的下标就是该位置上的数。
 
优化方法：
同样是`vis`数组我们求前缀和之后可以通过二分快速找到 `a[i] + 1`。
因为每次确定一个数之后, 未确定数的数量就会变化, 不能用前缀和, 这里可以用树状数组/线段树来快速处理。
 
总共用到的只有区间求和和单点修改。
 
注意二分查询时的边界条件, 如果是这样会死循环：（我也不知道为啥）
~~~ c ++
while(l < r)
{
	int mid = l + r + 1 >> 1;
	if(query(1,mid,1,n) <= a[i] + 1)
		l = mid;
	else
		r = mid - 1;
}
~~~
 

title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 8e5 + 10, M = N << 2;
int t[M];
int a[N], ans[N];
 
void build(int l, int r, int u = 1)
{
    if (l == r)
    {
        t[u] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, u << 1), build(mid + 1, r, u << 1 | 1);
    t[u] = t[u << 1] + t[u << 1 | 1];
}
 
int query(int L, int R, int l, int r, int u = 1)
{
    if (L <= l && R >= r)
    {
        return t[u];
    }
    int mid = l + r >> 1;
    int res = 0;
    if (L <= mid)
        res += query(L, R, l, mid, u << 1);
    if (R > mid)
        res += query(L, R, mid + 1, r, u << 1 | 1);
    return res;
}
 
void modify(int idx, int l, int r, int u = 1)
{
    if (l == r)
    {
        t[u] = 0;
        return;
    }
    int mid = l + r >> 1;
    if (mid >= idx)
        modify(idx, l, mid, u << 1);
    else
        modify(idx, mid + 1, r, u << 1 | 1);
    t[u] = t[u << 1] + t[u << 1 | 1];
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
        cin >> a[i];
    build(1, n);
    for (int i = n; i > 0; i--)
    {
        int l = 1, r = n;
        while (l < r) // 二分找所有前缀和位置中等于 a[i] + 1的位置
        {
            int mid = (l + r) >> 1;
            if (query(1, mid, 1, n) >= a[i] + 1)
                r = mid;
            else
                l = mid + 1;
        }
        ans[i] = r;
        modify(r, 1, n); // 将该数标记为已确定
    }
 
    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}
~~~