codeforces
简单题
考虑每次都买它能买的最大的，所以他买的一定是价格比他钱低的东西。
我们考虑建立权值线段树，对于(a_i)将([1,a[i]])这一段加(1)，对于(b_i)将([1,b[i]])这一段减(1)。
每次查询就查询最右边的值大于(0)的，因为这意味着在他后面还有没被购买的。
这里查询最右边是为了保证最大
然后查询那个值就好了，修改就很简单了，不赘述了
代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define rg register
void 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
",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
",ans);
}
}
}