正解:堆
解题报告:
考虑把$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$
给一个长度为$n$的序列$a_i$和一个长度为$m$的序列$b_i$,定义一个$n\times m$的矩阵$C$满足$c_{i,j}=a_i+b_j$,求这个矩阵内的前$K$大元素之和
($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 ;
}