绝对是很好的题
把问题转化成当第 i 个询问的答案是数值 x 时是否可行
要判断值 x 是否可行, 只要再将问题转化成 a 数组里 >=x 的值数量是否严格大于 b 数组里的 >=x 的值
那么线段树叶子结点维护对于值 x 的 a 数组里的合法数数量 - b 数组里的合法数数量, 如果是正数即这个值可行
线段树维护区间最大值, 然后询问最靠右的非负叶子下标
- #include<bits/stdc++.h>
- #include<vector>
- using namespace std;
- #define maxn 1000005
- int Q,n,m,a[maxn],b[maxn],ans[maxn];
- struct Query{int op,i,x;}q[maxn];
- vector<int>v;
- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- int lazy[maxn<<2],Max[maxn<<2];
- void pushdown(int rt){
- if(lazy[rt]!=0){
- Max[rt<<1]+=lazy[rt];
- Max[rt<<1|1]+=lazy[rt];
- lazy[rt<<1]+=lazy[rt];
- lazy[rt<<1|1]+=lazy[rt];
- lazy[rt]=0;
- }
- }
- void pushup(int rt){
- Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
- }
- void update(int L,int R,int val,int l,int r,int rt){
- if(L<=l && R>=r){
- lazy[rt]+=val;
- Max[rt]+=val;
- return;
- }
- pushdown(rt);
- int m=l+r>>1;
- if(L<=m)update(L,R,val,lson);
- if(R>m)update(L,R,val,rson);
- pushup(rt);
- }
- int query(int l,int r,int rt){
- if(Max[rt]<=0)return -1;
- if(l==r && Max[rt]>0)return l;
- pushdown(rt);
- int m=l+r>>1;
- if(Max[rt<<1|1]>0)
- return query(rson);
- else if(Max[rt<<1]>0)
- return query(lson);
- else return -1;
- }
- int main(){
- cin>>n>>m;
- for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
- for(int i=1;i<=m;i++)scanf("%d",&b[i]),v.push_back(b[i]);
- cin>>Q;
- for(int i=1;i<=Q;i++){
- scanf("%d%d%d",&q[i].op,&q[i].i,&q[i].x);
- v.push_back(q[i].x);
- }
- sort(v.begin(),v.end());
- v.erase(unique(v.begin(),v.end()),v.end());
- int nn=v.size();
- for(int i=1;i<=n;i++){
- int pos=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
- update(1,pos,1,1,nn,1);
- }
- for(int i=1;i<=m;i++){
- int pos=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
- update(1,pos,-1,1,nn,1);
- }
- for(int i=1;i<=Q;i++){
- int op=q[i].op,p=q[i].i,x=q[i].x;
- if(op==1){// 修改 a 的值
- int pos=lower_bound(v.begin(),v.end(),a[p])-v.begin()+1;
- update(1,pos,-1,1,nn,1);
- a[p]=x;
- pos=lower_bound(v.begin(),v.end(),a[p])-v.begin()+1;
- update(1,pos,1,1,nn,1);
- ans[i]=query(1,nn,1);
- if(ans[i]>0)
- ans[i]=v[ans[i]-1];
- }
- else {
- int pos=lower_bound(v.begin(),v.end(),b[p])-v.begin()+1;
- update(1,pos,1,1,nn,1);
- b[p]=x;
- pos=lower_bound(v.begin(),v.end(),b[p])-v.begin()+1;
- update(1,pos,-1,1,nn,1);
- ans[i]=query(1,nn,1);
- if(ans[i]>0)
- ans[i]=v[ans[i]-1];
- }
- }
- for(int i=1;i<=Q;i++)
- cout<<ans[i]<<'\n';
- }
来源: http://www.bubuko.com/infodetail-3106897.html