Chrysanthemum's Blog

易知，每次操作后中位数要么不变要么增加一。因此我们只要分块判断此时的中位数是否需要加一。

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,mid,x,y,L,R,len,num,sum,k;
int l[10010],r[10010],b[100010],tag[10010];
struct node{int x,id;}a[100010];
bool cmp(const node x,const node y){return x.x<y.x;}
void add(int x,int L,int R)
{
    for (int i=l[x];i<=r[x];i++)if (a[i].id>=L&&a[i].id<=R)a[i].x++;
    sort(a+l[x],a+r[x]+1,cmp);
}
int binary(int l,int r,int x)
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    if (a[mid].x>=x) return binary(l,mid,x);return binary(mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].id=i;
    }
    for (int i=1;i<=n;i++)
        b[i]=a[i].x;
    nth_element(b+1,b+(n/2)+1,b+n+1);
    mid=b[n/2+1];
    len=(int)sqrt(n);
    if (n%len) num=n/len+1;else num=n/len;
    for (int i=1;i<=num;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=min(n,i*len);
        sort(a+l[i],a+r[i]+1,cmp);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        L=x/len;
        if (x>r[L]) L++;
        R=y/len;
        if (y>r[R]) R++;
        if (L==R) add(L,x,y);else
        {   
            add(L,x,r[L]);add(R,l[R],y);
            for (int j=L+1;j<R;j++) tag[j]++;
        }
        sum=0;
        mid++;
        for (int j=1;j<=num;j++)
        {
            k=binary(l[j],r[j],mid-tag[j]);
            if (a[k].x>=mid-tag[j]) k--;
            if (k>=l[j]) sum+=k-l[j]+1;
        }
        if (sum>n/2) mid--;
        printf("%d\n",mid);
    }
}