CF1326E Bombs（思维题）

题意

给出一个排列 $\left\{p_i\right\}${pi​}，同时给出一个炸弹顺序 $\left\{q_i\right\}${qi​}，第 $i$i 颗炸弹放在第 $q_i$qi​ 处。每次从左往右加入 $p_i$pi​，遇到炸弹时炸掉当前最大值。输出放前 $i$i 颗炸弹最终序列的最大值（ $i=0,1,\mathrm{2...},n-1$i=0,1,2...,n−1）。

分析

这题真是巧妙啊！我太蒻了！
首先， $an{s}_i\ge an{s}_{i+1}$ansi​≥ansi+1​。于是我们每次要得到 $an{s}_{i+1}$ansi+1​，只需要从 $an{s}_i$ansi​ 不断减 $1$1 减过来即可。那么要减多少次 $1$1 呢？这就要观察答案的性质了。
当 ans<x 时，有以下事实：
每个大于等于 $x$x 的数 $v$v 都会被炸掉！也就是说，每个 $v$v 后面都有一个炸弹专门炸它的。每个 $v$v 和离它最近的炸弹形成一个匹配。
那么，我们让每个 $v$v 所在位置 $+1$+1，让每个炸弹所在位置 $-1$−1，令 $b_i$bi​ 为 $[i,n]$[i,n] 的后缀和。(有点像括号序列）
现在 ans<x 的条件即为：对于每个 $b_i$bi​， $b_i\le 0$bi​≤0。
所以我们用线段树找到最大的 $b_i$bi​ 即可。
每次加数或者遇到炸弹都是修改一个区间的后缀和，用线段树实现区间加即可。
时间复杂度 $O\left(nlogn\right)$O(nlogn)
此题的关键在于每次判断 $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;
}