简单的线段数上二分

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e6;
ll seg[N*4];  
int n,m;
int a[N];
int ans[N];
void update(int id){
    seg[id]=seg[id*2]+seg[id*2+1];
}
void change(int id,int l,int r,int x,int t){
    if(l==r){
        seg[id]=seg[id]+t;
    }else{
        int mid=(l+r)>>1;
        if(mid>=x) change(id*2,l,mid,x,t);
        else change(id*2+1,mid+1,r,x,t);
        update(id);
    }
}
int query(int id,int l,int r,int x){
    if(l==r){
        return l;
    }else{
        int mid=(l+r)>>1;
        if(seg[id*2]>=x) return query(id*2,l,mid,x);
        else{
            return query(id*2+1,mid+1,r,x-seg[id*2]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        change(1,1,M,a[i],1);
    }
    int wei=(n+1)/2;
    for(int j=1;j<=m;j++){
        int x,d;
        scanf("%d%d",&x,&d);
        change(1,1,M,a[x],-1);
        change(1,1,M,d,1);
        a[x]=d;
        printf("%d\n",query(1,1,M,wei));
    }
    return 0;
}