2021牛客暑期多校训练营2 K题 Stack

题目描述

ZYT had a magic permutation $a_1,a_2,\cdots, a_n$, and he constructed a sequence $b_1,b_2,\cdots b_n$ by the following pseudo code:

Stk is an empty stack
for i = 1 to n :
while ( Stk is not empty ) and ( Stk's top > a[i] ) :
pop Stk
push a[i]
b[i]=Stk's size

But he somehow forgot the permutation ${a}$, and only got some ${k}$ elements of $b_i$.

Construct a permutation ${a}$ satisfying these $b_i$, or determine no such permutation exists.

Here a permutation refers to a sequence that contains all integers from ${1}$ to ${n}$ exactly once.

输入描述:

The first line contains two integers ${n},{k} (1\leq k\leq n)$— the length of the permutation, the number of left $b_i$.

Then ${k}$ lines each contains two integer $p_i,x_i$, denoting that $b_{p_i}=x_i$.

输出描述:

Output one line with n integers $a_1,a_2,\cdots a_n$ — a possible permutation.

If no such permutation exists, output one integer -1.

示例1

输入

5 2
2 2
5 4

输出

1 2 5 3 4

示例2

输入

10 1
1 10

输出

-1

备注:

It's guaranteed that $n\leq 10^6,1\leq p_i,x_i\leq n$, and $\forall i\ne j,p_i\ne p_j$.

代码

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;

int n, k;
int a[maxn];
int b[maxn];
int tree[maxn];
int num[maxn];

int lowbit(int x) { return x & (-x); }

for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}

int getsum(int x) {
int sum = 0;
for (int i = x; i >= 1; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}

int mid_query(int l, int r, int k) {
while (r - l > 1) {
int mid = (l + r) >> 1;
int num = getsum(mid);
if (num >= k)
r = mid;
else
l = mid;
}
return r;
}

int main() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
int l, r;
cin >> l >> r;
b[l] = r;
}
int flag = 0;
for (int i = 1; i <= n; i++) {
if (!b[i]) {
b[i] = b[i - 1] + 1;
}
if (b[i] - b[i - 1] > 1) flag = 1;
}
if (flag == 1) {
cout << -1 << endl;
return 0;
}
for (int i = n; i >= 1; i--) {
a[i] = mid_query(0, n + 1, b[i]);
}