https://ac.nowcoder.com/acm/contest/61132/L

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],n,m;
struct tnode
{
    int tree[N];
    int lowbit(int x)
        {
            return x&-x; 
        }
    void add(int x,int c)
    {
        while(x<N)
        {
            tree[x]+=c;
            x+=lowbit(x);
        }   
    }
    int query(int x)
    {
        int sum=0;
        while(x)
        {
            sum+=tree[x];
            x-=lowbit(x);
        }
        return sum;
    }
};
tnode st;
int main()
{ /*
把所有数字设置成一个树节点，，某个数字右边全+1代表自己是第几个数字
        如果该数字结点==中位数结点 就是中位数
*/
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)   
    {
        cin>>a[i];
        st.add(a[i],1);
    }
    int d=(n+1)/2;
    for(int i=1;i<=m;i++)
    {
        int z,y;
        cin>>z>>y;
        st.add(a[z],-1);
        st.add(y,1);
        a[z]=y;
        int l=1,r=1e6+10;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(st.query(mid)>=d) r=mid;
            else l=mid+1;
        }
        cout<<l<<"\n";
    }
    return 0;
}