题目链接

https://codeforces.com/problemset/problem/1922/D

思路

假设在某一轮，元素$a_x$没有被删掉，而当前序列的$a_x$的前驱和后继也都没有被删掉，则元素$a_x$在下一轮也不会成为被删除的点。

假设在某一轮，元素$a_x$被删掉，则下一轮可能被删掉的点为其前驱和后继。

我们可以用$set$记录下一轮有可能被删除的点的下标，用链表维护当前存在的序列。

时间复杂度：$O(nlogn)$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 5;
int n;
int a[N], d[N];
bool st[N];
struct node
{int b, pre, nxt;
} p[N];
vector<int>v, ans;
void solve()
{cin >> n;v.clear();ans.clear();for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> d[i];}a[n + 1] = 0, d[n + 1] = 0;p[0].pre = 0;p[0].nxt = 1;p[n + 1].pre = n;p[n + 1].nxt = n + 1;//初始化for (int i = 1; i <= n; i++){st[i] = false;p[i].b = d[i];p[i].nxt = i + 1;p[i].pre = i - 1;}for (int i = 1; i <= n; i++){if (p[i].b < a[p[i].pre] + a[p[i].nxt]){if (!st[i]){st[i] = true;v.push_back(i);}}}for (int k = 1; k <= n; k++){ans.push_back(v.size());int low, high;set<int>var;for (int i = 0; i < v.size(); i++){low = v[i];high = v[i];int j = i;while (j + 1 < v.size() && p[v[j]].nxt  == v[j + 1]){j++;high = v[j];}if (p[low].pre >= 1)var.insert(p[low].pre);if (p[high].nxt <= n)var.insert(p[high].nxt);p[p[low].pre].nxt = p[high].nxt;p[p[high].nxt].pre = p[low].pre;i = j;}v.clear();for (int i : var){if (p[i].b < a[p[i].pre] + a[p[i].nxt]){if (!st[i]){st[i] = true;v.push_back(i);}}}}for (int val : ans){cout << val << " ";}cout << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}