整体二分

题目链接:Dynamic Rankings

整体二分:

int sum[50005],n;

void update(int wz,int val)
{
    for(; wz<=n; wz+=wz&(-wz))
        sum[wz]+=val;
}

int get_sum(int l,int r)
{
    int res=0;
    for(; r; r-=r&(-r))
        res+=sum[r];
    for(--l; l; l-=l&(-l))
        res-=sum[l];
    return res;
}

struct node
{
    int l,r,k,op,wz;
} a[150005],t[150005];

int ans[10005];

void bs(int l,int r,int opl,int opr)
{
    if(l==r)
    {
        for(int i=opl; i<=opr; i++)
            if(a[i].op==2)ans[a[i].wz]=l;
        return;
    }
    int mid=(l+r)>>1,x=opl-1,y=opl-1;
    for(int i=opl; i<=opr; i++)
        if(a[i].op<=1)
            if(a[i].l<=mid)
                update((a[++x]=a[i]).wz,a[i].op);
            else t[++y]=a[i];
        else
        {
            int res=get_sum(a[i].l,a[i].r);
            if(a[i].k<=res)a[++x]=a[i];
            else t[++y]=a[i],t[y].k-=res;
        }
    int opm=x;
    for(int i=opl; i<=y; i++)a[++x]=t[i];
    for(int i=opl; i<=opm; i++)
        if(a[i].op<=1)update(a[i].wz,-a[i].op);
    if(opl<=opm)bs(l,mid,opl,opm);
    if(opm+1<=opr)bs(mid+1,r,opm+1,opr);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int q,minn=inf,maxx=-inf;
        scanf("%d%d",&n,&q);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].l);
            a[i].r=a[i].l,a[i].op=1,a[i].wz=i;
            if(a[i].l>maxx)maxx=a[i].l;
            if(a[i].l<minn)minn=a[i].l;
        }
        char op[2];
        int idx=n,x,y,z=0;
        while(q--)
        {
            scanf("%s",op);
            if(op[0]=='Q')
            {
                ++idx;
                scanf("%d%d%d",&a[idx].l,&a[idx].r,&a[idx].k);
                a[idx].op=2,a[idx].wz=++z;
            }
            if(op[0]=='C')
            {
                scanf("%d%d",&x,&y);
                if(y>maxx)maxx=y;
                if(y<minn)minn=y;
                a[++idx].op=-1,a[idx].l=a[x].r,a[idx].wz=x;
                a[++idx].op=1,a[idx].l=y,a[idx].wz=x;
                a[x].r=y;
            }
        }
        bs(minn,maxx,1,idx);
        for(int i=1; i<=z; i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

题目链接:K大数查询

整体二分:

int n;
ll c[50005],d[50005];

void update(int l,int r,ll val)
{
    for(int i=l--; i<=n; i+=i&(-i))
        c[i]+=val,d[i]+=l*val;
    for(int i=r+1; i<=n; i+=i&(-i))
        c[i]-=val,d[i]-=r*val;
}

ll get_sum(int l,int r)
{
    ll res=0;
    for(int i=r; i; i-=i&(-i))
        res+=r*c[i]-d[i];
    for(int i=--l; i; i-=i&(-i))
        res-=l*c[i]-d[i];
    return res;
}

struct node
{
    int l,r,op,wz;
    ll k;
} a[100005],t[100005];

int ans[50005];

void bs(ll l,ll r,int opl,int opr)
{
    if(l==r)
    {
        for(int i=opl; i<=opr; i++)
            if(a[i].op==2)ans[a[i].wz]=l;
        return;
    }
    ll mid=(l+r)>>1;
    int x=opl-1,y=opl-1;
    for(int i=opl; i<=opr; i++)
        if(a[i].op==1)
            if(a[i].k>mid)
            {
                update(a[i].l,a[i].r,1);
                a[++x]=a[i];
            }
            else t[++y]=a[i];
        else
        {
            ll res=get_sum(a[i].l,a[i].r);
            if(a[i].k<=res)a[++x]=a[i];
            else t[++y]=a[i],t[y].k-=res;
        }
    int opm=x;
    for(int i=opl; i<=y; i++)a[++x]=t[i];
    for(int i=opl; i<=opm; i++)
        if(a[i].op==1)update(a[i].l,a[i].r,-1);
    if(opl<=opm)bs(mid+1,r,opl,opm);
    if(opm+1<=opr)bs(l,mid,opm+1,opr);
}

int main()
{
    int q,idx=0;
    ll maxx=-1e18,minn=1e18;
    scanf("%d%d",&n,&q);
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d%d%lld",&a[i].op,&a[i].l,&a[i].r,&a[i].k);
        if(a[i].op==1)
        {
            if(a[i].k>maxx)maxx=a[i].k;
            if(a[i].k<minn)minn=a[i].k;
        }
        else a[i].wz=++idx;
    }
    bs(minn,maxx,1,q);
    for(int i=1; i<=idx; i++)
        printf("%d\n",ans[i]);
    return 0;
}