**题意:**单调栈中先放数,然后计算出栈的大小存入b数组。现在给你b的部分数组,然后让你还原出一种a数组。
题解:
- 一开始我想了个假算法,把队友带飞了
- 我们从1-n开始构造b数组,如果没有给定b,则直接插入到当前栈中,及b[i] = b[i-1] + 1
- 并且根据b数组单调的关系,我们可知b[i] > b[i-1] + 1 的话,这样就中间肯定没有足够的数字进行填充,所以直接输出-1
-
我是写了个线段树维护区间第k小,然后取出,这样来进行构造a数组
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define lowbit(x) ((x) & -(x))
#define lson p << 1, l, mid
#define rson p << 1 | 1, mid + 1, r
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
const int N = 1e6 + 50;
int ans[N];
bool flag = 0;
int n, k;
bool vis[N];
queue<int> que;
struct node
{
int pos, x;
} e[N];
struct tree
{
int l, r;
int cnt;
} t[N << 2];
struct sj
{
int id;
int num;
} b[N];
void build(int l, int r, int p)
{
t[p] = {l, r, 0};
if (l == r)
{
t[p].cnt = 1;
return;
}
int mid = l + r >> 1;
build(l, mid, p << 1);
build(mid + 1, r, p << 1 | 1);
t[p].cnt = t[p << 1].cnt + t[p << 1 | 1].cnt;
}
int ask(int l, int r, int p, int k)
{
if (t[p].l == t[p].r)
{
return t[p].l;
}
if (k <= t[p << 1].cnt)
return ask(l, r, p << 1, k);
else
return ask(l, r, p << 1 | 1, k - t[p << 1].cnt);
}
void modify(int pos, int p)
{
if (t[p].l == t[p].r)
{
t[p].cnt = 0;
return;
}
int mid = t[p].l + t[p].r >> 1;
if (pos <= mid)
modify(pos, p << 1);
else
modify(pos, p << 1 | 1);
t[p].cnt = t[p << 1 | 1].cnt + t[p << 1].cnt;
}
void solve()
{
build(1, n, 1);
for (int i = n; i >= 1; i--)
{
int p = b[i].id, x = b[i].num;
int tmp = ask(1, n, 1, x);
vis[tmp] = 1;
ans[p] = tmp;
modify(tmp, 1);
}
rep(i, 1, n) cout << ans[i] << " ";
}
int main()
{
IOS cin >> n >> k;
rep(i, 1, k)
{
cin >> e[i].pos >> e[i].x;
b[e[i].pos].num = e[i].x;
}
for (int i = 1; i <= n; i++)
{
b[i].id = i;
if (b[i].num)
{
if (b[i].num > b[i - 1].num + 1)
{
printf("-1\n");
return 0;
}
}
else
b[i].num = b[i - 1].num + 1;
}
solve();
return 0;
}