给出一个长度为n的数列({a_i})和一个长度为m的二元组数列({b_i,c_i})，现在请寻找一个二元组({b_i,c_i})使得第一元在a数列中出现次数尽可能多的前提下，第二元在a中出现的次数尽可能多，(1≤n,m≤200000)。
解
显然数据范围支持我们枚举选哪个二元组，于是问题就转化成如何快速查询一个数字在数列a中出现的次数，自然想到桶排，但是注意到序列a的数字范围过大，于是可以考虑离散化或者hash，然后就可以做到(O(log(n)))或者(O(1))查询。
但要注意的几点是可能二元组的某些数在序列中压根没出现过，这个要特判为0.
参考代码：
离散化
#include <iostream>
#include <cstdio>
#include <algorithm>
#define il inline
#define ri register
#define Size 200050
using namespace std;
struct lsh{
int a[Size],b[Size],n;
il void prepare(int size,int ar[]){n=size;
for(ri int i(1);i<=n;++i)a[i]=ar[i];sort(a+1,a+n+1);
for(ri int i(1);i<=n;++i)b[i]=dfs(ar[i]);
}
il int dfs(int x){
int l(1),r(n),mid;
while(l<=r){
mid=l+r>>1;
if(a[mid]<x)l=mid+1;
else r=mid-1;
}if(a[l]==x)return l;
return 0;
}
}L;
struct pi{
int b,c;
}p[Size],hl;
int a[Size],bu[Size];
il void read(int&);
int main(){
int n,m,czf;read(n);
for(int i(1);i<=n;++i)read(a[i]);read(m);
for(int i(1);i<=m;++i)read(p[i].b);
for(int i(1);i<=m;++i)read(p[i].c);
L.prepare(n,a);
for(int i(1);i<=n;++i)++bu[L.b[i]];
for(int i(1),j;i<=m;++i){
j=L.dfs(p[i].b);
if(bu[j]>hl.b)hl.b=bu[j],hl.c=bu[L.dfs(p[i].c)],czf=i;
else if(bu[j]==hl.b){j=L.dfs(p[i].c);
if(bu[j]>hl.c)hl.c=bu[j],czf=i;
}
}printf("%d",czf);
return 0;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
hash
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define Size 200100
#define czf 1188839
using namespace std;
struct unordered_map{
struct DATA{
DATA*next;int d,b;
}*head[czf],*pt;
il void insert(int d){
int H(d%czf);pt=new DATA;
pt->next=head[H],pt->d=d,pt->b=1;
head[H]=pt;
}
il DATA* find(int d){
for(pt=head[d%czf];pt!=NULL;pt=pt->next)
if(pt->d==d)return pt;return NULL;
}
}un;
struct pi{
int b,c;
}p[Size],hl;
int a[Size];
il void read(int&);
int main(){int n,m,lsy(1);read(n);
for(int i(1);i<=n;++i)read(a[i]);read(m);
for(int i(1);i<=m;++i)read(p[i].b);
for(int i(1);i<=m;++i)read(p[i].c);
for(int i(1);i<=n;++i)
if(un.find(a[i])==NULL)un.insert(a[i]);
else ++un.find(a[i])->b;
for(int i(1);i<=m;++i){
if(un.find(p[i].b)==NULL)continue;
if(un.find(p[i].b)->b>hl.b){
hl.b=un.find(p[i].b)->b,lsy=i;
if(un.find(p[i].c)==NULL){hl.c=0;continue;}
hl.c=un.find(p[i].c)->b;
}
else if(un.find(p[i].b)->b==hl.b){
if(un.find(p[i].c)==NULL)continue;
if(un.find(p[i].c)->b>hl.c)
hl.c=un.find(p[i].c)->b,lsy=i;
}
}printf("%d",lsy);
return 0;
}
il void read(int &x){
x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}