题目描述

blablabla

样例

blablabla

算法1

(树状数组 + 二分) $O(nlogn * logn)$

秦淮dalao写的很详细了

时间复杂度 O(nlogn * logn)

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int c[N], n, rk[N];
pair<int, int> a[N];

void add(int x, int k) { for (; x <= n; x += -x & x) c[x] += k;  }

int ask(int x) { int ans = 0; for (; x; x -= -x & x) ans += c[x]; return ans; }

int main () {
    while (cin >> n) {
        memset(c, 0, sizeof c);
        for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second, ++a[i].first, add(i, 1);
        for (int i = n, l = 1, r = n; i; --i, l = 1, r = n) {
            while (l < r) {
                int mid = l + r >> 1;
                if (ask(mid) >= a[i].first) r = mid;
                else l = mid + 1;
            }
            rk[l] = a[i].second; add(l, -1);
        }
        for (int i = 1; i <= n; ++i) cout << rk[i] << ' '; cout << '\n';
    }
    return 0;
}

算法2

(树状数组 + 倍增) $O(nlogn * logn)$

记得要判断第i个人的位置要倒叙, 怎么去找位置(就是所有位置全置一,有人占了位置就置零)
应该不用解释为什么吧....

就说一下,怎么区倍增;
为了找到最小的i使得 Σc[i] == 第i个人入队时的位置
所以if ans + w > n 则 w >>= 1;
else if c[w + ans] < a[i] 则 ans += w, w <<= 1;
else if c[w + ans] > a[i] 则 w >>= 1;
当相等时 我们不能确定这个 w 是不是最小满足的 所以我们要在比较一下
if Σc[ans + w - 1] < a[i] ans = w, 答案找到
else w不是最小满足的 w >>= 1;

时间复杂度 $O(nlogn * logn)$

参考文献

C++ 代码

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

const int maxn = 2e5 + 5;

int c[maxn], n, rk[maxn];
PII a[maxn];

void add(int x, int k)
{
    for (; x <= n; x += -x & x) c[x] += k; 
}

int ask(int x)
{
    int ans = 0;
    for (; x; x -= -x & x) ans += c[x];
    return ans;
}

int main ()
{
    while (~scanf("%d", &n))
    {
        memset(c, 0, sizeof c);
        for (int i = 1; i <= n; ++i) 
            scanf("%d%d", &a[i].fi, &a[i].se), ++a[i].fi, add(i, 1);
        for (int i = n; i; --i)
        {
            int ans = 0;
            for (ll w = 1; ;)
            {
                if (w + ans <= n)
                {
                    int d = ask(w + ans);
                    if (d < a[i].fi) ans += w, w <<= 1;
                    else if (d == a[i].fi)
                    {
                        int dd = ask(w + ans - 1);
                        if (dd < a[i].fi) { ans += w; break;}
                        else w >>= 1;
                    }
                    else w >>= 1;
                }
                else w >>= 1;
            }
            rk[ans] = a[i].se; add(ans, -1);
        }
        for (int i = 1; i <= n; ++i) printf("%d ", rk[i]);
        puts("");
    }
    return 0;
}