不想写 $O(n\log n)$ 做法

#include <bits/stdc++.h>
#pragma GCC optimize(3)
typedef long long ll;
using namespace std;

const ll mod = 1e9 + 7;

inline ll read() {
	ll ret = 0;
	char c;
	do {
		c = getchar();
	} while (('0' > c) | ('9' < c));
	do {
		ret = (ret << 3) + (ret << 1) + c - 48;
		c = getchar();
	} while (('0' <= c) & (c <= '9'));
	return ret;
}
inline void write(ll x) {
	if (!x) {
		putchar('0');
		return;
	}
	ll revx = 0;
	ll hz0 = 0;
	bool hz = 1;
	while (x) {
		revx = (revx << 3) + (revx << 1) + x % 10;
		if (hz & !(x % 10)) {
			++hz0;
		} else {
			hz = 0;
		}
		x /= 10;
	}
	while (revx) {
		putchar(revx % 10 + '0');
		revx /= 10;
	}
	for (ll i = 1; i <= hz0; ++i) {
		putchar('0');
	}
}

int n, m, s[5002];
int ansf = 0;
ll anss = 1; // count, ways
int gcl[5002][5002] = {{}}, gcr[5002][5002] = {{}}; //[flavor][position]
vector<int> c[5002];

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			gcl[j][i] = gcl[j][i - 1];
		}
		++gcl[s[i]][i];
	}
	for (int i = n; i >= 1; --i) {
		for (int j = 1; j <= n; ++j) {
			gcr[j][i] = gcr[j][i + 1];
		}
		++gcr[s[i]][i];
	}
	for (int i = 1; i <= m; ++i) {
		int f, h;
		f = read(), h = read();
		c[f].push_back(h);
	}
	for (int tp = 1; tp <= n; ++tp) {
		sort(c[tp].begin(), c[tp].end());
	}
	for (int tp = 1; tp <= n; ++tp) {
		for (int& h : c[tp]) {
			if (gcl[tp][n] < h) {
				break;
			}
			int lm; // the leftmost position---------------------------------------------------
			int l = 1, r = n, mid;
			while (l < r) {
				mid = (l + r) >> 1;
				if (gcl[tp][mid] >= h) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			lm = l;
			int curf = 1;
			ll curs = 1;
			// tp1 != tp--------------------------------------------------------------------
			for (int tp1 = 1; tp1 <= n; ++tp1) {
				if (tp1 == tp) {
					continue;
				}
				int lc = 0, rc = 0, lrc = 0;
				for (int& h1 : c[tp1]) {
					if ((gcl[tp1][lm] >= h1) & (gcr[tp1][lm] >= h1)) {
						++lrc;
					} else if (gcl[tp1][lm] >= h1) {
						++lc;
					} else if (gcr[tp1][lm] >= h1) {
						++rc;
					} else {
						break;
					}
				}
				if ((lrc >= 2) | (bool(lrc) & bool(lc + rc))) {
					curf += 2;
					curs = curs * lrc * (lrc - 1 + lc + rc) % mod;
				} else if (lrc + lc + rc) {
					++curf;
					curs = curs * ((lrc << 1) + lc + rc) % mod;
				}
			}
			// tp1 == tp--------------------------------------------------------------------
			int rc;
			int l2 = -1, r2 = c[tp].size() - 1, mid2;
			while (l2 < r2) {
				mid2 = (l2 + r2 + 1) >> 1;
				if (c[tp][mid2] < gcr[tp][lm]) {
					l2 = mid2;
				} else {
					r2 = mid2 - 1;
				}
			}
			if (l2 == -1) {
				rc = 0;
			} else {
				rc = l2 + 1;
				if (c[tp][l2] >= h) {
					--rc;
				}
			}
			if (rc) {
				++curf;
				curs = curs * rc % mod;
			}
			// update ans----------------------------------------------------------------
			if (curf > ansf) {
				ansf = curf;
				anss = curs;
			} else if (curf == ansf) {
				anss = (anss + curs) % mod;
			}
		}
	}
	// only right------------------------------------------------------------------------
	int olrf = 0;
	ll olrs = 1;
	for (int tp = 1; tp <= n; ++tp) {
		int rc;
		int l = -1, r = c[tp].size() - 1, mid;
		while (l < r) {
			mid = (l + r + 1) >> 1;
			if (c[tp][mid] <= gcr[tp][1]) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		rc = l + 1;
		if (rc) {
			++olrf;
			olrs = olrs * rc % mod;
		}
	}
	if (bool(olrf) | bool(olrs != 1)) {
		if (olrf > ansf) {
			ansf = olrf;
			anss = olrs;
		} else if (ansf == olrf) {
			anss = (anss + olrs) % mod;
		}
	}
	write(ansf);
	putchar(' ');
	write(anss);
	return 0;
}