#include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
typedef long long LL;
int a[N], b[N], _a[N], _b[N];
map<int, int> cnt;
signed main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]] ++;
    for (int i = 1; i <= n; i++) cin >> b[i], cnt[b[i]] ++;

    memcpy(_a, a, sizeof a); memcpy(_b, b, sizeof b);
    cnt[a[1]] --; a[1] = b[1] = 0;

    for (int i = 3; i <= n; i++) a[i] = max(a[i], a[i - 1]);
    for (int i = 3; i <= n; i++) b[i] = max(b[i], b[i - 1]);
    
    for (int i = 2; i <= n; i++)
        cnt[a[i]] += upper_bound(b + 1, b + n + 1, a[i]) - b - 2;

    for (int i = 2; i <= n; i++)
        cnt[b[i]] += upper_bound(a + 1, a + n + 1, b[i] - 1) - a - 2;
    
    int mx = 0, idx = 0;

    for (int i = 1; i <= n; i++)
    {
        if (mx == cnt[_a[i]]) idx = max(idx, _a[i]);
        if (mx < cnt[_a[i]]) mx = cnt[_a[i]], idx = _a[i];
        if (mx == cnt[_b[i]]) idx = max(idx, _b[i]);
        if (mx < cnt[_b[i]]) mx = cnt[_b[i]], idx = _b[i];
    }

    cout << idx << ' ' << mx;
    return 0;
}

挺诡异的一道黄

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
int a[N],b[N],ma[N],mb[N];
map<int,int>f;int mx,t,q[N]; 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];f[a[i]]++;q[++t]=a[i];
		if(i>1)ma[i]=max(ma[i-1],a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];f[b[i]]++;q[++t]=b[i];
		if(i>1)mb[i]=max(mb[i-1],b[i]);
	}
	f[a[1]]--;ma[1]=mb[1]=0;
	for(int i=2;i<=n;i++)
	{
		if(a[i]<=ma[i-1])continue;
		int id1=upper_bound(ma+1,ma+n+1,a[i])-ma;
		int id2=upper_bound(mb+1,mb+n+1,a[i])-mb;
		f[a[i]]+=(id1-i)*(id2-2);
	}
	for(int i=2;i<=n;i++)
	{
		if(b[i]<=mb[i-1])continue;
		int id1=lower_bound(ma+1,ma+n+1,b[i])-ma;
		int id2=upper_bound(mb+1,mb+n+1,b[i])-mb;
		f[b[i]]+=(id1-2)*(id2-i);
	}
	sort(q+1,q+t+1,[](int a,int b){return a>b;});
	for(int i=1;i<=t;i++)mx=max(mx,f[q[i]]);
	for(int i=1;i<=t;i++)if(f[q[i]]==mx)
		cout<<q[i]<<' '<<mx,exit(0);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 200005;
int n;
int a[N], b[N];
int prea[N], preb[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 2; i <= n; i++) prea[i] = max(prea[i - 1], a[i]), preb[i] = max(preb[i - 1], b[i]);
    map<int, long long> cnt;
    cnt[a[1]]++;
    for (int i = 2; i <= n; i++) {
        int rb = upper_bound(preb + 2, preb + n + 1, prea[i]) - preb - 2;
        cnt[prea[i]] += rb;
        int ra = lower_bound(prea + 2, prea + n + 1, preb[i]) - prea - 2;
        cnt[preb[i]] += ra;
        cnt[a[i]]++, cnt[b[i]]++;
    }
    long long mx = 0, mxnum = 0;
    for (auto [v, num] : cnt)
        if (num > mxnum)
            mxnum = num, mx = v;
        else if (num == mxnum && v > mx)
            mx = v;
    cout << mx << " " << mxnum << "\n";
    return 0;
}

此题评价：本题思想工作挺难的，但想好后就容易多了。

正文

相信各位都读懂题意了，在此我就不再赘述了。

定义：在网格图中，第一列第 $n$ 个数记作 $A_{n}$ 。第一行第 $n$ 个数记作 $B_{n}$ 。网格图中第 $i$ 列第 $j$ 行的格子记作 $O_{i,j}$ 。（不存在 $O_ {i,0},O_{0,j}$）。

如果只是单纯的暴力加模拟，一定会 TLE or MLE。

那么，该如何解决呢？

MLE 问题

注意到：对于任意 $O_{i,j}$ 都有 $O_{i,j}=\max(A_{1}\dots A_{i},B_{1}\dots B_{j})$。

为了简化操作 ， 我们用一种类似于前缀和的方式做预处理。 使得 $A_{i}=\max(A_{1}\dots A_{i})$ ， $B_{i}=\max(B_{1}\dots B_{i})$ 。 即：让序列 A ，序列 B 单调不降。

这样， $O_{i,j}=\max(A_{i},B_{j})$ 。 我们可以直接从预处理的序列 A ，序列 B 推出网格图中的某一格子，空间复杂度从 $O(n^{2})$ 降到了 $O(n)$ 。

TLE 问题

为了解决 MLE 问题，我们竟阴差阳错地得到了一个宝贝单调不降序列。

目前，我们每次要提出一个 $A_{i}$ 并与整个序列 B 做一轮比较。

容易发现：总有前几个数数值是相同的且等于 $A_{i}$ ，我们暂时把这个“几”记作 $xp$ 吧。

很容易明白，这是因为序列 B 单调不降。前 $xp$ 个数都小于等于 $A_{i}$ 。

可以考虑二分。这样的话，时间复杂度就会变为 $O(n\log{n})$ 了。

别忘了序列 A 也是单调不降的。

因为 $A_{i}\le A_{i+1}$ 这使得 $xp$ 也只增不减。

考虑双指针。因为两个指针只把两个序列扫一遍，因此时间复杂度变成 $O(n)$ 了。

查找，输出答案

实在想不出别的算法了，就排序吧（痛失 $O(n)$ 的时间复杂度）。

AC code：

#include <bits/stdc++.h>
using namespace std;

#define N (int)2e5+10
int n, xp = 1;

struct num {
	int t, m;
	long long c;
}A[N], B[N], AB_h[2*N];

//-----------------------------------------------------
/*		第一部分 
N 代表 n 的上限 
n 接收 网格图的边长
xp 是 辅助变量，用于查找各个数出现的次数

结构体 num 中：
	t 记录输入的原始数据。 
	m 类似指针，在预处理时指向比它大的数或自己。 
	c 用于记录此数 (t) 出现的次数。

序列A，序列B，分别储存输入的数。
在代码的最后用 AB_h 合并序列A，序列B以便求出答案。

温馨提示： 不开 long long 见祖宗。 
*/ 

bool cmp_one (num a,num b) {
	return a.t > b.t;
}

bool cmp_two (num a,num b) {
	if (a.c == b.c)
		return a.t > b.t;
	else return a.c > b.c;
}

//-----------------------------------------------------
/*		第二部分
两次排序 cmp 均对 num 结构体。 
第一次排序：把相同数 (t) 的放在一起，方便次数相加。 
第二次排序：按照题目要求排序，查找到答案。 
*/ 

int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
		scanf("%d", &A[i].t);
		A[i].m = i;	A[i].c = 1;
		if (i >= 2 && A[i].t < A[A[i-1].m].t)
			A[i].m = A[i-1].m;
	}
	for (int i = 0; i < n; i ++) {
		scanf("%d", &B[i].t);
		B[i].m = i;	B[i].c = 1;
		if (i >= 2 && B[i].t < B[B[i-1].m].t)
			B[i].m = B[i-1].m;
	}
	B[0].c = 0;
	
//-----------------------------------------------------
/*		第三部分-输入部分
输入序列A，序列B并初始化。同时对两者做预处理。 
特殊的东西必须特殊对待，直接把左上角的数的次数调为0
*/ 
	
	for (int i = 1; i < n; i ++) {
		while (A[A[i].m].t >= B[B[xp].m].t && xp < n){
			B[B[xp].m].c += i-1;
			xp ++;
		}
		A[A[i].m].c += xp-1;
	}
	while (xp < n) {
		B[B[xp].m].c += n-1;
		xp ++;
	}
	
//-----------------------------------------------------
/*		第四部分-处理部分1 
xp 作辅助变量，找到各个数的次数，累加到序列A，序列B中。
有个别的数据点使得 xp 不能扫到最后，因此再用 While 封个底
*/ 
	
	for (int i = 0; i < n; i ++) {
		AB_h[2*i+0].t = A[i].t; AB_h[2*i+0].c = A[i].c;
		AB_h[2*i+1].t = B[i].t; AB_h[2*i+1].c = B[i].c;
	}
	sort(AB_h, AB_h+2*n, cmp_one);
	for (int i = 2*n; i >= 0; i --) {
		if (AB_h[i].t == AB_h[i+1].t) {
			AB_h[i].c += AB_h[i+1].c;
			AB_h[i+1].t = AB_h[i+1].c = 0;
		}
	}
	
//-----------------------------------------------------
/*		第五部分-处理部分2
交错存储到AB_h中。
第一次排序后对相同数(t)的次数相加并把后者删除。 
*/ 
	
	sort(AB_h, AB_h+2*n, cmp_two);
	printf("%d %lld", AB_h[0].t, AB_h[0].c);
	
//-----------------------------------------------------
/*		第六部分-输出部分 
第二次排序 输出答案
*/ 
	
    return 0; //完结 
}

后记

时间复杂度为 $O(n\log{n})$ 。 空间复杂度为 $O(n)$ 。

AC 记录。

运行得还算快，用时 $280ms$ 。

What can I say ? I_AM_TLEer out !。