题目

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1001
#define MAXM 500001

int n, q, v, ind, lans, cnt;
int it[MAXN], ans[MAXM];
int a[MAXN][MAXN];

struct Node{
	int ind, v;
}nodes[MAXM];

bool cmp(Node a, Node b){
	return a.v > b.v;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> q;
    for (int i(1); i<=n; ++i){
    	for (int j(1); j<=n; ++j) cin >> a[i][j];
    	sort(a[i]+1, a[i]+n+1, greater<int>());
    	it[i] = 1;
	}
	for (int i(1); i<=q; ++i){
		cin >> nodes[i].v;
		nodes[i].ind = i;
	}
	sort(nodes+1, nodes+q+1, cmp);
	
	for (int i(1); i<=q; ++i){
		v = nodes[i].v;
		ind = nodes[i].ind;
		cnt = 0;
		for (int j(1); j<=n; ++j){
			while (it[j] <= n && a[j][it[j]] >= v){
				++it[j];
				++cnt;
			}
		}
		ans[ind] = min(lans+cnt, n);
		lans = ans[ind];
	}
	for (int i(1); i<=q; ++i) cout << ans[i] << '\n';

    return 0;
}

这是离线的代码。显然，最内层的循环最多只会执行 $n^2$ 次。

那我能不能把时间复杂度简单地算为 $O(n^2 \log n+n^2 +q \log q+q)=O(n^2 \log n+q \log q)$。

尽管有一个 $q$ 次的循环套一个 $n$ 次的循环，但是复杂度却优于 $O(nq)$。有点令人不可置信。