赛中感觉还是思路不是很清晰啊。首先对于此题，赛中犯了两点错误，一是对于难题瞎猜假算法，可能是cf前面的题比较简单，就很容易养成猜结论的习惯，这题也是先猜了个假结论，然后写了半小时wa了一次的，感觉十分影响接下来的精力，二是对于思路的问题，我一直认为是迭代求解的，但是我已经把最后我需要做的操作想出来了，已经卡住了，其实就没有必要继续写下去了，后来都是垃圾思考时间，其实应该及时推出的，去想其他思路。
首先是这题的主体思路，尝试过模拟的我们，会发现前一次的答案和后一次的答案，是很难快速转移的，虽然只是加了一个炸弹，但是不能保证它对后续的影响是什么，所以迭代的思路应该思考过问题后正确放弃。这题的主要思路是因为答案的递减性，答案之间的差距总体是o(n)的，你要做的就是检查当前的答案是否可能为x，如果你能快速判出这个可行性，那么问题复杂度就降下来了。
对于如何判断答案是否可能是x，你会想到大于x的答案都应该被炸掉，就有了对于大于x的数字，都有这样一个规律：
如果他是从右边查第一个大于x的，它右边至少有1个炸弹。
如果他是从右边查第二个大于x的，它右边至少有2个炸弹。
如果他是从右边查第三个大于的，它右边至少有3个炸弹。
你会发现这样一个事情，你要做的就是检查所有的是否都满足条件。但是你发现这其实是可以迭代的，对于判x可行，与判x-1是可以迭代的。你会发现对与一个位置，如果从判x到判x-1，就多了一个大于x-1的数字和一个炸弹而已。
我们开一个线段树，每个位置存（当前右侧大于x的数量-右侧炸弹的数量），小于0，答案就需要减1了，没次区间更新就好了。
#include<iostream> #include<string> #include<string.h> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long ll; typedef pair<int, int> P; const int maxn=3e5+10; int tree[maxn<<2],lazy[maxn<<2],a[maxn],p[maxn],tong[maxn]; void pushdown(int rt) { tree[lson]+=lazy[rt]; tree[rson]+=lazy[rt]; lazy[lson]+=lazy[rt]; lazy[rson]+=lazy[rt]; lazy[rt]=0; } void pushup(int rt) { tree[rt]=max(tree[lson],tree[rson]); } void update(int L,int R,int x,int l,int r,int rt) { if(L<=l&&r<=R) { tree[rt]+=x; lazy[rt]+=x; return; } pushdown(rt); int mid=(l+r)/2; if(L<=mid) update(L, R, x,l, mid, lson); if(mid<R) update(L, R, x,mid+1, r, rson); pushup(rt); } int q(int L,int R,int l,int r,int rt) { pushdown(rt); if(L<=l&&r<=R) { return tree[rt]; } int mid=(l+r)/2; int ans=0; if(L<=mid) ans=max(ans,q(L, R, l, mid, lson)); if(mid<R) ans=max(ans,q(L, R, mid+1, r, rson)); return ans; } inline int lowbit(int x){ return x&(-x); } int n; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; tong[a[i]]=i; } for(int i=1;i<=n;i++) cin>>p[i]; int now=n; update(1,tong[n], 1, 1, n ,1); for(int i=1;i<=n;i++) { cout<<now<<" "; if(i==n) break; update(1, p[i], -1, 1, n, 1); while(q(1, n, 1, n, 1)<=0) { now--; update(1,tong[now], 1, 1, n, 1); } } }