题意

给出一个排列 { p i } \{p_i\} {pi},同时给出一个炸弹顺序 { q i } \{q_i\} {qi},第 i i i 颗炸弹放在第 q i q_i qi 处。每次从左往右加入 p i p_i pi,遇到炸弹时炸掉当前最大值。输出放前 i i i 颗炸弹最终序列的最大值( i = 0 , 1 , 2... , n 1 i=0,1,2...,n-1 i=0,1,2...,n1)。

分析

这题真是巧妙啊!我太蒻了!
首先, a n s i a n s i + 1 ans_i\geq ans_{i+1} ansiansi+1。于是我们每次要得到 a n s i + 1 ans_{i+1} ansi+1,只需要从 a n s i ans_i ansi 不断减 1 1 1 减过来即可。那么要减多少次 1 1 1 呢?这就要观察答案的性质了。
a n s < x ans<x ans<x 时,有以下事实:
每个大于等于 x x x 的数 v v v 都会被炸掉!也就是说,每个 v v v 后面都有一个炸弹专门炸它的。每个 v v v 和离它最近的炸弹形成一个匹配。
那么,我们让每个 v v v 所在位置 + 1 +1 +1,让每个炸弹所在位置 1 -1 1,令 b i b_i bi [ i , n ] [i,n] [i,n] 的后缀和。(有点像括号序列)
现在 a n s < x ans<x ans<x 的条件即为:对于每个 b i b_i bi b i 0 b_i\leq 0 bi0
所以我们用线段树找到最大的 b i b_i bi 即可。
每次加数或者遇到炸弹都是修改一个区间的后缀和,用线段树实现区间加即可。
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
此题的关键在于每次判断 a n s ans ans 要减到多少,然而我太蒻了根本不会QAQ

代码如下

#include <bits/stdc++.h>
#define N 300005
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
int p[N], q[N];
LL val[N * 4], tag[N * 4];
void pushdown(int rt){
	if(tag[rt]){
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		val[rt << 1] += tag[rt];
		val[rt << 1 | 1] += tag[rt];
		tag[rt] = 0;
	}
}
void update(int l, int r, int rt, int a, int b, int c){
	if(l >= a && r <= b){
		val[rt] += c;
		tag[rt] += c;
		return;
	}
	pushdown(rt);
	int m = l + r >> 1;
	if(a <= m) update(lson, a, b, c);
	if(b > m) update(rson, a, b, c);
	val[rt] = max(val[rt << 1], val[rt << 1 | 1]);
}
int main(){
	int i, j, n, m, ret;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &j), p[j] = i;
	for(i = 1; i <= n; i++) scanf("%d", &q[i]);
	ret = n;
	update(1, n, 1, 1, p[ret], 1);
	printf("%d ", ret);
	for(i = 1; i < n; i++){
		update(1, n, 1, 1, q[i], -1);
		while(val[1] <= 0){
			ret--;
			update(1, n, 1, 1, p[ret], 1);
		}
		printf("%d ", ret);
	}
	return 0;
}