Codeforces 1326 E Bombs —— 线段树，括号匹配

本文主要是介绍Codeforces 1326 E Bombs —— 线段树，括号匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有n个数，然后有n个炸弹，告诉你n个位置的数和每个炸弹的位置，如果确定了是前i个炸弹的话，那么这i个炸弹会按照位置从小到大爆炸，位于x位置的炸弹会炸掉前x数中剩下数的最大值。
让你输出n个值，第i个值表示取前i-1个炸弹时，剩下的数最大是多少。

题解：

有些想法，一看就知道无法每次都做一遍，那么只能每次新的炸弹来的时候，找到对应的最大值删掉即可，但是每次又并不是找到这个炸弹的前面的数，而是可能这个炸弹由于位置比较小，可能取代之前的炸弹，然后之前的炸弹又会一个一个取代过去，找到最终正确的炸弹，再在那个区间找到正确的值：
假设之前的炸弹的位置用下箭头表示，匹配的最大值的位置用圈表示，当前的炸弹位置用上箭头表示：
在这里插入图片描述
那么对于这张图，新来的箭头位置最小，所以先匹配，所以前面两个圆圈中，一定一个是由它匹配，那么对于第一个下箭头，一定匹配另一个圆圈，因为他们原本就是最大值。所以此时需要重新找最大值的区间是1-最后一个下箭头。
在这里插入图片描述
但是如果图变成了这样呢，那么当前会找到第一个圆圈，第一个下箭头需要重新找，而第二个下箭头找到的依旧是第二个圆圈，所以，这种情况找的区间是1-第一个下箭头。
再多观察几个样例会发现，其实无论下箭头匹配的是哪个圆圈都无所谓，重要的是每个圆圈都可以与这个圆圈后面第一个下箭头的位置消掉。那么现在其实就变成了一个括号匹配，对于新来的位置，找到它右边最后一个从当前位置开始，无法完美匹配的炸弹位置即可。
那么怎么看是否完美匹配，我们只需要将左括号到右括号-1的区间的值置为1即可，那么下次如果有这个区间的炸弹，就可以找到这个右括号了。
所以我使用两个线段树，第一个线段树是查询要询问区间的最大值的位置的。
第二个线段树是查询当前点右边第一个0的位置。
有点时间没写查询位置了，还wa了好几发

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int mi[N*4],mx[N*4],a[N],f[N*4];
void build(int l,int r,int root){if(l==r){mx[root]=a[l];return ;}int mid=l+r>>1;build(l,mid,root<<1);build(mid+1,r,root<<1|1);mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
void del(int l,int r,int root,int p){if(l==r){mx[root]=0;return ;}int mid=l+r>>1;if(mid>=p)del(l,mid,root<<1,p);elsedel(mid+1,r,root<<1|1,p);mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
int p;
int q_mx(int l,int r,int root,int ql,int qr){if(l==r)return l;if(l>=ql&&r<=qr){int mid=l+r>>1;if(mx[root<<1]==mx[root])return q_mx(l,mid,root<<1,ql,qr);return q_mx(mid+1,r,root<<1|1,ql,qr);}int mid=l+r>>1,ans=0;if(mid>=ql)ans=q_mx(l,mid,root<<1,ql,qr);if(mid<qr){int p=q_mx(mid+1,r,root<<1|1,ql,qr);if(a[p]>a[ans])ans=p;}return ans;
}void push_down(int root){if(!f[root])return ;mi[root<<1]+=f[root];mi[root<<1|1]+=f[root];f[root<<1]+=f[root];f[root<<1|1]+=f[root];f[root]=0;
}
void update(int l,int r,int root,int ql,int qr,int v){if(l>=ql&&r<=qr){mi[root]+=v;f[root]+=v;return ;}int mid=l+r>>1;push_down(root);if(mid>=ql)update(l,mid,root<<1,ql,qr,v);if(mid<qr)update(mid+1,r,root<<1|1,ql,qr,v);mi[root]=min(mi[root<<1],mi[root<<1|1]);
}
int q_zero(int l,int r,int root,int ql,int qr){if(l==r)return mi[root]==0?l:0;push_down(root);if(l>=ql&&r<=qr){int mid=l+r>>1;if(mi[root<<1]==0)return q_zero(l,mid,root<<1,ql,qr);else if(mi[root<<1|1]==0)return q_zero(mid+1,r,root<<1|1,ql,qr);return 0;}int mid=l+r>>1,ans=0;if(mid>=ql)ans=q_zero(l,mid,root<<1,ql,qr);if(mid<qr){int p=q_zero(mid+1,r,root<<1|1,ql,qr);if(!ans)ans=p;}return ans;
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);int x;printf("%d\n",mx[1]);for(int i=1;i<=n;i++){scanf("%d",&x);int p=q_zero(1,n,1,x,n);p=p?p:x;int p2=q_mx(1,n,1,1,p);del(1,n,1,p2);a[p2]=0;if(p2<x)update(1,n,1,p2,x-1,1);if(p2>x)update(1,n,1,x,p2-1,-1);if(i!=n)printf("%d\n",mx[1]);}return 0;
}