简单题
考虑每次都买它能买的最大的，所以他买的一定是价格比他钱低的东西。
我们考虑建立权值线段树，对于\(a_i\)将\([1,a[i]]\)这一段加\(1\)，对于\(b_i\)将\([1,b[i]]\)这一段减\(1\)。
每次查询就查询最右边的值大于\(0\)的，因为这意味着在他后面还有没被购买的。
这里查询最右边是为了保证最大
然后查询那个值就好了，修改就很简单了，不赘述了
代码：
#include#include #include using namespace std;#define rg registervoid read(int &x){ char ch;bool ok; for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1; for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=1e6+10,inf=1e6;int n,m,q,a[maxn],b[maxn];int ls[maxn*4],rs[maxn*4],s[maxn*4],la[maxn*4],sum[maxn*4];void pushdown(int x){ if(!la[x])return ; s[x<<1]+=la[x],s[x<<1|1]+=la[x]; la[x<<1]+=la[x],la[x<<1|1]+=la[x]; la[x]=0;}void update(int x){s[x]=max(s[x<<1],s[x<<1|1]);}void change(int x,int l,int r,int a,int b,int c){ if(a<=l&&b>=r)return s[x]+=c,la[x]+=c,void(); pushdown(x);int mid=(l+r)>>1; if(a<=mid)change(x<<1,l,mid,a,b,c); if(b>mid)change(x<<1|1,mid+1,r,a,b,c); update(x);}int find(int x,int l,int r,int a){ if(l==r)return l; pushdown(x);int mid=(l+r)>>1; if(a<=sum[x<<1])return find(x<<1,l,mid,a); else return find(x<<1|1,mid+1,r,a-sum[x<<1]);}int get(int x,int l,int r,int a){ if(l==r)return find(1,1,inf,a+s[x]); pushdown(x);int mid=(l+r)>>1; if(s[x<<1|1]>0)return get(x<<1|1,mid+1,r,a+sum[x<<1]); if(s[x<<1]>0)return get(x<<1,l,mid,a); return -1;}void modify(int x,int l,int r,int a,int b){ sum[x]+=b;if(l==r)return ; pushdown(x);int mid=(l+r)>>1; if(a<=mid)modify(x<<1,l,mid,a,b); else modify(x<<1|1,mid+1,r,a,b);}int main(){ read(n),read(m); for(rg int i=1;i<=n;i++)read(a[i]),change(1,1,inf,1,a[i],1),modify(1,1,inf,a[i],1); for(rg int i=1;i<=m;i++)read(b[i]),change(1,1,inf,1,b[i],-1); read(q); for(rg int i=1,op,x,y;i<=q;i++){ read(op),read(x),read(y); if(op==1){ change(1,1,inf,1,a[x],-1),modify(1,1,inf,a[x],-1); a[x]=y;modify(1,1,inf,a[x],1);change(1,1,inf,1,a[x],1); int ans=get(1,1,inf,0);printf("%d\n",ans); } else { change(1,1,inf,1,b[x],1),b[x]=y;change(1,1,inf,1,b[x],-1); int ans=get(1,1,inf,0);printf("%d\n",ans); } }}