山东一级造价师考试时间/上海seo推广方法

绝对是很好的题

把问题转化成当第i个询问的答案是数值x时是否可行

要判断值x是否可行，只要再将问题转化成a数组里>=x的值数量是否严格大于b数组里的>=x的值

那么线段树叶子结点维护对于值x的a数组里的合法数数量-b数组里的合法数数量，如果是正数即这个值可行

线段树维护区间最大值，然后询问最靠右的非负叶子下标

#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define maxn 1000005int 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';
}