牛客练习赛$48E$ 小$w$的矩阵前$k$大元素 堆

正解:堆

解题报告:

传送门$QwQ$

考虑把$b$从大往小排序,然后把$a_1+b_1,a_2+b_1,...,a_n+b_1$丢到堆里,顺便记录下$b$的下标

然后每次拿出一个最大值,设为$mx=x+b_i$,就把$x+b_{i+1}$丢进去就成

$over$

然后拓展以下$q$的范围是$m\cdot n$的时候怎么做昂$QAQ$

考虑把$a,b$分别排序,然后二分这个第$k$大是多少,发现$b$的数量是递增的,所以随便维护一下,$check$的复杂度就$O(m+n)$的

然后总的复杂度大概是$O((m+n)\times \log{1e9})$?

($upd:$

$dbq$我康了眼题发现我之前看到的是简略版,,,所以有些细节就忽略掉了$QAQ$

再说点儿细节趴

首先它这个题目里是多次询问,而且$x,y$的范围是变化的

但是注意到每次$x,y$都是单调不降的所以没有关系,只是对$b$的话直接开个$multiset$趴,方便些其实$QwQ$

然后就没了?其实也差不多的$QwQ$

昂然后关于那个法二可能就不太对了,,,放下原来的法二可做的题面趴$QwQ$

($updd:$

$umm$我用我前面写的方法然后发现$T$了,,,$QAQ$

要优化下,怎么优化呢?就把$a,b$全放到$set$里面,这样状态数就更少了$QwQ$

然后差不多的拓展方式?只是要注意现在变成双向拓展了嘛,但是又不能枚举重复状态,所以就加个状态限制的就能保证不重不漏了$QwQ$

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=1e5+;

int n,m,q,a[N],b[N],numa=,numb=;

multiset<int>Sa,Sb;

struct node{multiset<int>::iterator ita,itb;bool zt;};

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

bool operator < (node gd,node gs){return *gd.ita+*gd.itb>*gs.ita+*gs.itb;}

il char rd(){rc ch=gc;while(ch!='R' && ch!='D' && ch!='Q')ch=gc;return ch;}

il void work3()

{

    priority_queue<node>Q;Q.push((node){Sa.begin(),Sb.begin(),});

    ri tmp=read();

    rp(i,,tmp)

    {

        multiset<int>::iterator ita=Q.top().ita,itb=Q.top().itb;bool zt=Q.top().zt;Q.pop();

        printf("%d ",*ita+*itb);

        ++ita;if(zt && ita!=Sa.end())Q.push((node){ita,itb,});;--ita;

        if(++itb!=Sb.end())Q.push((node){ita,itb,});

    }

    printf("\n");

}

int main()

{

    freopen("923e.in","r",stdin);freopen("923e.out","w",stdout);

    n=read();m=read();q=read();rp(i,,n)a[i]=read();rp(i,,m)b[i]=read();Sb.insert(b[]);Sa.insert(a[]);

    while(q--)

    {

        rc ch=rd();

        if(ch=='R'){ri tmp=min(read(),m-numb);rp(i,numb+,numb+tmp)Sb.insert(b[i]);numb+=tmp;}

        if(ch=='D'){ri tmp=min(read(),n-numa);rp(i,numa+,numa+tmp)Sa.insert(a[i]);numa+=tmp;}

        if(ch=='Q')work3();

    }

    return ;

}